Logo

Programming-Idioms

  • Python
  • Go

Idiom #84 Count bits set in integer binary representation

Count number c of 1s in the integer i in base 2.

E.g. i=6 → c=2

import "math/bits"
c := bits.OnesCount(i)

i is a uint.
All OnesCountX functions take unsigned integer types.
func PopCountUInt64(i uint64) (c int) {
	i -= (i >> 1) & 0x5555555555555555
	i = (i>>2)&0x3333333333333333 + i&0x3333333333333333
	i += i >> 4
	i &= 0x0f0f0f0f0f0f0f0f
	i *= 0x0101010101010101
	return int(i >> 56)
}

func PopCountUInt32(i uint32) (n int) {
	i -= (i >> 1) & 0x55555555
	i = (i>>2)&0x33333333 + i&0x33333333
	i += i >> 4
	i &= 0x0f0f0f0f
	i *= 0x01010101
	return int(i >> 24)
}

This was useful only before go 1.9.
See math/bits.OnesCount instead.
c = bin(i).count("1")
c = i.bit_count()

For Python 3.10+
#include <stdint.h>
uint32_t c = i;
c = (c & 0x55555555) + ((c & 0xAAAAAAAA) >> 1);
c = (c & 0x33333333) + ((c & 0xCCCCCCCC) >> 2);
c = (c & 0x0F0F0F0F) + ((c & 0xF0F0F0F0) >> 4);
c = (c & 0x00FF00FF) + ((c & 0xFF00FF00) >> 8);
c = (c & 0x0000FFFF) + ((c & 0xFFFF0000) >> 16);

add even and odd bits
then add even and odd pairs of bits
then add even and odd quadruples of bits
then add even and odd octets of bits
then add whatever groups of 16 bits are called
done

with gcc you can also use the function _builtin_popcount
New implementation...
< > ⌨
deleplace 
c := bits.OnesCount(i)
func PopCountUInt64(i uint64) (c int) {
	i -= (i >> 1) & 0x5555555555555555
	i = (i>>2)&0x3333333333333333 + i&0x3333333333333333
	i += i >> 4
	i &= 0x0f0f0f0f0f0f0f0f
	i *= 0x0101010101010101
	return int(i >> 56)
}

func PopCountUInt32(i uint32) (n int) {
	i -= (i >> 1) & 0x55555555
	i = (i>>2)&0x33333333 + i&0x33333333
	i += i >> 4
	i &= 0x0f0f0f0f
	i *= 0x01010101
	return int(i >> 24)
}
c = bin(i).count("1")
c = i.bit_count()
uint32_t c = i;
c = (c & 0x55555555) + ((c & 0xAAAAAAAA) >> 1);
c = (c & 0x33333333) + ((c & 0xCCCCCCCC) >> 2);
c = (c & 0x0F0F0F0F) + ((c & 0xF0F0F0F0) >> 4);
c = (c & 0x00FF00FF) + ((c & 0xFF00FF00) >> 8);
c = (c & 0x0000FFFF) + ((c & 0xFFFF0000) >> 16);
(def c (count (re-seq #"1" (Integer/toBinaryString i))))
uint32_t c = 0;
for (; i; i &= i - 1, ++c);
var c = BitOperations.PopCount((uint)i);
public static int BitCount(int i)
{
    var c = 0;
    while (n != 0)
    {
        c++;
        n &= (n - 1); //walking through all the bits which are set to one
    }

    return c;
}
auto c = bitSet(i).length;
var c = i.toRadixString(2).replaceAll('0','').length;
c = popcnt(i)
c = Data.Bits.popCount i

const c = i.toString(2).replace(/[^1]/g, '').length
int c = Integer.bitCount(i);
int c = new BigInteger(valueOf(i), 2).bitCount();
(setf c (logcount i))
$i = base_convert($i,10,2);
$x = str_replace(0,'',$i);
$c = strlen($x);
c := PopCnt(i);
function BitCount(N: Int64): Integer;
var
  Q: QWord;
  i: Integer;
begin
  Result := 0;
  Q := QWord(N);
  for i := 0 to (8 * SizeOf(N) - 1) do
  begin
    if ((Q and 1) = 1) then Inc(Result);
    Q := Q shr 1;
  end;
end;
# Not best, but simple:
$c=0;
while ($i) {
   $c += $i&1;
   $i /= 2;
}
$c = unpack '%b*', pack 'i', $i;
c = i.digits(2).count(1)
let c = i.count_ones();