Exercise about counting 1 bits in an integer in C

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 mentioned by the exercise is this:

/* 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;
}

I kind of got why this happens intuitively but I couldn't find a more rigorous answer, here's the answer I came up with anyways: the reason behind this I guess is because when we subtract one we change the position of the rightmost bit therefore when we bitwise AND x with x-1 the rightmost 1 disappears because the rightmost 1 in x changed its position in x - 1 because of substracting one for example if x = 1010 then x-1 = 1001 and when we bitwise AND them we get 1000 so the rightmost 1 in x disappeared

And here's my implementation of this idea to write a shorter version of bitcount:

#include <stdio.h>

int bitcount(unsigned x);

int main() {
    int x, onebits;
    printf("Enter an integer: ");
    scanf("%d", &x);
    onebits = bitcount(x);
    printf("This integer contains %d one bits.", onebits);
    return 0;
}

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

Can anyone correct me if I made any mistakes or provide a more rigorous answer than mine? Thanks! :)

This exercise is from the famous book The C Programming Language by Ritchie and Kerninghan

Solution

Your code is fine, but the explanation of why the operation works is not very rigorous.

A binary number can end with either 0 or 1.

If it ends with 1, subtracting 1 simply changes that to a 0. When you AND this with the original number, all the other bits stay the same, and 1 & 0 becomes 0. Since the last 1 bit was also the last bit, this removes the last 1 bit.

If it ends with 0, subtracting 1 has to "borrow" from the next higher bit. If that bit is also 0, it borrow from the next bit, and so on. All the low-order 0 bits get flipped to 1, and when the borrowing ends the 1 bit is flipped to 0. So if you start with 111000, the borrowing and flipping results in 110111. As you can see, all the low-order 0 bits turn to 1, and the lowest 1 bit turns to 0. When you AND these, the bits higher than the series of flipping and borrowing stay the same, while the lower bits all cancel out to 0. The final result is that the lowest 1 bit is converted to 0.