Упражнение 2.9.

Применительно к числам, в представлении которых использован дополнительный код, выражение х &= (х-1) уничтожает самую правую 1 в х. Объясните, почему. Используйте это наблюдение при написании более быстрого варианта функции bitcount.

Выражения x и x-1 всегда отличаются младшим битом, поэтому операция побитового И всегда обнулит младший бит.

Например,
101(10) = 0110 0101(2)
100(10) = 0110 0100(2)

0110 0101
&
0110 0100
---------
0110 0100

#include <stdio.h>

int bitcount(unsigned x);

int main(void)

{

    printf("%u\n", bitcount(100));

    return 0;

}

/* bitcount: подсчет единиц в х */

int bitcount(unsigned x)

{

int b;

for (b = 0; x != 0; x &= (x - 1))

b++;

return b;

}