Thread: Fastest way to count the number of 1's in a n-bit number

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    1

    Fastest way to count the number of 1's in a n-bit number

    Figure out the fastest way to count the number of 1's in a n-bit number. Also, code it up as part of a function and then call the function on an arbitrary-length number. Assume that each 32bits of the number are stored in an integer array as shown below:

    320 bit number is represented as:

    int a[10];

    a[9] = 0x99999999;
    a[8] = 0x88888888;
    ....
    a[0] = 0x0;

    So, this number 320-bit number is:

    0x9999 9999 8888 8888 7777 7777 ....0000 0000

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    You might want to read this link.

    The fastest way to do what you want would involve lookup tables and/or specific assumptions/knowledge about relative performance of certain bitwise/numeric operators on your target machine/environment.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The answer depends on the result.
    Some of the algorithms have a running time proportional to the number of bits that were set. In those cases they are the fastest algorithm if the number of bits set is below some threshold. Unfortunately if you don't have any idea of the number of bits set in advance then you can't know which algorithm to pick. (Chicken & egg scenario)

    The only algorithm that can therefore be considered the fastest is the popcount family of intrinsics, which isn't really an algorithm at all since the hardware just does it for you.

    You forgot to ask a question, and do not simply presume to pass your work on to us. We will not do it for you!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Count number of letters...
    By sponi in forum C Programming
    Replies: 24
    Last Post: 09-14-2011, 10:30 PM
  2. what would I use to count number of words
    By yuuh in forum C Programming
    Replies: 1
    Last Post: 08-11-2009, 07:10 AM
  3. Count number!
    By tx1988 in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2007, 08:23 PM
  4. how to count the number of sentences.
    By Ray Thompson in forum C Programming
    Replies: 3
    Last Post: 11-10-2002, 10:25 AM
  5. count the number of token
    By rsanga1 in forum C Programming
    Replies: 0
    Last Post: 10-02-2001, 11:48 AM