# Counter the number of 1 bits?

Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last
• 04-03-2005
gqchynaboy
Counter the number of 1 bits?
I'm having a trouble of thinking of way to count the number of 1 bits in a binary number with out using any condition tests or branches. Only ones i know have condition tests or branches like

Code:

```while (n!=0) { count++; n=n&(n-1) }```
This is for my assembly language class and I'm supposed to use any kind of shifting or and/or. But if I saw it in C++ i probably be able to convert it.
• 04-03-2005
Dave_Sinkula
Oooh! Pick me!
• 04-03-2005
gqchynaboy
Quote:

Originally Posted by Dave_Sinkula
Oooh! Pick me!

Sorry but I dont think it will work, I forgot to mention I need to count 8-bits :(
• 04-03-2005
Hunter2
(1 << n) is a mask for bit #n.

(number & mask) == 0 when the bit is 0.
(number & mask) != 0 when the bit is 1.

Now loop for each bit from 0 to 7, checking if each is 1.
• 04-03-2005
samGwilliam
Code:

```        int num = 46;         int bit = 1;         int count = 0;         while (bit <= 128)         {                 count += ((num & bit) > 0);                 bit <<= 1;         }         cout << "Has " << count << " bits." << endl;```
• 04-03-2005
quzah
Code:

```unsigned char count foo( unsigned char b ) {     return (!!(b&  1))+(!!(b&  2))+(!!(b&  4))+(!!(b&  8))+           (!!(b& 16))+(!!(b& 32))+(!!(b& 64)0+(!!(b&128)); }```
Me too, me too!
• 04-03-2005
gqchynaboy
Quote:

Originally Posted by quzah
Code:

```unsigned char count foo( unsigned char b ) {     return (!!(b&  1))+(!!(b&  2))+(!!(b&  4))+(!!(b&  8))+           (!!(b& 16))+(!!(b& 32))+(!!(b& 64)0+(!!(b&128)); }```
Me too, me too!

What does the !! mean? And is this for 128 bits? and if i wanted 8 bits I would use
return (!!(b& 1))+(!!(b& 2))+(!!(b& 4))+(!!(b& 8)))
• 04-03-2005
quzah
No. It's for eight bits. Just like you wanted. ! is the the "not" operator. That means, if something is non-zero, it becomes zero. Otherwise, it becomes 1. We apply it twice, to make it "change non-zero to zero and then to one".

Otherwise, without it, you just end up with whatever value you origionally pass to the function.

Quzah.
• 04-03-2005
Lithorien
Quote:

Originally Posted by gqchynaboy
What does the !! mean? And is this for 128 bits? and if i wanted 8 bits I would use
return (!!(b& 1))+(!!(b& 2))+(!!(b& 4))+(!!(b& 8)))

Here's a hint: Powers of 2.

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128

Range from 0-7: 8. Therfore, Quzah is correct in his statement - he is covering all 8 bits in a byte.
• 04-03-2005
samGwilliam
Let's face it though - my solution is more elegant.
• 04-03-2005
quzah
Is this a contest? Should I do the standard "yeah, but mine's faster" reply now, or what?

Quzah
• 04-03-2005
samGwilliam
Quote:

Originally Posted by quzah
Is this a contest? Should I do the standard "yeah, but mine's faster" reply now, or what?

Quzah

I'm always finding myself torn between efficiency and elegance, but for such a trivial problem you may as well just plump for elegance.
• 04-03-2005
gqchynaboy
I want simplicity =]
• 04-03-2005
Prelude
Simple, elegant, and about as fast as it gets. Next?
Code:

```int bits[] = {   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3,   3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,   3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,   3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3,   3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,   3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,   3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,   6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,   3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4,   4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5,   5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4,   3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4,   4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,   6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7,   6, 7, 7, 8 }; int count ( unsigned char x ) {   return bits[x]; }```
:D
• 04-03-2005
samGwilliam
Quote:

Originally Posted by Prelude
Simple, elegant, and about as fast as it gets. Next?
Code:

```int bits[] = {   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3,   3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,   3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,   3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3,   3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,   3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,   3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,   6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,   3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4,   4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5,   5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4,   3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4,   4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,   6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7,   6, 7, 7, 8 }; int count ( unsigned char x ) {   return bits[x]; }```
:D

:cool:

For extra brownie points you could compute the look-up table beforehand instead of manually bashing it out. For any more bits than this, you'd need to!!!
Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last