commit - 896ce3ce10338082282f3c76bd06e6062be27087
commit + ece643e6eb497fb87bb09907b5f0410631a60213
blob - /dev/null
blob + 135020ac42f5883340a8f3f4b8aa26d099328303 (mode 644)
--- /dev/null
+++ 2-9-input
@@ -0,0 +1,8 @@
+0x7de65afe 22
+0xadd230f1 16
+0x0feb3112 15
+0xa0b0c118 10
+0x001992ba 11
+0x8ab30d3a 15
+0x37ab16de 19
+0x6de9bcd7 21
blob - /dev/null
blob + a45186167595bf261c7e50cd339fd54a22caa765 (mode 644)
--- /dev/null
+++ 2-9-output
@@ -0,0 +1,10 @@
+Type input line: x  expected
+                %x %d
+result = 22, expect = 22
+result = 16, expect = 16
+result = 15, expect = 15
+result = 10, expect = 10
+result = 11, expect = 11
+result = 15, expect = 15
+result = 19, expect = 19
+result = 21, expect = 21
blob - /dev/null
blob + d20904c85498e9a22b2705d415e2afae69e7a939 (mode 644)
--- /dev/null
+++ 2-9.c
@@ -0,0 +1,69 @@
+/* 2-9 In a two's complement number system, x &= (x-1) deletes the rightmost
+ * 1-bit in x. Explain why. Use this observation to write a faster version of
+ * bitcount.
+ *
+ * 0xab              1010 1011
+ * invert + 1        0101 0101
+ * 0xab = -(5*16+5) = -85
+ * 0xaa              1010 1010
+ * invert + 1        0101 0110
+ * 0xaa = -(5*16+6) = -86
+ *
+ * In a two's complement number system:
+ * 1) if the leading bit of x is 1 (ie, x is negative), x-1 subtracts from
+ * the lowest order bit
+ * 2) if the leading bit of x is 0 (ie, x is positive), x-1 subtracts from
+ * the lowest order bit
+ *
+ * Either way, the lowest order bit is subtracted from. The rightmost bit is
+ * replaced with 0, and the bits further to the right are all 1. x & x-1 takes
+ * the & of 1 (from the rightmost-bit in x) and 0 (from x-1), and 0 (from all
+ * remaining bits in x) and 1 (from all remaining bits in x-1). The result is
+ * always 0.
+ *
+ * Therefore, taking the bitwise and (&) of x &= (x-1) therefore always removes
+ * the rightmost bit.
+ */
+
+#include <stdio.h>
+
+int bitcount(unsigned x);
+
+int main() {
+
+	printf("Type input line: x  expected\n");
+	printf("                %%x %%d\n");
+	unsigned x = 0;
+	unsigned expect = 0;
+
+	while(scanf("%x %d\n", &x, &expect) == 2) {
+		printf("result = %d, expect = %d\n", bitcount(x), expect);
+	}
+	return 0;
+}
+
+/* bitcount: return number of 1 bits in x */
+int bitcount(unsigned x) {
+	int b;
+	for (b = 0; x; b++)
+		x &= (x-1);
+	return b;
+}
+/* 0x7de65afe 22
+ * 0x7de65afe 0111 1101 1110 0110 0101 1010 1111 1110
+ *
+ * 0xadd230f1 16
+ * 0xadd230f1 1010 1101 1101 0010 0011 0000 1111 0001
+ *
+ * 0x0feb3112 15
+ * 0x0feb3112 0000 1111 1110 1011 0011 0001 0001 0010
+ *
+ * 0xa0b0c118 10
+ * 0xa0b0c118 1010 0000 1011 0000 1100 0001 0001 1000
+ *
+ * 0x001992ba 11
+ * 0x001992ba 0000 0000 0001 1001 1001 0010 1011 1010
+ *
+ * The remainder come from my old KNR test cases
+ */
+