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.

Recommended Answers

All 4 Replies

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.