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.
Programming Praxis 
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[…] 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):
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]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()andformat().)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]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
pop4to 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 pWhile 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)))
(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))))))
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:
def population(n): i = 0 while n: i += n & 1 n >>= 1 return nSorry, It ostensibly is supposed to be “return i”, not “return n”.
great cemper you are awesome ,what a great post.
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 popSolution 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
#
def populationcount(n): return sum([int(i) for i in str(n) if i == '1']) #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; }—
— 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
: 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 + ;