[algorithm] 32 비트 정수로 설정된 비트 수를 계산하는 방법은 무엇입니까?

또한 컴파일러의 내장 함수를 고려하십시오.

예를 들어 GNU 컴파일러에서는 다음을 사용할 수 있습니다.

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

최악의 경우 컴파일러는 함수에 대한 호출을 생성합니다. 가장 좋은 경우 컴파일러는 동일한 작업을 더 빨리 수행하기 위해 CPU 명령을 내 보냅니다.

GCC 내장 함수는 여러 플랫폼에서 작동합니다. Popcount는 x86 아키텍처에서 주류가 될 것이므로 이제 내장 함수를 사용하는 것이 좋습니다. 다른 아키텍처에는 몇 년 동안 인구수가 있습니다.

x86에서는 컴파일러에게 동일한 세대에 추가 된 벡터 명령어를 사용 하거나 popcnt명령어를 지원한다고 가정 할 수 있습니다 . GCC x86 옵션을 참조하십시오 . (또는 코드에서 가정하고 조정하려는 CPU)가 좋은 선택이 될 수 있습니다. 이전 CPU에서 결과 바이너리를 실행하면 잘못된 명령 오류가 발생합니다.-mpopcnt-msse4.2-march=nehalem-march=

바이너리를 빌드 한 머신에 최적화 된 바이너리를 만들려면 -march=native gcc, clang 또는 ICC와 함께 사용하십시오 .

MSVC는 x86 popcnt명령어에 대한 내장 함수를 제공 하지만 gcc와 달리 실제로는 하드웨어 명령어에 고유하며 하드웨어 지원이 필요합니다.

std::bitset<>::count()내장 대신 사용

이론적으로 대상 CPU에 대해 효율적으로 popcount하는 방법을 알고있는 모든 컴파일러는 ISO C ++를 통해 해당 기능을 노출해야합니다 std::bitset<>. 실제로 일부 대상 CPU의 경우 비트 핵 AND / shift / ADD를 사용하는 것이 좋습니다.

하드웨어 popcount가 선택적인 확장 (x86과 같은) 인 대상 아키텍처의 경우 모든 컴파일러가 std::bitset사용 가능한 경우이를 활용 하는 것은 아닙니다 . 예를 들어, MSVC는 popcnt컴파일 타임에 지원 을 활성화 할 수있는 방법이 없으며 기술적으로 별도의 기능 비트가 있지만 SSE4.2를 의미하는 경우에도 항상 테이블 조회를 사용 합니다 ./Ox /arch:AVXpopcnt

그러나 적어도 어느 곳에서나 휴대 가능한 것을 얻을 수 있으며 올바른 대상 옵션이있는 gcc / clang을 사용하면이를 지원하는 아키텍처에 대한 하드웨어 팝 카운트를 얻을 수 있습니다.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

Godbolt 컴파일러 탐색기 에서 gcc, clang, icc 및 MSVC의 asm을 참조하십시오 .

x86-64는 다음을 gcc -O3 -std=gnu++11 -mpopcnt방출합니다.

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret
unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax
    ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64는 다음을 gcc -O3 -std=gnu++11방출합니다 ( intarg 버전의 경우).

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

이 소스는 x86 또는 GNU에 국한되지 않지만 gcc / clang / icc를 사용하여 x86에 대해서만 잘 컴파일됩니다.

또한 단일 명령 popcount가없는 아키텍처에 대한 gcc의 폴백은 한 번에 바이트 당 테이블 조회입니다. 예를 들어 이것은 ARM 에게는 좋지 않습니다 .

답변

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
    return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

v = v - ((v >> 1) & 0x55555555);

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00
   0b01           0b00               0b01
   0b10           0b01               0b01
   0b11           0b01               0b10

v = (v & 0x33333333) + ((v >> 2) & 0x33333333);

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

v + (v >> 4)

0b01000010 + 0b01000000

0b01100010 & 0xF0 = 0b01100000

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}