## 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 10111_{2}, 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.

Pages: 1 2

My solution (Haskell):

[...] today’s Programming Praxis, our task is to count the active bits in a number. Let’s get started, [...]

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

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()`

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

Extending my lookup-in-dictionary

`pop4`

to arbitrarily large unsigned integers:While certainly not memory efficient, this is rather speedy for large numbers (especially with

repeated calls).

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;

}

;; Should work properly.

(

define(make-bit-count table-size)(

let((v (make-vector table-size)))(

letloop ((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)))

(

letloop ((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))))))

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

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())}”

[...] Little bit of J language fun at programmingpraxis: http://programmingpraxis.com/2011/01/28/population-count/#comment-2370 [...]

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

#include

#include

long int hamming(long a)

{long n=a;

const long int m1= 0x55555555;

const long int m2=0x33333333;

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;

}

Simple C function:

int pop_count (unsigned bitstring){

int i;

int population_count = 0;

for (i=0; i> 1)){

if (bitstring & 0x1){

population_count ++;

}

}

return population_count;

}

hello ramakrishna

can you please give full function with main()

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;

}

It seems I need to paste html.

Link to code is as below

http://codepad.org/MOQkkc1Q

In Python:

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

great cemper you are awesome ,what a great post.

My try in REXX

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));

}

good answer siva

#

My implementation on C++ :

–

— 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) .&. 0x55555555) of

x -> case (x .&. 0x33333333) + ((x `shiftR` 2) .&. 0x33333333) 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)

FORTH version