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.

[Christian Bau]

In article <45************ **************@ posting.google. com>,
le****@lycos.co .kr (lefoot) wrote:

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 [i] = 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 :-)

[Arthur J. O'Dwyer]

On Tue, 29 Sep 2003, lefoot wrote:

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

[Ben Pfaff]

le****@lycos.co .kr (lefoot) writes:

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.
--
"What is appropriate for the master is not appropriate for the novice.
You must understand the Tao before transcending structure."
--The Tao of Programming

[pete]

lefoot wrote:

Here is the problem.
The funtion "bitcount"

unsigned bit_count(unsig ned n)
{
unsigned count;

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

--
pete