1 // This has the programs for computing the number of 1-bits
2 // in a word, or byte, etc.
3 // Max line length is 57, to fit in hacker.book.
4 #include <stdio.h>
5 #include <stdlib.h> //To define "exit", req'd by XLC.
6 #include <ctime>
7
rotatel(unsigned x,int n)8 unsigned rotatel(unsigned x, int n)
9 {
10 if ((unsigned)n > 63) {printf("rotatel, n out of range.\n"); exit(1);}
11 return (x << n) | (x >> (32 - n));
12 }
13
pop0(unsigned x)14 int pop0(unsigned x)
15 {
16 x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
17 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
18 x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
19 x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
20 x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
21 return x;
22 }
23
pop1(unsigned x)24 int pop1(unsigned x)
25 {
26 x = x - ((x >> 1) & 0x55555555);
27 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
28 x = (x + (x >> 4)) & 0x0F0F0F0F;
29 x = x + (x >> 8);
30 x = x + (x >> 16);
31 return x & 0x0000003F;
32 }
33 /* Note: an alternative to the last three executable lines above is:
34 return x*0x01010101 >> 24;
35 if your machine has a fast multiplier (suggested by Jari Kirma). */
36
pop2(unsigned x)37 int pop2(unsigned x)
38 {
39 unsigned n;
40
41 n = (x >> 1) & 033333333333; // Count bits in
42 x = x - n; // each 3-bit
43 n = (n >> 1) & 033333333333; // field.
44 x = x - n;
45 x = (x + (x >> 3)) & 030707070707; // 6-bit sums.
46 return x%63; // Add 6-bit sums.
47 }
48
49 /* An alternative to the "return" statement above is:
50 return ((x * 0404040404) >> 26) + // Add 6-bit sums.
51 (x >> 30);
52 which runs faster on most machines (suggested by Norbert Juffa). */
53
pop3(unsigned x)54 int pop3(unsigned x)
55 {
56 unsigned n;
57
58 n = (x >> 1) & 0x77777777; // Count bits in
59 x = x - n; // each 4-bit
60 n = (n >> 1) & 0x77777777; // field.
61 x = x - n;
62 n = (n >> 1) & 0x77777777;
63 x = x - n;
64 x = (x + (x >> 4)) & 0x0F0F0F0F; // Get byte sums.
65 x = x*0x01010101; // Add the bytes.
66 return x >> 24;
67 }
68
pop4(unsigned x)69 int pop4(unsigned x)
70 {
71 int n;
72
73 n = 0;
74 while (x != 0) {
75 n = n + 1;
76 x = x & (x - 1);
77 }
78 return n;
79 }
80
pop5(unsigned x)81 int pop5(unsigned x)
82 {
83 int i, sum;
84
85 // Rotate and sum method // Shift right & subtract
86
87 sum = x; // sum = x;
88 for (i = 1; i <= 31; i++) { // while (x != 0) {
89 x = rotatel(x, 1); // x = x >> 1;
90 sum = sum + x; // sum = sum - x;
91 } // }
92 return -sum; // return sum;
93 }
94
pop5a(unsigned x)95 int pop5a(unsigned x)
96 {
97 int sum;
98
99 // Shift right & subtract
100
101 sum = x;
102 while (x != 0) {
103 x = x >> 1;
104 sum = sum - x;
105 }
106 return sum;
107 }
108
pop6(unsigned x)109 int pop6(unsigned x)
110 { // Table lookup.
111 static char table[256] = {
112 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
113 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
114 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
115 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
116
117 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
118 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
119 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
120 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
121
122 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
123 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
124 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
125 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
126
127 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
128 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
129 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
130 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
131
132 return table[x & 0xFF] +
133 table[(x >> 8) & 0xFF] +
134 table[(x >> 16) & 0xFF] +
135 table[(x >> 24)];
136 }
137
138 // The following works only for 8-bit quantities.
pop7(unsigned x)139 int pop7(unsigned x)
140 {
141 x = x*0x08040201; // Make 4 copies.
142 x = x >> 3; // So next step hits proper bits.
143 x = x & 0x11111111; // Every 4th bit.
144 x = x*0x11111111; // Sum the digits (each 0 or 1).
145 x = x >> 28; // Position the result.
146 return x;
147 }
148
149 // The following works only for 7-bit quantities.
pop8(unsigned x)150 int pop8(unsigned x)
151 {
152 x = x*0x02040810; // Make 4 copies, left-adjusted.
153 x = x & 0x11111111; // Every 4th bit.
154 x = x*0x11111111; // Sum the digits (each 0 or 1).
155 x = x >> 28; // Position the result.
156 return x;
157 }
158
159 // The following works only for 15-bit quantities.
pop9(unsigned x)160 int pop9(unsigned x)
161 {
162 unsigned long long y;
163 y = x * 0x0002000400080010ULL;
164 y = y & 0x1111111111111111ULL;
165 y = y * 0x1111111111111111ULL;
166 y = y >> 60;
167 return y;
168 }
169
170 int errors;
error(int x,int y)171 void error(int x, int y)
172 {
173 errors = errors + 1;
174 printf("Error for x = %08x, got %08x\n", x, y);
175 }
176
main()177 int main()
178 {
179 # ifdef NDEBUG
180
181 int i, n;
182 static unsigned test[] = {0,0, 1,1, 2,1, 3,2, 4,1, 5,2, 6,2, 7,3,
183 8,1, 9,2, 10,2, 11,3, 12,2, 13,3, 14,3, 15,4, 16,1, 17,2,
184 0x3F,6, 0x40,1, 0x41,2, 0x7f,7, 0x80,1, 0x81,2, 0xfe,7, 0xff,8,
185 0x4000,1, 0x4001,2, 0x7000,3, 0x7fff,15,
186 0x55555555,16, 0xAAAAAAAA, 16, 0xFF000000,8, 0xC0C0C0C0,8,
187 0x0FFFFFF0,24, 0x80000000,1, 0xFFFFFFFF,32};
188
189 std::size_t const Count = 1000000;
190
191 n = sizeof(test)/4;
192
193 std::clock_t TimestampBeg = 0;
194 std::clock_t TimestampEnd = 0;
195
196 TimestampBeg = std::clock();
197 for (std::size_t k = 0; k < Count; ++k)
198 for (i = 0; i < n; i += 2) {
199 if (pop0(test[i]) != test[i+1]) error(test[i], pop0(test[i]));}
200 TimestampEnd = std::clock();
201
202 printf("pop0: %ld clocks\n", TimestampEnd - TimestampBeg);
203
204 TimestampBeg = std::clock();
205 for (std::size_t k = 0; k < Count; ++k)
206 for (i = 0; i < n; i += 2) {
207 if (pop1(test[i]) != test[i+1]) error(test[i], pop1(test[i]));}
208 TimestampEnd = std::clock();
209
210 printf("pop1: %ld clocks\n", TimestampEnd - TimestampBeg);
211
212 TimestampBeg = std::clock();
213 for (std::size_t k = 0; k < Count; ++k)
214 for (i = 0; i < n; i += 2) {
215 if (pop2(test[i]) != test[i+1]) error(test[i], pop2(test[i]));}
216 TimestampEnd = std::clock();
217
218 printf("pop2: %ld clocks\n", TimestampEnd - TimestampBeg);
219
220 TimestampBeg = std::clock();
221 for (std::size_t k = 0; k < Count; ++k)
222 for (i = 0; i < n; i += 2) {
223 if (pop3(test[i]) != test[i+1]) error(test[i], pop3(test[i]));}
224 TimestampEnd = std::clock();
225
226 printf("pop3: %ld clocks\n", TimestampEnd - TimestampBeg);
227
228 TimestampBeg = std::clock();
229 for (std::size_t k = 0; k < Count; ++k)
230 for (i = 0; i < n; i += 2) {
231 if (pop4(test[i]) != test[i+1]) error(test[i], pop4(test[i]));}
232 TimestampEnd = std::clock();
233
234 printf("pop4: %ld clocks\n", TimestampEnd - TimestampBeg);
235
236 TimestampBeg = std::clock();
237 for (std::size_t k = 0; k < Count; ++k)
238 for (i = 0; i < n; i += 2) {
239 if (pop5(test[i]) != test[i+1]) error(test[i], pop5(test[i]));}
240 TimestampEnd = std::clock();
241
242 printf("pop5: %ld clocks\n", TimestampEnd - TimestampBeg);
243
244 TimestampBeg = std::clock();
245 for (std::size_t k = 0; k < Count; ++k)
246 for (i = 0; i < n; i += 2) {
247 if (pop5a(test[i]) != test[i+1]) error(test[i], pop5a(test[i]));}
248 TimestampEnd = std::clock();
249
250 printf("pop5a: %ld clocks\n", TimestampEnd - TimestampBeg);
251
252 TimestampBeg = std::clock();
253 for (std::size_t k = 0; k < Count; ++k)
254 for (i = 0; i < n; i += 2) {
255 if (pop6(test[i]) != test[i+1]) error(test[i], pop6(test[i]));}
256 TimestampEnd = std::clock();
257
258 printf("pop6: %ld clocks\n", TimestampEnd - TimestampBeg);
259
260 TimestampBeg = std::clock();
261 for (std::size_t k = 0; k < Count; ++k)
262 for (i = 0; i < n; i += 2) {
263 if ((test[i] & 0xffffff00) == 0)
264 if (pop7(test[i]) != test[i+1]) error(test[i], pop7(test[i]));}
265 TimestampEnd = std::clock();
266
267 printf("pop7: %ld clocks\n", TimestampEnd - TimestampBeg);
268
269 TimestampBeg = std::clock();
270 for (std::size_t k = 0; k < Count; ++k)
271 for (i = 0; i < n; i += 2) {
272 if ((test[i] & 0xffffff80) == 0)
273 if (pop8(test[i]) != test[i+1]) error(test[i], pop8(test[i]));}
274 TimestampEnd = std::clock();
275
276 printf("pop8: %ld clocks\n", TimestampEnd - TimestampBeg);
277
278 TimestampBeg = std::clock();
279 for (std::size_t k = 0; k < Count; ++k)
280 for (i = 0; i < n; i += 2) {
281 if ((test[i] & 0xffff8000) == 0)
282 if (pop9(test[i]) != test[i+1]) error(test[i], pop9(test[i]));}
283 TimestampEnd = std::clock();
284
285 printf("pop9: %ld clocks\n", TimestampEnd - TimestampBeg);
286
287 if (errors == 0)
288 printf("Passed all %d cases.\n", sizeof(test)/8);
289
290 # endif//NDEBUG
291 }
292