Count number of bits set in a number

[Mack]

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.

Thanks in advance,

-Mukesh

[Joachim Schmitz]

"Mack" <Ma**********@g mail.comschrieb im Newsbeitrag
news:11******** **************@ d55g2000hsg.goo glegroups.com.. .

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.

You'd better do your homework yourself.

Bye, Jojo

[Eric Sosman]

Mack wrote:

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.

Start by writing down a few numbers along with
their bit counts, using any method you like to count
the bits:

Number Bits
0 0
1 1
2 1
3 2

Now find the straight line that gives the best
least-squares fit to the observed data (any spreadsheet
will do this for you if you can't recall the math).
Take the fitted coefficients and write your function:

double bit_count(int number) {
return 0.6 * number + 0.1;
}

Use more data points, if you like, to get a statistically
more accurate fit. There, that wasn't so hard, was it?

--
Eric Sosman
es*****@ieee-dot-org.invalid

[karthikbalaguru]

On Sep 27, 5:48 pm, Eric Sosman <[e-mail] e:

Mack wrote:

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.

Start by writing down a few numbers along with
their bit counts, using any method you like to count
the bits:

Number Bits
0 0
1 1
2 1
3 2

Now find the straight line that gives the best
least-squares fit to the observed data (any spreadsheet
will do this for you if you can't recall the math).
Take the fitted coefficients and write your function:

double bit_count(int number) {
return 0.6 * number + 0.1;
}

Use more data points, if you like, to get a statistically
more accurate fit. There, that wasn't so hard, was it?

--
Eric Sosman
[e-mail]

A rough idea will be like this... Just a very very high level idea.
Not the exact algorithm for you.

Take the number in which you want to count the bits set ,
And the first bit, check if it is set, add it to
your bitset counter if it is set. Move to next bit
And the next bit, check if it is set , add it to
your bitset counter if it is set. Move to next bit.

Implement with bitwise operators (lshift or rshift , & ) and have fun.

Karthik Balaguru

[Mark Bluemel]

karthikbalaguru wrote:

On Sep 27, 5:48 pm, Eric Sosman <[e-mail] e:

>Mack wrote:

>>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.

[Snip]

A rough idea will be like this... Just a very very high level idea.
Not the exact algorithm for you.

Take the number in which you want to count the bits set ,
And the first bit, check if it is set, add it to
your bitset counter if it is set. Move to next bit
And the next bit, check if it is set , add it to
your bitset counter if it is set. Move to next bit.

What part of "we should not loop through each bit" didn't you understand?

[karthikbalaguru]

On Sep 27, 6:06 pm, Mark Bluemel <mark_blue...@p obox.comwrote:

karthikbalaguru wrote:

On Sep 27, 5:48 pm, Eric Sosman <[e-mail] e:

Mack wrote:
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.

[Snip]

A rough idea will be like this... Just a very very high level idea.
Not the exact algorithm for you.

Take the number in which you want to count the bits set ,
And the first bit, check if it is set, add it to
your bitset counter if it is set. Move to next bit
And the next bit, check if it is set , add it to
your bitset counter if it is set. Move to next bit.

What part of "we should not loop through each bit" didn't you understand?- Hide quoted text -

- Show quoted text -

Then, do not shift the bits in the number that you are checking for
the bits set.
Move the other number that you are 'And'ing with.

Something like below !
This is a rough idea/steps, it will not compile or give the exact
output that you desire.

a = 0x1100;
b = 0x0001;
if(a & b) bitsetcount++;
if(a & b<<1) bitsetcount++;
if(a & b<<2) bitsetcount++;
if(a & b<<3) bitsetcount++;

Karthik Balaguru

[Mark Bluemel]

Mack wrote:

Hi all,
I want to write a program to count number of bits set in a number.

I think you meant to say "my homework is to write ...".

The condition is we should not loop through each bit to find whether
its set or not.

We're not going to write it for you, but a few moments with Google for
"bit manipulation tricks" or some similar search term would be valid
research I'd say...

I found a wonderfully elegant solution in a matter of moments...

[user923005]

On Sep 27, 12:49 am, Mack <Mack.Chau...@g mail.comwrote:

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_ha rd_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_ma sk, 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_ha rd_way(index);
printf("%u has %d bits in it.\n", index, count);
}
return 0;
}

[pete]

Mark Bluemel wrote:

>
karthikbalaguru wrote:

On Sep 27, 5:48 pm, Eric Sosman <[e-mail] e:

Mack wrote:
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.

[Snip]

A rough idea will be like this... Just a very very high level idea.
Not the exact algorithm for you.

Take the number in which you want to count the bits set ,
And the first bit, check if it is set, add it to
your bitset counter if it is set. Move to next bit
And the next bit, check if it is set , add it to
your bitset counter if it is set. Move to next bit.

What part of "we should not loop through each bit"
didn't you understand?

I had trouble understanding it.
Is it allowable to only loop through the set bits
if you don't loop through the unset bits?

unsigned bit_count(unsig ned n)
{
unsigned count;

for (count = 0; n != 0; n &= n - 1) {
++count;
}
return count;
}

--
pete

[user923005]

On Sep 27, 3:44 pm, pete <pfil...@mindsp ring.comwrote:

Mark Bluemel wrote:

karthikbalaguru wrote:

On Sep 27, 5:48 pm, Eric Sosman <[e-mail] e:
>Mack wrote:
>>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.

[Snip]

A rough idea will be like this... Just a very very high level idea.
Not the exact algorithm for you.

Take the number in which you want to count the bits set ,
And the first bit, check if it is set, add it to
your bitset counter if it is set. Move to next bit
And the next bit, check if it is set , add it to
your bitset counter if it is set. Move to next bit.

What part of "we should not loop through each bit"
didn't you understand?

I had trouble understanding it.
Is it allowable to only loop through the set bits
if you don't loop through the unset bits?

unsigned bit_count(unsig ned n)
{
unsigned count;

for (count = 0; n != 0; n &= n - 1) {
++count;
}
return count;

}

The algorithm I posted is intended to be mind-numbingly stupid.

It sets random bits in a string, one at a time (until potentially all
bits are set).

Then, after each bit is set, it does an xor to see if the current
number matches the number passed in.

If the numbers match, then return the number of bits set.

Otherwise continue setting bits until all bits are set.

If all bits are set and we did not find a match, then reset to zero
and try again.

It is conceivable that the value 1 would iterate forever, but most
likely it would only take about 4 full passes through the code (on
average) to find a match. A bad prng could spell real trouble here,
especially if you extend it to larger integer sizes.

I suggest that a contest to create a worse algorithm would require
some hefty creativity, if there were a requirement that every
statement must have a purpose towards the goal (e.g. no deliberate
wait loops or things of that nature). I suppose that an incredibly
inefficient prng might be a nice touch.