473,320 Members | 1,722 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Challenging BitManipulation puzzles...

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.
Nov 13 '05 #1
4 2534
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 :-)
Nov 13 '05 #2

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
Nov 13 '05 #3
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
Nov 13 '05 #4
lefoot wrote:

Here is the problem.
The funtion "bitcount"


unsigned bit_count(unsigned n)
{
unsigned count;

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

--
pete
Nov 13 '05 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Kevin Wan | last post by:
Hi, I have some puzzles about sgistl source code, that is why some methods are placed in protected field. To vector itself, private and protected are the same, and vector isn't desired to be...
17
by: madhav_a_kelkar | last post by:
i was browsing this problem: The following is a piece of C code, whose intention was to print a minus sign 20 times. But you can notice that, it doesn't work. #include <stdio.h> int main() {...
11
by: George | last post by:
Was my question too challenging for everyone? I thought I would get a much quicker response, complete with witty and (sometimes) condescending remarks Here's my question again, in case you missed...
18
by: Frankie | last post by:
I have been hired to go to a former client of mine and train their staff programmers on ASP.NET. These guys have only Mainframe, MS Access, SQL Server, and VB6 desktop application development...
2
by: xPy | last post by:
do you know any links where i can find puzzles, like the 8 queens problem? (I'm not intrested in the solution, only for puzzle...)
11
by: John Salerno | last post by:
Similar to the Python Challenge, does anyone know of any other websites or books that have programming puzzles to solve? I found a book called "Puzzles for Hackers", but it seems like it might be a...
5
by: alainpoint | last post by:
Hi, I have what in my eyes seems a challenging problem. Thanks to Peter Otten, i got the following code to work. It is a sort of named tuple. from operator import itemgetter def...
2
by: =?Utf-8?B?Q3JtTmV3Ymll?= | last post by:
Hi, 1) I want to hone my problem solving skills and be good at logic. How do I achieve this? 2) Where can I find c# puzzles or c# algorithms. 3) How do I print the values of a N X N matrix...
25
by: Oltmans | last post by:
Hi guys, I'm learning JavaScript and I need some puzzles that can make me a better JavaScript programmer. I mean I'm looking out for programming puzzles (e.g. Project Euler or TopCoder) but I'm...
62
jkmyoung
by: jkmyoung | last post by:
Does anyone have some super, super hard Sudoku puzzles? Back in February this year, I had enough time to finally program a Sudoku solver in Java. Right now, I'm looking for solvable puzzles, but...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.