```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 ``` ```/* yet more bit hacks */ #include typedef int bool; #define true 1 #define false 0 #define CHAR_BIT 8 int main(void) { /* 1) count parity */ unsigned int v = 847362849; bool parity = false; while (v) { parity = !parity; v = v & (v - 1); } printf("%d\n", parity); static const bool ParityTable256[256] = { # define P2(n) n, n^1, n^1, n # define P4(n) P2(n), P2(n^1), P2(n^1), P2(n) # define P6(n) P4(n), P4(n^1), P4(n^1), P4(n) P6(0), P6(1), P6(1), P6(0) }; v = 847362849; v ^= v >> 16; v ^= v >> 8; parity = ParityTable256[v & 0xff]; printf("%d\n", parity); v = 847362849; unsigned char * p = (unsigned char *) &v; parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]]; printf("%d\n", parity); unsigned char b = 73; // byte value to compute the parity of parity = (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1; printf("%d\n", parity); printf("\n"); /* 2) reversing bits */ v = 847362849; // input bits to be reversed unsigned int r = v; // r will be reversed bits of v; first get LSB of v int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end for (v >>= 1; v; v >>= 1) { r <<= 1; r |= v & 1; s--; } r <<= s; // shift when v's highest bits are zero printf("%d\n", r); static const unsigned char BitReverseTable256[256] = { # define R2(n) n, n + 2*64, n + 1*64, n + 3*64 # define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) # define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 ) R6(0), R6(2), R6(1), R6(3) }; v = 847362849; // reverse 32-bit value, 8 bits at time unsigned int c; // c will get v reversed c = (BitReverseTable256[v & 0xff] << 24) | (BitReverseTable256[(v >> 8) & 0xff] << 16) | (BitReverseTable256[(v >> 16) & 0xff] << 8) | (BitReverseTable256[(v >> 24) & 0xff]); printf("%d\n", c); p = (unsigned char *) &v; unsigned char * q = (unsigned char *) &c; q[3] = BitReverseTable256[p[0]]; q[2] = BitReverseTable256[p[1]]; q[1] = BitReverseTable256[p[2]]; q[0] = BitReverseTable256[p[3]]; printf("%d\n", c); b = 73; // reverse this (8-bit) byte b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023; printf("%d\n", b); printf("\n"); /* 3) integer logarithm base-2 */ v = 847362849; // 32-bit word to find the log base 2 of r = 0; // r will be lg(v) while (v >>= 1) { r++; } printf("%d\n", r); static const char LogTable256[256] = { #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) }; v = 847362849; // 32-bit word to find the log of register unsigned int t, tt; // temporaries if (tt = v >> 16) { r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else { r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } printf("%d\n", r); if (tt = v >> 24) { r = 24 + LogTable256[tt]; } else if (tt = v >> 16) { r = 16 + LogTable256[tt]; } else if (tt = v >> 8) { r = 8 + LogTable256[tt]; } else { r = LogTable256[v]; } printf("%d\n", r); return 0; } ```
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 ``` ```1 1 1 1 -2065858228 -2065858228 -2065858228 146 29 29 29 ```