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
#include<cstdint>
uint32_t c = 0;
for (; i; i &= i - 1, ++c);
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
funcPopCountUInt64(i uint64) (c int) {
i -= (i >> 1) & 0x5555555555555555
i = (i>>2)&0x3333333333333333 + i&0x3333333333333333
i += i >> 4
i &= 0x0f0f0f0f0f0f0f0f
i *= 0x0101010101010101returnint(i >> 56)
}
funcPopCountUInt32(i uint32) (n int) {
i -= (i >> 1) & 0x55555555
i = (i>>2)&0x33333333 + i&0x33333333
i += i >> 4
i &= 0x0f0f0f0f
i *= 0x01010101returnint(i >> 24)
}
This was useful only before go 1.9. See math/bits.OnesCount instead.
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;
Perl pack 'i' interprets $i as an integer and packs it into a byte string. Unpack '%b' converts it to a list of zeros and ones. In scalar context, $c gets the count of the list.
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)
}
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;