1のビットを数える popcount

#ビット演算で立っているビットを数える

population count = #popcount

x86_64の組み込み関数を使う

code:c++

#ifdef _MSC_VER

#include <intrin.h>

#include <x86intrin.h>

#ifdef __GNUC__

__builtin_popcountll(x)

__builtin_popcount(x)

__popcnt64(x)

__popcnt(x)

ビット演算で書く

code:c++

int pop_count_ull(uint64_t x){

x = x - ((x >> 1) & 0x5555555555555555ULL);

x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);

x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL;

x = (x * 0x0101010101010101ULL) >> 56;

return x;

}

int pop_count_uint(uint32_t x){

x = (x & 0x55555555) + ((x & 0xAAAAAAAA) >> 1);

x = (x & 0x33333333) + ((x & 0xCCCCCCCC) >> 2);

return (x & 0x0F0F0F0F) + ((x & 0xF0F0F0F0) >> 4);

}

int pop_count_uchar(uint8_t x){

x = (x & 0b01010101) + ((x & 0b10101010) >> 1);

x = (x & 0b00110011) + ((x & 0b11001100) >> 2);

return (x & 0b00001111) + ((x & 0b11110000) >> 4);

}