Bit Counting

Discussion in 'C Programming' started by GJ, Oct 20, 2005.

  1. GJ

    GJ Guest

    I came accross the following code snippet to count the number of 1 bit in a word (32bit in this case). However I am not able to understand it thoroughly.. Could anyone please explain this.

    ===============================================

    x = (0x55555555 & x) + (0x55555555 & (x>> 1)); x = (0x33333333 & x) + (0x33333333 & (x>> 2)); x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4)); x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8)); x = (0x0000ffff & x) + (0x0000ffff & (x>>16));===============================================

    Regards,

    GJ
     
    GJ, Oct 20, 2005
    #1
    1. Advertisements

  2. GJ

    Alex Fraser Guest

    The nth line makes each adjacent group of 2^n bits in x equal the sum of the
    two (2^(n-1))-bit numbers which make up that group.

    Alex
     
    Alex Fraser, Oct 20, 2005
    #2
    1. Advertisements

  3. You will find this in "Hacker's Delight" by Warren on p. 65.
    Basically it is divide-and-conquer. Warren explains it in detail.


    --
    Julian V. Noble
    Professor Emeritus of Physics

    ^^^^^^^^^^^^^^^^^^
    http://galileo.phys.virginia.edu/~jvn/

    "For there was never yet philosopher that could endure the
    toothache patiently."

    -- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.
     
    Julian V. Noble, Oct 20, 2005
    #3
  4. Consider the decimal case of showing the sum of digits in the number
    12738349 (37)...

    12738349
    \/\/\/\/
    03101113 (1+2, 7+3, 8+3, 4+9)
    \ / \ /
    00130024 (3+10, 11+13)
    \ /
    00000037 (13+24)

    The code above does the same thing, only bitwise for binary (and with
    extra iterations for the extra initial digits.)
     
    Peter Nilsson, Oct 21, 2005
    #4
    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.