From e41bafc5885aac630b6d19893e9c80cc334497c2 Mon Sep 17 00:00:00 2001 From: Adam Carpenter Date: Tue, 23 Jul 2019 12:08:40 -0400 Subject: Finished 2-9 --- ch2/2-9.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 ch2/2-9.c 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 + +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; +} + -- cgit v1.2.3