## Population Count

### January 28, 2011

Scheme doesn’t have the concept of the size of a number, but if you are working in a language like C, you should consider finding the population count of integers of the native size for your machine.

We begin with the naive solution: index through the bits of the number, counting those that are set, using bit operations instead of arithmetic (`ash`

is arithmetic-shift, where a negative argument is a right-shift):

`(define (pop-count n)`

(let loop ((n n) (count 0))

(if (zero? n) count

(loop (ash n -1) (+ count (logand n 1))))))

If you have space available, you can count the bits *k* at a time instead of one at a time; here is the case for *k*=4, but you may wish to use *k*=8, or even *k*=32, which makes `pop-count`

a constant-time operation:

`(define (pop-count n)`

(let ((bits #(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)))

(let loop ((n n) (count 0))

(if (zero? n) count

(loop (ash n -4) (+ count (vector-ref bits (logand n #xF))))))))

If you know that the bitstring is sparse, it is faster to count only the 1-bits and ignore the 0-bits; this technique was described by Peter Wegner in 1960 (CACM, Volume 3, Number 5, May 1960, Page 322) and takes one loop per 1-bit instead of one loop per bit:

`(define (pop-count n)`

(let loop ((n n) (count 0))

(if (zero? n) count

(loop (logand n (- n 1)) (+ count 1)))))

Our last version comes from HAKMEM 169 by Bill Gosper and is specific to 32-bit unsigned integers; we’ll leave to you the pleasure of figuring out how it works:

`(define (pop-count n)`

(let ((count n))

(set! count (- count (logand (ash n -1) #o33333333333)))

(set! count (- count (logand (ash n -2) #o11111111111)))

(set! count (logand (+ count (ash count -3)) #o30707070707))

(modulo count 63)))

There are other ways to perform the population count; hopefully we’ll see some of the possibilities in the comments below.

We used the `ash`

and `logand`

operators from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/XdWh16R5.

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: https://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