# Counter the number of 1 bits?

This is a discussion on Counter the number of 1 bits? within the C++ Programming forums, part of the General Programming Boards category; I'm having a trouble of thinking of way to count the number of 1 bits in a binary number with ...

1. ## 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.

2. Oooh! Pick me!

3. 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

4. (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.

5. Code:
```	int num = 46;
int bit = 1;
int count = 0;

while (bit <= 128)
{
count += ((num & bit) > 0);
bit <<= 1;
}

cout << "Has " << count << " bits." << endl;```

6. 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!

7. 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)))

8. 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.

9. 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.

10. Let's face it though - my solution is more elegant.

11. Is this a contest? Should I do the standard "yeah, but mine's faster" reply now, or what?

Quzah

12. 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.

13. I want simplicity =]

14. 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];
}```

15. 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];
}```

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!!!

Page 1 of 3 123 Last