Hi all,
I want to write a program to count number of bits set in a number.
The condition is we should not loop through each bit to find whether
its set or not.
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
/*
This is from the C-FAQ:
*/
#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
/*
This is from the C-FAQ:
*/
int rand_range(size_t n)
{
return (int) ((double) rand() / ((double) RAND_MAX + 1) * n);
}
/*
This is decidedly *not* from the C-FAQ (but in the tradition of the
great Peter Seebach, I present to you):
In the modus operandi of 'bogo-sort', I present the {*cough*,
drumroll..} 'nearly optimal' algorithm 'bogo-bitcount'.
This version is for one byte unsigned integers, but easily generalizes
to unsigned long long.
It may need a few minor _tweaks_ to work efficiently with integers of
64 bits or larger.
Sample run:
0 has 0 bits in it.
1 has 1 bits in it.
2 has 1 bits in it.
3 has 2 bits in it.
4 has 1 bits in it.
5 has 2 bits in it.
6 has 2 bits in it.
7 has 3 bits in it.
8 has 1 bits in it.
9 has 2 bits in it.
10 has 2 bits in it.
11 has 3 bits in it.
12 has 2 bits in it.
13 has 3 bits in it.
14 has 3 bits in it.
15 has 4 bits in it.
16 has 1 bits in it.
17 has 2 bits in it.
18 has 2 bits in it.
19 has 3 bits in it.
20 has 2 bits in it.
21 has 3 bits in it.
22 has 3 bits in it.
23 has 4 bits in it.
24 has 2 bits in it.
25 has 3 bits in it.
26 has 3 bits in it.
27 has 4 bits in it.
28 has 3 bits in it.
29 has 4 bits in it.
30 has 4 bits in it.
31 has 5 bits in it.
32 has 1 bits in it.
33 has 2 bits in it.
34 has 2 bits in it.
35 has 3 bits in it.
36 has 2 bits in it.
37 has 3 bits in it.
38 has 3 bits in it.
39 has 4 bits in it.
40 has 2 bits in it.
41 has 3 bits in it.
42 has 3 bits in it.
43 has 4 bits in it.
44 has 3 bits in it.
45 has 4 bits in it.
46 has 4 bits in it.
47 has 5 bits in it.
48 has 2 bits in it.
49 has 3 bits in it.
50 has 3 bits in it.
51 has 4 bits in it.
52 has 3 bits in it.
53 has 4 bits in it.
54 has 4 bits in it.
55 has 5 bits in it.
56 has 3 bits in it.
57 has 4 bits in it.
58 has 4 bits in it.
59 has 5 bits in it.
60 has 4 bits in it.
61 has 5 bits in it.
62 has 5 bits in it.
63 has 6 bits in it.
64 has 1 bits in it.
65 has 2 bits in it.
66 has 2 bits in it.
67 has 3 bits in it.
68 has 2 bits in it.
69 has 3 bits in it.
70 has 3 bits in it.
71 has 4 bits in it.
72 has 2 bits in it.
73 has 3 bits in it.
74 has 3 bits in it.
75 has 4 bits in it.
76 has 3 bits in it.
77 has 4 bits in it.
78 has 4 bits in it.
79 has 5 bits in it.
80 has 2 bits in it.
81 has 3 bits in it.
82 has 3 bits in it.
83 has 4 bits in it.
84 has 3 bits in it.
85 has 4 bits in it.
86 has 4 bits in it.
87 has 5 bits in it.
88 has 3 bits in it.
89 has 4 bits in it.
90 has 4 bits in it.
91 has 5 bits in it.
92 has 4 bits in it.
93 has 5 bits in it.
94 has 5 bits in it.
95 has 6 bits in it.
96 has 2 bits in it.
97 has 3 bits in it.
98 has 3 bits in it.
99 has 4 bits in it.
100 has 3 bits in it.
101 has 4 bits in it.
102 has 4 bits in it.
103 has 5 bits in it.
104 has 3 bits in it.
105 has 4 bits in it.
106 has 4 bits in it.
107 has 5 bits in it.
108 has 4 bits in it.
109 has 5 bits in it.
110 has 5 bits in it.
111 has 6 bits in it.
112 has 3 bits in it.
113 has 4 bits in it.
114 has 4 bits in it.
115 has 5 bits in it.
116 has 4 bits in it.
117 has 5 bits in it.
118 has 5 bits in it.
119 has 6 bits in it.
120 has 4 bits in it.
121 has 5 bits in it.
122 has 5 bits in it.
123 has 6 bits in it.
124 has 5 bits in it.
125 has 6 bits in it.
126 has 6 bits in it.
127 has 7 bits in it.
128 has 1 bits in it.
129 has 2 bits in it.
130 has 2 bits in it.
131 has 3 bits in it.
132 has 2 bits in it.
133 has 3 bits in it.
134 has 3 bits in it.
135 has 4 bits in it.
136 has 2 bits in it.
137 has 3 bits in it.
138 has 3 bits in it.
139 has 4 bits in it.
140 has 3 bits in it.
141 has 4 bits in it.
142 has 4 bits in it.
143 has 5 bits in it.
144 has 2 bits in it.
145 has 3 bits in it.
146 has 3 bits in it.
147 has 4 bits in it.
148 has 3 bits in it.
149 has 4 bits in it.
150 has 4 bits in it.
151 has 5 bits in it.
152 has 3 bits in it.
153 has 4 bits in it.
154 has 4 bits in it.
155 has 5 bits in it.
156 has 4 bits in it.
157 has 5 bits in it.
158 has 5 bits in it.
159 has 6 bits in it.
160 has 2 bits in it.
161 has 3 bits in it.
162 has 3 bits in it.
163 has 4 bits in it.
164 has 3 bits in it.
165 has 4 bits in it.
166 has 4 bits in it.
167 has 5 bits in it.
168 has 3 bits in it.
169 has 4 bits in it.
170 has 4 bits in it.
171 has 5 bits in it.
172 has 4 bits in it.
173 has 5 bits in it.
174 has 5 bits in it.
175 has 6 bits in it.
176 has 3 bits in it.
177 has 4 bits in it.
178 has 4 bits in it.
179 has 5 bits in it.
180 has 4 bits in it.
181 has 5 bits in it.
182 has 5 bits in it.
183 has 6 bits in it.
184 has 4 bits in it.
185 has 5 bits in it.
186 has 5 bits in it.
187 has 6 bits in it.
188 has 5 bits in it.
189 has 6 bits in it.
190 has 6 bits in it.
191 has 7 bits in it.
192 has 2 bits in it.
193 has 3 bits in it.
194 has 3 bits in it.
195 has 4 bits in it.
196 has 3 bits in it.
197 has 4 bits in it.
198 has 4 bits in it.
199 has 5 bits in it.
200 has 3 bits in it.
201 has 4 bits in it.
202 has 4 bits in it.
203 has 5 bits in it.
204 has 4 bits in it.
205 has 5 bits in it.
206 has 5 bits in it.
207 has 6 bits in it.
208 has 3 bits in it.
209 has 4 bits in it.
210 has 4 bits in it.
211 has 5 bits in it.
212 has 4 bits in it.
213 has 5 bits in it.
214 has 5 bits in it.
215 has 6 bits in it.
216 has 4 bits in it.
217 has 5 bits in it.
218 has 5 bits in it.
219 has 6 bits in it.
220 has 5 bits in it.
221 has 6 bits in it.
222 has 6 bits in it.
223 has 7 bits in it.
224 has 3 bits in it.
225 has 4 bits in it.
226 has 4 bits in it.
227 has 5 bits in it.
228 has 4 bits in it.
229 has 5 bits in it.
230 has 5 bits in it.
231 has 6 bits in it.
232 has 4 bits in it.
233 has 5 bits in it.
234 has 5 bits in it.
235 has 6 bits in it.
236 has 5 bits in it.
237 has 6 bits in it.
238 has 6 bits in it.
239 has 7 bits in it.
240 has 4 bits in it.
241 has 5 bits in it.
242 has 5 bits in it.
243 has 6 bits in it.
244 has 5 bits in it.
245 has 6 bits in it.
246 has 6 bits in it.
247 has 7 bits in it.
248 has 5 bits in it.
249 has 6 bits in it.
250 has 6 bits in it.
251 has 7 bits in it.
252 has 6 bits in it.
253 has 7 bits in it.
254 has 7 bits in it.
255 has 8 bits in it.
Enjoy this marvel of efficiency.
*/
int bitcount_the_hard_way(unsigned char value)
{
unsigned char test_mask = 0;
unsigned bitcount = 0;
/* choose a random bit: */
int bit;
if (!value)
return 0;
morebits:
if (test_mask == 0xff) {
test_mask = 0; /* this set of passes did not work, try
* again... */
bitcount = 0;
}
bit = rand_range(CHAR_BIT);
if (BITTEST(&test_mask, bit))
goto morebits; /* If the bit is already set, choose another
* one... */
BITSET(&test_mask, bit);
bitcount++;
if ((test_mask ^ value) == 0)
return bitcount;
goto morebits;
}
int main(void)
{
unsigned index;
int count;
for (index = 0; index <= UCHAR_MAX; index++) {
count = bitcount_the_hard_way(index);
printf("%u has %d bits in it.\n", index, count);
}
return 0;
}- Hide quoted text -
- Show quoted text -