Challenging BitManipulation puzzles...

Discussion in 'C Programming' started by lefoot, Sep 30, 2003.

  1. lefoot

    lefoot Guest

    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.
     
    lefoot, Sep 30, 2003
    #1
    1. Advertisements

  2. [bitcount HW]

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

    -Arthur
     
    Arthur J. O'Dwyer, Sep 30, 2003
    #2
    1. Advertisements

  3. 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 :)
     
    Christian Bau, Sep 30, 2003
    #3
  4. lefoot

    Ben Pfaff Guest

    Refer to section 5-1 of H.S. Warren, Jr., _Hacker's Delight_,
    which has an extensive discussion of the "population count"
    problem.
     
    Ben Pfaff, Sep 30, 2003
    #4
  5. lefoot

    pete Guest

    unsigned bit_count(unsigned n)
    {
    unsigned count;

    for (count = 0; n; n &= n - 1) {
    ++count;
    }
    return count;
    }
     
    pete, Sep 30, 2003
    #5
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.