How to count bits in a unsigned int?

[tfeldman21]

On 32-bit platform,
I am working on getting how many bits equal to 1 without an if loop.

 

[Guest]

On 32-bit platform,
I am working on getting how many bits equal to 1 without an if loop.

Use a for loop or a while loop, testing each bit until you have no
more bits to test. I'm not sure what an if loop would be like, unless
you're using goto.

 

[Keith Thompson]

On 32-bit platform,
I am working on getting how many bits equal to 1 without an if loop.

Your task is made easier by the fact that there's no such thing as an
"if loop", so you won't have any trouble avoiding it.

The most important step in solving any problem is defining exactly
what the problem is. You haven't done that.

But questions of the form "How can I do X without using feature Y?"
are almost always homework assignments. We won't do your homework for
you (unless you're willing to pay our exhorbitant consulting fees
*and* let us submit our solutions directly to your instructor).

We're quite willing to help you solve any problems in your C code, but
we can't do that unless you write some and post it.

 

[CBFalconer]

Use a for loop or a while loop, testing each bit until you have
no more bits to test. I'm not sure what an if loop would be like,
unless you're using goto.

I have no idea what an 'if loop' is.

unsigned int value, count;

value = whatever;
count = 0;

/* loop invariant: count + bitsinvalue = bitsinwhatever */
while (value) {
count++;
value = (value - 1) & value;
}
/* bitsinvalue = 0 */

which doesn't care how wide an int is.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Malcolm McLean]

On 32-bit platform,
I am working on getting how many bits equal to 1 without an if loop.

On the lowest bit can equal one. The rest equal 2, 4, 8 ... etc.

So if (x & 1) is your answer.

Tell your professor he means the number of set bits.

 

[Guest]

Use a for loop or a while loop, testing each bit until you have
no more bits to test. I'm not sure what an if loop would be like,
unless you're using goto.

I have no idea what an 'if loop' is.
[example]
which doesn't care how wide an int is.

And the way I mentioned does?

count = value < 0;
for (bit = 1; bit < INT_MAX / 2; bit *= 2)
if (value & bit)
count++;

It accepts ints of any width.

 

[Guest]

(e-mail address removed) wrote:

On 32-bit platform, I am working on getting how many bits equal
to 1 without an if loop.

Use a for loop or a while loop, testing each bit until you have
no more bits to test. I'm not sure what an if loop would be like,
unless you're using goto.

I have no idea what an 'if loop' is.
[example]
which doesn't care how wide an int is.

And the way I mentioned does?

count = value < 0;

count = 0;

for (bit = 1; bit < INT_MAX / 2; bit *= 2)

for (bit = 1; bit != 0; bit *= 2)

if (value & bit)
count++;

It accepts ints of any width.

The question asked for unsigned ints, but I posted an example for ints.

 

[Guest]

Harald van D?k wrote:
(e-mail address removed) wrote:

On 32-bit platform, I am working on getting how many bits equal
to 1 without an if loop.

Use a for loop or a while loop, testing each bit until you have
no more bits to test. I'm not sure what an if loop would be like,
unless you're using goto.

I have no idea what an 'if loop' is.
[example]
which doesn't care how wide an int is.

And the way I mentioned does?

count = value < 0;

count = 0;

for (bit = 1; bit < INT_MAX / 2; bit *= 2)

for (bit = 1; bit != 0; bit *= 2)

if (value & bit)
count++;

It accepts ints of any width.

The question asked for unsigned ints, but I posted an example for ints.

Sorry for replying to myself so much, but the example for ints was
wrong anyway. After the loop exited, I needed to check value & bit
once more, to see if the highest value bit was set.

 

[Ksitami]

static inline ulong bit_count(ulong x) {
// Return number of bits set
x = (0x55555555 & x) + (0x55555555 & (x>> 1)); // 0-2 in 2 bits
x = (0x33333333 & x) + (0x33333333 & (x>> 2)); // 0-4 in 4 bits
x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4)); // 0-8 in 8 bits
x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8)); // 0-16 in 16
bits
x = (0x0000ffff & x) + (0x0000ffff & (x>>16)); // 0-31 in 32
bits
return x;
}

