The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 2.09 on page 51

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 .

Solution by Vidhan Gupta

/* 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. */

#include <stdio.h>

// Function prototype for bitcount
int bitcount(int x);
// Function prototype to print binary of a given integer
void print_binary(unsigned x);

int main()
{
    int test = 102;
    print_binary(test);
    printf("%d\n",bitcount(test));
}

// Function that counts the number of 1-bit in the given integer
int bitcount(int x)
{
    int i;
    for (i = 0; x != 0; x &= (x-1))
        i++;
    return i;
}

// Function that prints binary of a given integer
void print_binary(unsigned x)
{
    int n = sizeof(x) * 8;
    for (int i = n-1; i >= 0; i--)
    {
        int curr_bit = (x >> i) & 1;
        printf("%d", curr_bit);
    }
    printf("\n");
}

OUTPUT:
00000000000000000000000001100110
4

Solution by Gregory Pietsch

bitcount is written on p.50 as 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;
}

Answer:

If x is odd, then (x-1) has the same bit representation as x except that the rightmost 1-bit is now a 0. In this case, (x & (x-1)) == (x-1).

If x is even, then the representation of (x-1) has the rightmost zeros of x becoming ones and the rightmost one becoming a zero. Anding the two clears the rightmost 1-bit in x and all the rightmost 1-bits from (x-1).

Here's the new version of bitcount:

/* bitcount:  count 1 bits in x */
int bitcount(unsigned x)
{
    int b;

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

Solution by Luke Panayi

My slightly varied solution that hits on the same point

Gregory likely gives a better answer to the question of 'why'.

#include <stdio.h>

/* 'Explain  why x&=(x-1) deletes the rightmost 1-bit in x':
Given any byte, subtracting 1 will flip the rightmost 1-bit. It will also likely change
other bits, but when &'ed with the original byte, these changes are reverted, but
the rightmost 1-bit being flipped will always result in the rightmost 1-bit of the newly 
asigned byte being 0.
*/



//Supposedly faster, although timing ./a.out using both functions both return 0.001s!

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

	return b;
}

int main()	{
	printf("%d\n", bitcount(25));
	return 0;
}

Solution by Cromagnon

This is an answer with example
This operation deletes the rightmost 1-bit in x because x-1 flips every bit from (and including) the rightmost 1-bit of x until its last bit. Then, performing a bitwise AND operation between x and x-1 zeroes from x every bit that was flipped in x-1. That is, this operation zeroes from x the rightmost 1-bit.

For example, consider x as a unsigned char variable defined to have the value 01110101. Thus, x has five 1-bits. Applying the operation x &= x-1 five times over x deletes all of its five 1-bits. The first column contains the expression; the second one shows the value of the expression in hexadecimal constant notation; the third column shows the same value, but in binary; and the last column comments what is happening.

x            0X75     01110101     x has five 1-bits
x-1          0X74     01110100     flipping the last bit
x &= x-1     0X74     01110100     zeroing the last bit

x            0X74     01110100     x now has four 1-bits
x-1          0X73     01110011     flipping the three last bits
x &= x-1     0X70     01110000     zeroing the three last bits

x            0X70     01110000     x now has three 1-bits
x-1          0X6F     01101111     flipping the five last bits
x &= x-1     0X60     01100000     zeroing the five last bits

x            0X60     01100000     x now has two 1-bits
x-1          0X5F     01011111     flipping the six last bits
x &= x-1     0X40     01000000     zeroing the six last bits

x            0X40     01000000     x now has one 1-bit
x-1          0X3F     00111111     flipping the seven last bits
x &= x-1     0X00     00000000     zeroing the seven last bits

x            0X00     00000000     x now has zero 1-bit

Solution by Miguel Degrossoli

I know there are more elegant solutions above. I just wanted to share mine.

/* 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". */

/* Let's suppose (char)x = 86. The expression x &= (x - 1) is the same as 
 * x = x & (x - 1). Then:
 *  01010110	<- this is x (86)
 * +11111111	<- this is -1 (two's complement of 1).
 *  01010101	<- this is the result of x - 1 (or, better, x + (-1)) (85)
 * &01010110 	<- this is x (86) again, for the & operation
 *  01010100	<- this is x & (x - 1), i.e., the new value of x. (84)
 *
 * Notice that the last 1 has been deleted. When you subtract 1 from a number
 * (or, in this case, adds -1), you are always going to flip the last 1 from
 * that number (i.e., it becomes 0) and the remaining rightmost bits all become
 * 1 - the oposite of the original number. When you perform an & operation
 * between that number and the result, from the last 1 on, the result will
 * always be 0. Notice also that x will never assume an odd value after the
 * first time you run the operation, because the rightmost bits will always
 * assume a value of 0 (even if you start with an even number) and the only way
 * to have an odd number is by setting the rightmost bit to 1.
 *
 * It means that the amount of 1 digits in the number equals the amount of times
 * you have to run the operation until x == 0. And it is faster because it
 * doesn't need to examine every single bit of the number. */

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

#define MAXLEN 10	/* maximum length of the input number */

unsigned getuint();
unsigned bitcount(unsigned x);

int main() {

	unsigned x;

	printf("Type any positive number: ");
	x = getuint();

	printf("The number %u has %u ones.\n", x, bitcount(x));
	exit(0);
}

unsigned getuint() {

	int i, c;
	char s[MAXLEN + 1];
	unsigned uint;

	uint = i = 0;
	while ((c = getchar()) != EOF && c != '\n' && i < MAXLEN)
		if (isdigit(c))
			s[i++] = c;
		else {
			printf("Error: \"%c\" is not a valid number!\n", c);
			exit(1);
		}
	s[i] = '\0';

	for (i = 0; s[i] != '\0'; i++)
		uint = uint * 10 + (s[i] - '0');

	return uint;
}

unsigned bitcount(unsigned x) {

	int i = 0;
	
	if (x == 0)
		return 0;

	while ((x &= (x-1)) > 0)
		++i;

	return ++i;
}

Results:

miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-9
Type any positive number: 1987
The number 1987 has 7 ones.
miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-9
Type any positive number: 1
The number 1 has 1 ones.
miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-9
Type any positive number: 15061987
The number 15061987 has 15 ones.
miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-9
Type any positive number: 2
The number 2 has 1 ones.
miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-9
Type any positive number: 4   
The number 4 has 1 ones.
miguel@Miguel-Notebook:~/Desenvolvimento/C$ ./exercise_2-9
Type any positive number: 8
The number 8 has 1 ones.