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.
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()
andformat()
.)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)))
(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:
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