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.
Solution by Foowar
/* * 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. */ /* * in two's complement system subtraction is performed by adding the inverse * of the second operand * * in our case the second operand is 1, its inverse is (-1) which is represented * in two's complement by all bits set to 1 * * so (x-1) becomes like this * xxxxxxxx * 11111111 * + -------- * yyyyyyyy * * let's call the result `y` * if x starts with 0-bits (from the right) they will become 1 in y * the first (rightmost) 1-bit from x will become 0 and a carry is generated * now we have to add the rest bits of x to -1 (all 1-bits) plus a carry, * this operation is equivalent to adding the carry to -1 (all 1-bits) and adding * the result to the rest bits of x, notic that -1 + carry yelds 0 which when added * to the rest bits of x will leave those bits from x unchanged. * * summary: * if x starts with 0-bits (from the right) they will become 1 in y * the first (rightmost) 1-bit from x will become 0 in y * the rest bits from x will not change in y * * xxxx1000 * 11111111 * + -------- * y = xxxx0111 * x = xxxx1000 * & -------- * xxxx0000 = x & y * * when performing AND on x and y will get this result * if x starts with 0-bits they will not change, because (0 AND a) = 0 * the first 1-bit from x will become 0, because (0 AND 1) = 0 * the rest bits from x will not changed, because (a AND a) = a * * notic that the first (rightmost) 1-bit became 0 while all other bits are * left unchanged * * this might not be the best explanation but I did my best to explain it in * a "small" text format, it's easier to explain in video format * * tell me if I'm wrong at ayoubkhater at protonmail dot com */ int bitcount(unsigned x) { int count; for (count = 0; x != 0; ++count) x &= (x-1); return count; }
