Thread: 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?

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

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.

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

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.

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.