Exercise 2-9

First of all, we realize that x &= (x-1) is analogous to x = x & (x-1). Let us try plugging in some examples. If x is equal to 1111_binary, the expression becomes 1111binary & 1110binary, which deletes the rightmost bit. If x is equal to 1110_binary, the expression becomes 1110binary & 1101binary, which results in 1100_binary. If x is equal to 1000_binary, the expression becomes 1000binary & 0111binary which results in 0000_binary. From this, we notice a pattern: when we subtract one, the rightmost 1-bit changes to a zero, and any subsequent bits change to ones. When the AND operator is used on the two strings, the result is x with its rightmost 1-bit changed to a zero. Note that this only works when x is positive.

Using this information, we can implement a more elegant version of bitcount by deleting the rightmost 1-bit every iteration instead and running the loop until x equals zero.

    /* bitcount:  count 1 bits in x */
    int bitcount(unsigned x)
    {
        int b;
    
        for (b = 0; x != 0; x >>= 1)
        for (b = 0; x != 0; x &= (x-1))
            if (x & 01)
            b++;
        return b;
    }