diff options
Diffstat (limited to 'ch2')
-rw-r--r-- | ch2/2-9.c | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/ch2/2-9.c b/ch2/2-9.c new file mode 100644 index 0000000..5ab3241 --- /dev/null +++ b/ch2/2-9.c @@ -0,0 +1,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; +} + |