Finished 2-9

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;
+}
+