Challenging BitManipulation puzzles...

[lefoot]

Here is the problem.
The funtion "bitcount" has the parameter x( integer type, 4byte).
The "bitcount" should count the number of '1' from the binary
representation
of x.
But You shouldn't use either 'if' or 'else'. You're allowed to use
bitwise
operators such as '!, ~, ^, &, |, >>, <<'. You can use any local
variables,
constants, and '=' operator.
Preventing you from counting in brute-force manner such
as(x&1+x>>1&1+x>>2&1+...x>>30&1+x>>31&1), You have to count the bit
number within 40 operators.
This is one of my assignment, but I can't find any solution. A little
hint
would be great help for me. Waiting for your reply. Thanks.

 

[Arthur J. O'Dwyer]

Here is the problem.

[bitcount HW]

Google "HAKMEM". Cut and paste.
[Hint: "parallel addition."]
If you have a real C question, you
can ask it here.

-Arthur

 

[Christian Bau]

Here is the problem.
The funtion "bitcount" has the parameter x( integer type, 4byte).
The "bitcount" should count the number of '1' from the binary
representation
of x.
But You shouldn't use either 'if' or 'else'. You're allowed to use
bitwise
operators such as '!, ~, ^, &, |, >>, <<'. You can use any local
variables,
constants, and '=' operator.
Preventing you from counting in brute-force manner such
as(x&1+x>>1&1+x>>2&1+...x>>30&1+x>>31&1), You have to count the bit
number within 40 operators.
This is one of my assignment, but I can't find any solution. A little
hint
would be great help for me. Waiting for your reply. Thanks.

Make a table with 2048 entries, where table = number of bits in i.
Then calculate table [x >> 22] + table [(x >> 11) & 0x7ff] + table [x &
0x7ff]. On my Macintosh that is compiled into exactly eight assembler
instructions.

By the way, if you have a Macintosh you can also submit your original
brute-force method (but I would subtract points for mixing & + and >>
without brackets), because it uses only 31 assembler instructions

 

[Ben Pfaff]

The funtion "bitcount" has the parameter x( integer type, 4byte).
The "bitcount" should count the number of '1' from the binary
representation
of x.
But You shouldn't use either 'if' or 'else'. You're allowed to use
bitwise
operators such as '!, ~, ^, &, |, >>, <<'. You can use any local
variables,
constants, and '=' operator.
Preventing you from counting in brute-force manner such
as(x&1+x>>1&1+x>>2&1+...x>>30&1+x>>31&1), You have to count the bit
number within 40 operators.

Refer to section 5-1 of H.S. Warren, Jr., _Hacker's Delight_,
which has an extensive discussion of the "population count"
problem.

 

[pete]

Here is the problem.
The funtion "bitcount"

unsigned bit_count(unsigned n)
{
unsigned count;

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