K&R C programming language exercise 2-9

Question

I don't understand the exercise 2-9, in K&R C programming language, chapter 2, 2.10:

Exercise 2-9. In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x . Explain why. Use this observation to write a faster version of bitcount .

the bitcount function is:

/* bitcount: count 1 bits in x */

int bitcount(unsigned x)
{
    int b;
    for (b = 0; x != 0; x >>= 1)
        if (x & 01)
            b++;
    return b;
}

The function deletes the rightmost bit after checking if it is bit-1 and then pops in the last bit .

I can't understand why x&(x-1) deletes the right most 1-bit? For example, suppose x is 1010 and x-1 is 1001 in binary, and x&(x-1) would be 1011, so the rightmost bit would be there and would be one, where am I wrong?

Also, the exercise mentioned two's complement, does it have something to do with this question?

Thanks a lot!!!

Answer 1

Ik I'm already very late (≈ 3.5yrs) but your example has mistake.

x = 1010 = 10
x - 1 = 1001 = 9
1010 & 1001 = 1000

So as you can see, it deleted the rightmost bit in 10.

7 = 111
6 = 110
5 = 101
4 = 100
3 = 011
2 = 010
1 = 001
0 = 000

Observe that the position of rightmost 1 in any number, the bit at that same position of that number minus one is 0. Thus ANDing x with x-1 will be reset (i.e. set to 0) the rightmost bit.

7 & 6 = 111 & 110 = 110 = 6
6 & 5 = 110 & 101 = 100 = 4
5 & 4 = 101 & 100 = 100 = 4
4 & 3 = 010 & 011 = 010 = 2
3 & 2 = 011 & 010 = 010 = 2
2 & 1 = 010 & 001 = 000 = 0
1 & 0 = 001 & 000 = 000 = 0

Answer 2

Here is a simple way to explain it. Let's arbitrarily assume that number Y is xxxxxxx1000 (x can be 0 or 1).

xxxxxxx1000 - 1 = xxxxxxx0111

xxxxxxx1000 & xxxxxxx0111 = xxxxxxx0000 (See, the "rightmost 1" is gone.)

So the number of repetitions of Y &= (Y-1) before Y becomes 0 will be the total number of 1's in Y.

Answer 3

First, you need to believe that K&R are correct. Second, you may have some mis-understanding on the words.

Let me clarify it again for you. The rightmost 1-bit does not mean the right most bit, but the right most bit which is 1 in the binary form.

Let's arbitrary assume that x is xxxxxxx1000(x can be 0 or 1). Then from right to left, the fourth bit is the "rightmost 1-bit". On the basis of this understanding, let's continue on the problem.

Why x &=(x-1) can delete the rightmost 1-bit?

In a two's complement number system, -1 is represented with all 1 bit-pattern.

So x-1 is actually x+(-1), which is xxxxxxx1000+11111111111. Here comes the tricky point.

before the righmost 1-bit, all 0 becomes 1 and the rightmost 1-bit becomes 0 and there is a carry 1 go to left side. And this 1 will continue to proceed to the left most and cause an overflow, meanwhile, all 'x' bit is still a because 'x'+'1'+'1'(carry) causes a 'x' bit.

Then x & (x-1) will delete the rightmost 1-bit.

Hope you can understand it now.

Thanks.

Answer 4

Why do x & (x-1) delete the right most order bit? Just try and see:

If the righmost order bit is 1, x has a binary representation of a...b1 and x-1 is a...b0 so the bitwise and will give a...b1 because common bits are left unchanged by the and and 1 & 0 is 0

Else x has a binary representation of a...b10...0; x-1 is a...b01...1 and for same reason as above x & (x-1) will be a...b00...0 again clearing the rightmost order bit.

So instead of scanning all bits to find which one are 0 and which one are 1, you just iterate the operation x = x & (x-1) until x is 0: the number of steps will be the number of 1 bits. It is more efficient than the naive implementation because statistically you will use half number of steps.

Example of code:

int bitcount(unsigned int x) {
    int nb = 0;
    while (x != 0) {
        x &= x-1;
        nb++
    }
    return nb;
}