## 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.

Pages: 1 2

### 29 Responses to “Population Count”

1. Erlend said

```-- 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 = 
bin' 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
)
(,.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, […]

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

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
}
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= 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;
}

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 & 0x1){
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

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

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) .&. 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)

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 + ;
```