//Algorithms for programmers ideas and source code
//by J¨org Arndt, (e-mail address removed)

 

[CoL]

You also try recursion for the same....

~col

I have no idea what an 'if loop' is.
[example]
which doesn't care how wide an int is.

And the way I mentioned does?

count = value < 0;
for (bit = 1; bit < INT_MAX / 2; bit *= 2)
    if (value & bit)
        count++;

It accepts ints of any width.

 

[Christopher Layne]

You also try recursion for the same....

~col

To count bits? You're not in the business of performance eh?

 

[CBFalconer]

(e-mail address removed) wrote:

On 32-bit platform, I am working on getting how many bits equal
to 1 without an if loop.

Use a for loop or a while loop, testing each bit until you have
no more bits to test. I'm not sure what an if loop would be like,
unless you're using goto.

I have no idea what an 'if loop' is.
[example]
which doesn't care how wide an int is.

And the way I mentioned does?

count = value < 0;
for (bit = 1; bit < INT_MAX / 2; bit *= 2)
if (value & bit)
count++;

It accepts ints of any width.

But it needs to know the precise type. My version will work when
fed bytes, longs, shorts, etc. (with matching changes in the type
of value, but making value an unsigned long will cover them all,
except long long which may or may not be available).

I find code fragments that need no editing more useful.
--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Christopher Layne]

But it needs to know the precise type. My version will work when
fed bytes, longs, shorts, etc. (with matching changes in the type
of value, but making value an unsigned long will cover them all,
except long long which may or may not be available).

I find code fragments that need no editing more useful.

What's wrong with the typical straightforward way?

int bs(unsigned long v)
{
int c;

for (c = 0; v; v >>= 1)
c += v & 1;

return c;
}

 

[Guest]

Harald van D?k wrote:
(e-mail address removed) wrote:

On 32-bit platform, I am working on getting how many bits equal
to 1 without an if loop.

Use a for loop or a while loop, testing each bit until you have
no more bits to test. I'm not sure what an if loop would be like,
unless you're using goto.

I have no idea what an 'if loop' is.
[example]
which doesn't care how wide an int is.

And the way I mentioned does?

count = value < 0;
for (bit = 1; bit < INT_MAX / 2; bit *= 2)
if (value & bit)
count++;

It accepts ints of any width.

But it needs to know the precise type. My version will work when
fed bytes, longs, shorts, etc. (with matching changes in the type
of value, but making value an unsigned long will cover them all,
except long long which may or may not be available).

I find code fragments that need no editing more useful.

Your version will not work with signed types, and the version for
unsigned types I posted later does not need editing either, as long as
the type of 'bit' is large enough.

 

[CBFalconer]

What's wrong with the typical straightforward way?

int bs(unsigned long v)
{
int c;

for (c = 0; v; v >>= 1)
c += v & 1;
return c;
}

Nothing that I can see. It will take more cycles, for each 0 bit
to the right of any 1 bit.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Radamanthe]

http://graphics.stanford.edu/~seander/bithacks.html

 

[pete]

On 32-bit platform,
I am working on getting how many bits equal to 1 without an if loop.

unsigned bit_count(unsigned n)
{
unsigned count;

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

 

[jxh]

To count bits? You're not in the business of performance eh?

Should perform just as well with proper optimizations:

static int
bits_r (unsigned int u, int count)
{
return !u ? count : bits_r(u & u-1, count+1);
}

int
bits (unsigned int u)
{
return bits_r(u, 0);
}

-- James

 

[dick]

I have no idea what an 'if loop' is.

unsigned int value, count;

value = whatever;
count = 0;

/* loop invariant: count + bitsinvalue = bitsinwhatever */
while (value) {
count++;
value = (value - 1) & value;
}
/* bitsinvalue = 0 */

which doesn't care how wide an int is.

this is an interview question.

i = 0;
while(var)
{
var &= ~(-var);
i++;
}

 

[CBFalconer]

this is an interview question.

i = 0;
while(var)
{
var &= ~(-var);
i++;
}

Doesn't work. Consider overflow (-var, for var == INT_MIN, 2'
complement), sign-magnitude representation, 1's complement
representation.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews