blob: 6ad608663029ad1ec28c7f398a1e7b4f3cee2c5f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <stdio.h>
/* The C Programming Language: 2nd Edition
*
* 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.
*
* Answer: Subtracting 1 from a number reverses the rightmost 1 bit and
* replaces all lower-order bits to 1. So for example:
*
* 110100 (52) minus 1 is
* 110011 (51)
*
* The & operator only masks bits off (makes them zero) if that bit in the
* second operand is also zero. That means...
*
* 110100 (52) &
* 110011 (51) is
* 110000
*
* Why? Because the 2nd operand (51) is only masking off two fields, the 3rd
* and 4th (which are zeros). The rightmost 1-bit in the 1st operand (52) is
* in that mask, so it goes poof.
*
* Oh, and here's the in-book version of bitcount():
*
* int bitcount(unsigned x) {
* int b;
* for (b = 0; x != 0; x >>= 1) {
* if (x & 01) {
* b++;
* }
* }
* return b;
* }
*/
unsigned bitcount(unsigned x) {
int count = 0;
while (x != 0) {
x &= (x - 1);
count++;
}
return count;
}
int main() {
int i;
unsigned test[4] = { 51, 65535, 256, 10834 };
for (i = 0; i < 4; i++) {
printf("%6u has %2d ones in its binary representation.\n", test[i], bitcount(test[i]));
}
return 0;
}
|
