# Thread: Understanding this bitwise function

1. ## Understanding this bitwise function

How does this bitwise function work(below), if you are ANDing two 8-bit numbers I understand that but as ints are either two or four bytes do you just set all the bits out in a row, For example to AND two 8-bit bytes you would do

00000001
00000011
-------- ANDing would give
00000001

So how do you AND an int?

Is it just,

01010101010101010101010101010101
10101010101010101010101010101010

etc...

This function also creates negative values for the (x-1) part and -1 for an unsigned int is 4294967295

Code:
```int count_ones(unsigned int x)
{
int result = 0;

while(x != 0) {
result++;
x = x & (x-1);
cout << x << "\n";
}

return result;
}```
So how exactly would you explain this on paper?

2. x = x & (x-1) is used to clear the least significant bit that is set in x. As the function states, it's counting the number of one bits.

Note there's an intrinsic function, popcnt, that uses a single X86 instruction to count the number of 1 bits, if it's available on your processor

3. Originally Posted by jim_0
How does this bitwise function work(below), if you are ANDing two 8-bit numbers I understand that but as ints are either two or four bytes do you just set all the bits out in a row, For example to AND two 8-bit bytes you would do
Yes -- it's the same, just longer numbers. You can do bitwise stuff to anything that's got bits -- strings, floating point, anything. Though the compiler will try pretty hard to stop you in some of those cases, but hey, that's what pointers are for.

Is it just,

01010101010101010101010101010101
10101010101010101010101010101010
etc...
Exactly.

This function also creates negative values for the (x-1) part and -1 for an unsigned int is 4294967295

Code:
```int count_ones(unsigned int x)
{
int result = 0;

while(x != 0) {
result++;
x = x & (x-1);
cout << x << "\n";
}

return result;
}```
So how exactly would you explain this on paper?
I don't follow what you mean about negative numbers. Signed integer over/overflow is undefined by the C standard, if I recall my facts correctly, so it'd be a very bad idea to use it.
Unsigned -- yes, 0-1 will give 0xffffffff. That can't happen in this function though because of the while loop check for 0.

As for how it works, I do get it but I don't think I can explain without a pile of binary. So let's do that.....

Take 290, which is 100100010. Because that isn't 0, straight away we know there are some ones to count.
x-1 is 100100001. The & doesn't make any difference yet
x-1 again is 288, 100100000

So far have been ticking off the 1s quite nicely. Next x-1 is 287, which is 100011111. Putting it next to the release result:

288 100100000
287 100011111

The subtraction has meant several more bits get set. We're not interested in these, so we use the previous value as a mask to get rid of the unwanted bits.
That gives 256: 100000000

255: 011111111'
Those two mask each other out, leaving 0.

There were 3 ones set initially, and every subtraction removes a 1. Either directly if it's the bottom bit, or indrectly by causing a carry to set lots of ones that are then cleared. Because of the &, no bit that has been cleared can become set again, so the number of bit clearing iterations gives the number of set bits.

I don't think I could explain it on 'paper' like proper paper.

4. Originally Posted by smokeyangel
explain without a pile of binary. So let's do that ... Take 290, which is 100100010.
Showing 16 bits

1st loop: x = x & (x-1) = 0000000100100010 & 0000000100100001 = 000000100100000
2nd loop: x = x & (x-1) = 0000000100100000 & 0000000100011111 = 000000100000000
3rd loop: x = x & (x-1) = 0000000100000000 & 0000000011111111 = 000000000000000

5. Not to be beaten on 'who can post the most binary today', I assulted a double and make it pretend to be an integral value for 10 mins. Here's what 1.2548246 looked like

Code:
```0b11111111110100000100111100001011110101101100110111010111100000
0b11111111110100000100111100001011110101101100110111010111000000
0b11111111110100000100111100001011110101101100110111010110000000
0b11111111110100000100111100001011110101101100110111010100000000
0b11111111110100000100111100001011110101101100110111010000000000
0b11111111110100000100111100001011110101101100110111000000000000
0b11111111110100000100111100001011110101101100110110000000000000
0b11111111110100000100111100001011110101101100110100000000000000
0b11111111110100000100111100001011110101101100110000000000000000
0b11111111110100000100111100001011110101101100100000000000000000
0b11111111110100000100111100001011110101101100000000000000000000
0b11111111110100000100111100001011110101101000000000000000000000
0b11111111110100000100111100001011110101100000000000000000000000
0b11111111110100000100111100001011110101000000000000000000000000
0b11111111110100000100111100001011110100000000000000000000000000
0b11111111110100000100111100001011110000000000000000000000000000
0b11111111110100000100111100001011100000000000000000000000000000
0b11111111110100000100111100001011000000000000000000000000000000
0b11111111110100000100111100001010000000000000000000000000000000
0b11111111110100000100111100001000000000000000000000000000000000
0b11111111110100000100111100000000000000000000000000000000000000
0b11111111110100000100111000000000000000000000000000000000000000
0b11111111110100000100110000000000000000000000000000000000000000
0b11111111110100000100100000000000000000000000000000000000000000
0b11111111110100000100000000000000000000000000000000000000000000
0b11111111110100000000000000000000000000000000000000000000000000
0b11111111110000000000000000000000000000000000000000000000000000
0b11111111100000000000000000000000000000000000000000000000000000
0b11111111000000000000000000000000000000000000000000000000000000
0b11111110000000000000000000000000000000000000000000000000000000
0b11111100000000000000000000000000000000000000000000000000000000
0b11111000000000000000000000000000000000000000000000000000000000
0b11110000000000000000000000000000000000000000000000000000000000
0b11100000000000000000000000000000000000000000000000000000000000
0b11000000000000000000000000000000000000000000000000000000000000
0b10000000000000000000000000000000000000000000000000000000000000
0b0```
37 set bits, apparently. There, now I have enriched everyone's life I shall head off. Probably into the slightly black and white matrix above.

[code]

6. Originally Posted by smokeyangel
Not to be beaten on 'who can post the most binary today'
That wasn't my point. I wanted to make clear that it was the & (binary) and operation with x and (x-1) that is clearing the least significant 1 bit.

7. It wasn't a serious comment on my part -- I was just being silly. I didn't even think when I wrote it. Anyway, apologies for the misunderstanding.

Popular pages Recent additions