Population Count

January 28, 2011

The population count of a bitstring is the number of set bits (1-bits) in the string. For instance, the population count of the number 23, which is represented in binary as 101112, is 4. The population count is used in cryptography and error-correcting codes, among other topics in computer science; some people use it as an interview question. The population count is also known as Hamming weight.

Your task is to write a function that determines the population count of a number representing a bitstring; you should concern yourself with the efficiency of your solution. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

29 Responses to “Population Count”

  1. Erlend said

    My solution (Haskell):

    -- lazily produce the binary representation of a number as a list of [0,1]
    bin :: Integer -> [Integer]
    bin n = bin' n ((floor . logBase 2 . fromIntegral) n)
        where bin' 1 0 = [1]
              bin' 0 0 = [0]
              bin' a b = if a >= 2^b
                            then 1:bin' (a-2^b) (b-1)
                            else 0:bin' a       (b-1)
    
    popCount :: Integer -> Integer
    popCount n = foldr (+) 0 (bin n)
    
    main = do
          print $ popCount 23
          print $ popCount 48975823499389471387489274897123894718238947238947189
    
  2. Alan said
    popcount =: monad define
    +/"1 #: y
    )
    pctab =: monad define
    (,.y);(#:y);,. popcount y
    )
    
       popcount 23
    4
    
       pctab 23
    +--+---------+-+
    |23|1 0 1 1 1|4|
    +--+---------+-+
    
       pctab 1 2 3 23 24 25
    +--+---------+-+
    | 1|0 0 0 0 1|1|
    | 2|0 0 0 1 0|1|
    | 3|0 0 0 1 1|2|
    |23|1 0 1 1 1|4|
    |24|1 1 0 0 0|2|
    |25|1 1 0 0 1|3|
    +--+---------+-+
    
  3. [...] today’s Programming Praxis, our task is to count the active bits in a number. Let’s get started, [...]

  4. My Haskell solution (see http://bonsaicode.wordpress.com/2011/01/28/programming-praxis-population-count/ for a version with comments):

    import Data.Bits
    import Data.Word
    import qualified Data.IntMap as I
    
    popCount1 :: Bits a => a -> Int
    popCount1 n = length $ filter (testBit n) [0..31]
    
    popCount2 :: Bits a => a -> Int
    popCount2 = length . takeWhile (/= 0) . iterate (\n -> n .&. (n - 1))
    
    popCount3 :: (Integral a, Bits a) => Int -> a -> Int
    popCount3 k = sum . map ((ps I.!) . fromIntegral . (.&. (2^k - 1))) .
                  takeWhile (/= 0) . iterate (\n -> shiftR n k) where
         ps = I.fromList $ map (\i -> (i, popCount2 i)) [0..2^k - 1]
    
  5. Graham said

    My Python versions, in increasing speed. The dictionary used in pop4 has been
    abbreviated here, but the full version is available on http://codepad.org/tLUpvZO8.
    (Note: I didn’t run this code on codepad, because it has some Python 2.6 or
    greater specific features, e.g. bin() and format().)

    def pop1(n):
    # Naive; first changes n to binary, then adds up bits one by one
    # Perhaps most Pythonic, but not the quickest
        return sum(int(i) for i in bin(n)[2:])
    
    def pop2(n):
    # Based on an equation in "Hacker's Delight" by H. Warren
        p = n
        while n:
            n >>= 1
            p -= n
        return p
    
    def pop3(n):
    # Wegner version; also claimed to be Kernighan's way and endorsed by Knuth
        p = 0
        while n:
            p += 1
            n &= n - 1
        return p
    
    d = {
            0: 0,  1: 1,  2: 1,  3: 2,  4: 1,  5: 2,  6: 2,  7: 3,  8: 1,  9: 2,
            ...
            252: 6,  253: 7,  254: 7,  255: 8
        }
    
    def pop4(n):
    # Lookup table/dictionary; only works on integers in [0, 2 ** 32 - 1]
    # Fast but memory intensive; might be worth it if we make repeated calls
        return d[n & 0xFF] + d[(n >> 8) & 0xFF] + d[(n >> 16) & 0xFF] + d[n >> 24]
    
  6. Gambiteer said

    Gosper’s algorithm, and many similar ones, can be found in “Hacker’s delight” by Henry Warren; it’s a great book!

  7. Graham said

    Extending my lookup-in-dictionary pop4 to arbitrarily large unsigned integers:

    def pop5(n):
    # Written to extend pop4 to arbitrarily large unsigned integers
        p = 0
        while n:
            p += d[n & 0xFF]
            n >>= 8
        return p
    

    While certainly not memory efficient, this is rather speedy for large numbers (especially with
    repeated calls).

  8. Bruno said

    I`m a somewhat recent user of this website, but I just love it because it can help me improve my codes and thinking.

    Here`s my somewhat naive solution:

    /* Bruno Oliveira – This program determines the number of set-bits (1 bit) in a bitstring,
    representing a decimal number. */

    #include
    #include
    #include
    using namespace std;

    int hamming(unsigned long long int n)
    {
    vector v;
    int res = 0;

    while(n > 0)
    {
    v.push_back(n%2);
    n = n/2;
    }

    for(int x = v.size()-1; x >= 0; x–)
    {
    if(v[x] == 1)
    res++;
    }
    return res;
    }

    int main()
    {
    int s = hamming(23);
    cout << s;
    return 0;
    }

  9. Axio said

    ;; Should work properly.

    (define (make-bit-count table-size)
      (let ((v (make-vector table-size)))
        (let loop ((i 0))
          (if (= table-size i)
            (lambda (idx) (vector-ref v idx))
            (begin
              ;; I know, I’m cheating here because I use gambit
              ;; But the table isn’t hard to compute and could even
              ;; be hard-coded.
              (vector-set! v i (bit-count i))
              (loop (+ i 1)))))))

    (define (my-bit-count n #!optional (size 8))
      (let* ((s (expt 2 size))
             (b-c (make-bit-count s))
             (t-s-b (- s 1)))
        (let loop ((n n) (bc 0))
          (if (> n t-s-b)
            (loop (arithmetic-shift n (- size))
                  (+ bc (b-c (bitwise-and n t-s-b))))
            (+ bc (b-c n))))))

  10. Bruno said

    I`d now like to ask, if any of you knows how to manipulate large integers in C++, without using any external libraries?

    I`d like to perform only the 4 basic arithmetic operations on them: Sum, divide, subtract, multiply; I`d also like to assign them to variables and manipulate them as I do with normal integers.

    Hope that it`s okay to ask it here ;)

    Thanks in advance,
    Bruno

  11. eb said

    This work?

    Groovy(/Java):

    def getPop(num) {
    def pop = rem = 0
    while(num != 0) {
    (num,rem) = num.divideAndRemainder(2)
    pop += rem
    }
    return pop
    }

    println “Enter a number: ”
    def num = null
    System.in.withReader {
    num = it.readLine()
    }
    assert num.isBigInteger()
    println “Population is: ${getPop(num.toBigInteger())}”

  12. Marco said

    def hamming_weight(number):
    “””docstring for get_bit_string_pop_count”””
    count = 0
    if number == 1:
    return 1
    elif number == 0:
    return 0
    count += hamming_weight(number/2)
    count += number % 2
    return count

  13. rajul said

    #include
    #include

    long int hamming(long a)
    {long n=a;
    const long int m1= 0×55555555;
    const long int m2=0×33333333;
    const long int m4=0x0f0f0f0f;
    const long int m8=0x00ff00ff;
    const long int m16=0x0000ffff;

    n=(n+(n>>1))&m1;
    n=(n+(n>>2))&m2;
    n=(n+(n>>4))&m4;
    n=(n+(n>>8))&m8;
    n=(n+(n>>16))&m16;
    return n;
    }

    int main()
    {
    long int n;
    printf(“%ld”,hamming(100));
    getch();
    return 0;
    }

  14. Ramakrishna Chikkala said

    Simple C function:

    int pop_count (unsigned bitstring){

    int i;
    int population_count = 0;

    for (i=0; i> 1)){
    if (bitstring & 0×1){
    population_count ++;

    }
    }

    return population_count;

    }

  15. rajul said

    hello ramakrishna
    can you please give full function with main()

  16. Ramakrishna Chikkala said

    Sorry.. for some reason it “paste didn’t work properly.
    The function with a sample main is below:
    int pop_count (unsigned);
    int pop_count (unsigned bitstring){
    int i;
    int population_count = 0;

    for(i=0;i> 1;
    }

    return population_count;

    }

    int main () {

    unsigned input = 0xf3f3;
    unsigned result = 0;
    result = pop_count(input);
    printf(“\n population count is %d”, result);
    return 1;
    }

  17. Ramakrishna Chikkala said

    It seems I need to paste html.
    Link to code is as below

    http://codepad.org/MOQkkc1Q

  18. cemper said

    In Python:

    def population(n):
        i = 0
        while n:
            i += n & 1
            n >>= 1
        return n
    
  19. cemper said

    Sorry, It ostensibly is supposed to be “return i”, not “return n”.

  20. rajul said

    great cemper you are awesome ,what a great post.

  21. Rainer said

    My try in REXX

    do forever                                           
        say 'Whole number?'                              
        parse pull num                                   
        if \ datatype(num,'N') then leave                
        say 'Decimal 'num' = Binary: 'X2B(D2X(num)),     
            '-> Population: 'pop(num)                    
    end                                                  
    exit                                                 
                                                         
    pop:                                                 
       parse arg dez                                     
       pop = 0                                           
       do until dez = 0                                  
          bit = dez // 2                                 
          pop = pop + bit                                
          dez = dez % 2                                  
       end                                               
       return pop                                        
    
  22. siva said

    Solution in C:

    #include

    int population(int num)
    {
    int pop = 0;

    while (num)
    {
    ++pop;
    num &= (num – 1);
    }

    return pop;
    }

    int main(int argc, char *argv[])
    {
    int num;
    printf(“Enter val:”);
    scanf(“%d”, &num);

    printf(“Population of %d = %d\n”, num, population(num));
    }

  23. rajul said

    good answer siva

  24. pfcuttle said
    import Data.Char
    import Numeric
    
    
    population x = length . filter (== '1') . showIntAtBase 2 intToDigit x $ ""
    
  25. #

    def populationcount(n):
        return sum([int(i) for i in str(n) if i == '1'])
    #
  26. homanhduc said

    My implementation on C++ :

    #include <iostream>
    using namespace std;
    
    //count the number of set bits
    int popCount(int num)
    {
    	int sBit = 0;
    	//shift 32 bits
    	for (int i = 0; i < 32; ++i){
    		//OR with 1
    		if ((num & 1) == 1)
    			sBit++;
    		//shift 1 pos more.
    		num = num >> 1;
    	}
    	return sBit;
    }
    int main()
    {
    	int n;
    	cout << "Enter a number: ";
    	cin  >> n;
    	cout << "The number of set bits in " << n
    		 << ": " << popCount(n);
    	
    	return 0;
    }
    
  27. jtlien said


    – Haskell popCount that can handle very large integers. The one above uses logbase which converts n to a float
    – and hence cannot handle bignum integers larger than 2^2048.

    module Main (main) where

    import Data.Bits
    import Data.Word
    import Data.List

    two30 = 1073741824 — 2^30

    – Count the one bits in the binary representation of a 32 bit int

    ones :: Word32 -> Word32
    ones n =
    case n – ((n `shiftR` 1) .&. 0×55555555) of
    x -> case (x .&. 0×33333333) + ((x `shiftR` 2) .&. 0×33333333) of
    y -> case (y + (y `shiftR` 4)) .&. 0x0F0F0F0F of
    z -> case z + (z `shiftR` 8) of
    a -> case a + (a `shiftR` 16) of
    b -> b .&. 0x3F

    – Get all the one bits sets for an bignum Integer

    allOnes::Integer->Integer
    allOnes b = sum ( allOneList b )

    – From a bignum Integer, get a list of Integers [Integer]
    allOneList b | b == 0 = []
    allOneList b = [ fromIntegral (ones ( fromIntegral ( b `mod` two30 ))) ] ++ allOneList (b `shiftR` 30)

    main = print $ show $ allOnes ((2^131)-1)

  28. David said

    FORTH version

    : countbits ( n -- n )
        dup $55555555 and  swap $AAAAAAAA and  1 rshift +
        dup $33333333 and  swap $CCCCCCCC and  2 rshift +
        dup $0F0F0F0F and  swap $F0F0F0F0 and  4 rshift +
        dup $00FF00FF and  swap $FF00FF00 and  8 rshift +
        dup $0000FFFF and  swap $FFFF0000 and  16 rshift + ;
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: