1 /*
2  * 2-9. In a two's complement number system, x &= (x-1) deletes the
3  * rightmost 1-bit in x. Explain why. Use this observation to write a
4  * faster version of bitcount.
5  */
6 
7 /*
8 When you subtract 1 from x, the new number will differ by
9 x by 2 bits -- the rightmost 1-bit in x, and the next bit.
10 
11 When you bitwise and the two, both become 0. This deletes
12 the rightmost 1-bit in x.
13 
14 Illustrated:
15 x:        1010 1010
16 x-1:      1010 1001
17 x&=(x-1): 1010 1000
18 */
19 
20 #include <stdio.h>
21 
22 int bitcount(unsigned x);
23 unsigned setbits(unsigned x, int p, int n, unsigned y);
24 unsigned getbits(unsigned x, int p, int n);
25 unsigned invert(unsigned x, int p, int n);
26 unsigned rightrot(unsigned x, int n);
27 
28 main()
29 {
30 	printf("%u: %d %d\n", 0x8ab30d3a, bitcount(0x8ab30d3a), 15);
31 	printf("%u: %d %d\n", 0x37ab16de, bitcount(0x37ab16de), 19);
32 	printf("%u: %d %d\n", 0x6de9bcd7, bitcount(0x6de9bcd7), 21);
33 }
34 
35 /*
36 8    a    b    3    0    d    3    a
37 1000 1010 1011 0011 0000 1101 0011 1010
38 
39 3    7    a    b    1    6    d    e
40 0011 0111 1010 1011 0001 0110 1101 1110
41 
42 6    d    e    9    b    c    d    7
43 0110 1101 1110 1001 1011 1100 1101 0111
44  */
45 int bitcount(unsigned x) {
46 	int i;
47 	for (i = 0; x > 0; x &= (x-1), ++i);
48 	return i;
49 }
50 unsigned rightrot(unsigned x, int n) {
51 	return (x >> n) | setbits(0,31,n,x);
52 }
53 
54 unsigned invert(unsigned x, int p, int n) {
55 	return setbits(x, p, n, ~getbits(x, p, n));
56 }
57 
58 unsigned setbits(unsigned x, int p, int n, unsigned y)
59 {
60 	return ((x >> (p+1)) << (p+1)) | (getbits(y, n-1, n) << (p-n+1)) | (x & ~(~0 << (p-n+1)));
61 }
62 
63 unsigned getbits(unsigned x, int p, int n)
64 {
65 	return (x >> (p+1-n)) & ~(~0 << n);
66 }