ch2/2-09.c


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

#include <stdio.h>

int bitcount_original(unsigned x);
int bitcount(unsigned x);

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

/*
 * A binary subtraction operation will toggle the least-significant bits
 * required for the subtraction. The `&` operation between two opposing bits
 * will always result in 0. This is why using `x &= (x - 1)` will always delete
 * the rightmost 1-bit in x; the least-significant 1-bit and all 1-bits
 * generated from the subtraction operation will be zeroed out.
 *
 * This observation makes this implementation more efficient than
 * `bitcount_original` simply because it requires fewer operations.
 */
int bitcount(unsigned x) {
    int b;
    
    for (b = 0; x > 0; b++)
        x &= (x - 1);

    return b;
}

int bitcount_original(unsigned x) {
    int b;

    for (b = 0; x != 0; x >>= 1)
        if (x & 01)
            b++;

    return b;
}