summaryrefslogtreecommitdiff
path: root/ch2
diff options
context:
space:
mode:
authorAdam Carpenter <gitlab@53hor.net>2019-07-23 12:08:40 -0400
committerAdam Carpenter <gitlab@53hor.net>2019-07-23 12:08:40 -0400
commite41bafc5885aac630b6d19893e9c80cc334497c2 (patch)
tree080a615268a8561c3ac5df6386ba3c4ab079a406 /ch2
parent8fcf25523124008a56515dc0b3de0a32f3283e18 (diff)
downloadlearning-c-e41bafc5885aac630b6d19893e9c80cc334497c2.tar.xz
learning-c-e41bafc5885aac630b6d19893e9c80cc334497c2.zip
Finished 2-9
Diffstat (limited to 'ch2')
-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;
+}
+