| View previous topic - View next topic |
| Author |
Message |
Tenshi
Everyone's Peachy Lil' Bitch
Joined: 31 May 2002
Posts: 386
Location: Newport News
|
 Posted: Wed Feb 19, 2003 6:30 am Post subject: THE TIGHTEST bit-counting algorithm EVER! |
[quote] |
|
- I learned this one in Algorithms' class. I just had to share it. It's so beautiful and elegant, it makes me drool.
| Code: | count_bits( N )
count = 0
while ( N != 0 )
N = N ^ (N - 1 ) // ^ = bitwise AND
count ++
return count |
It's beautiful.
If count = 1 or 0, then N is a power of 2.
Also, this algorithm runs in the amount of time of the number of bits there are. If there're only 3 bits and you're checking a 128 bit number, it only executes 3 times.
_________________
- Jaeda
|
|
| Back to top |
|
 |
Nexinarus
Slightly Deformed Faerie Princess
Joined: 25 Oct 2002
Posts: 32
Location: In the distance
|
| Posted: Wed Feb 19, 2003 8:35 am Post subject: |
[quote] |
|
wha im not sure what you mean by what that will do when you say "count bits" ?
_________________
Anorexia is phat!
|
|
| Back to top |
|
|
Guest
|
| Posted: Wed Feb 19, 2003 11:44 am Post subject: |
[quote] |
|
err... he probably mean that it count bits.. like in "count bits" yeah.. it could also maybe count bits..
like err... bit counting... yup.. that's it..
it counts the number of bits that are set in a given number.
like bitcount(0xFF) == 8 && bitcount(3) = 2... etc...
probably... but I could be wrong...
|
|
| Back to top |
|
|
Nexinarus
Slightly Deformed Faerie Princess
Joined: 25 Oct 2002
Posts: 32
Location: In the distance
|
| Posted: Wed Feb 19, 2003 6:22 pm Post subject: |
[quote] |
|
ah silly me. X_X
_________________
Anorexia is phat!
|
|
| Back to top |
|
|
Tenshi
Everyone's Peachy Lil' Bitch
Joined: 31 May 2002
Posts: 386
Location: Newport News
|
| Posted: Thu Feb 20, 2003 6:29 am Post subject: |
[quote] |
|
- Yeah, and it runs in the amount of time of bits there are. It's so pretty I almost get off on it (I'm kidding, seriously). I don't think I would have come up with that if I had to think of it myself. This class is honestly the highlight of my day every MWF.
- And yes, it counts bits...
100111000000000000000111 = 7 ; and it would only execute seven times.
1000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000001 = 2
And it would only loop through twice.
- This algorithm is tight!
_________________
- Jaeda
|
|
| Back to top |
|
|
Nexinarus
Slightly Deformed Faerie Princess
Joined: 25 Oct 2002
Posts: 32
Location: In the distance
|
| Posted: Thu Feb 20, 2003 8:13 am Post subject: |
[quote] |
|
no offence but.. um.. does this have any use ? :P
_________________
Anorexia is phat!
|
|
| Back to top |
|
|
Tenshi
Everyone's Peachy Lil' Bitch
Joined: 31 May 2002
Posts: 386
Location: Newport News
|
| Posted: Thu Feb 20, 2003 6:07 pm Post subject: |
[quote] |
|
- Yes. a lot! If you need to quickly determine a power of 2 (remember, a modulus doesn't necessarily determine a power of X); and if you use a lot of bit flags.
_________________
- Jaeda
|
|
| Back to top |
|
|
