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