summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ch2/2-9.c40
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;
+}
+