Anyone have an idea how see if a 32 bit integer has an even or odd number
of 1 bits using ONLY bitwise operations?
! ~ & ^ | + << >>

thnx.

4
Contributors
4
Replies
6
Views
6 Years
Discussion Span
Last Post by Narue

Anyone have an idea...

Sure.
Check the last bit, if 1, increment a count
Shift the value 1 bit >
Check again
Continue until done.

@Walt

Quick question, the condition in the while loop will use arithmetic and relational operators right ? Or is there any way to write the while loop condition?

How many bits do you want to test?

Anyone have an idea how see if a 32 bit integer has an even or odd number of 1 bits using ONLY bitwise operations?

First, ! and + aren't bitwise operators. Second, yes, I know several ways of doing this. Third, since this is invariably a homework question, the task is for you to do it, not for you to ask someone else for the solution.

Though I'll be nice and provide a partial solution since counting bits without a loop is somewhat non-trivial. It's partial because arithmetic operators are used as well. Your job now is to replace them with bitwise operators:

``````unsigned bitcount(unsigned v)
{
unsigned c = 0;

v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

return c;
}``````

Alternatively, you could be pedantic and use the implicit test against 0 for a loop:

``````unsigned value = n;

while (value) /* Equivalent to "while (value != 0)" */
value >>= 1;``````

Some teachers may not allow that though, so I wouldn't recommend it without checking first.

Edited by Narue: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.