32 비트 정수에서 설정 비트 수를 계산하는 방법은 무엇입니까?
숫자 7을 나타내는 8 비트는 다음과 같습니다.
00000111
3 비트가 설정됩니다.
32 비트 정수에서 세트 비트 수를 결정하는 알고리즘은 무엇입니까?
이를 ' 해밍 가중치 ', '팝 카운트'또는 '옆으로 더하기'라고합니다.
'최상의'알고리즘은 실제로 사용중인 CPU와 사용 패턴에 따라 다릅니다.
일부 CPU에는이를 수행하기위한 단일 내장 명령어가 있고 다른 CPU에는 비트 벡터에서 작동하는 병렬 명령어가 있습니다. 병렬 명령어 (예 : x86 popcnt, 지원되는 CPU에서)는 거의 확실하게 가장 빠릅니다. 일부 다른 아키텍처에는주기 당 비트를 테스트하는 마이크로 코딩 된 루프로 구현 된 느린 명령어가있을 수 있습니다 ( 인용 필요 ).
미리 채워진 테이블 조회 방법은 CPU에 큰 캐시가 있고 / 또는 타이트한 루프에서 이러한 명령을 많이 수행하는 경우 매우 빠를 수 있습니다. 그러나 CPU가 주 메모리에서 일부 테이블을 가져와야하는 '캐시 미스'비용으로 인해 문제가 발생할 수 있습니다.
바이트가 대부분 0 또는 대부분 1이라는 것을 알고 있다면 이러한 시나리오에 대한 매우 효율적인 알고리즘이 있습니다.
나는 아주 좋은 범용 알고리즘이 '병렬'또는 '가변 정밀도 SWAR 알고리즘'으로 알려진 다음과 같다고 생각합니다. 저는 이것을 C와 유사한 의사 언어로 표현했습니다. 특정 언어에서 작동하도록 조정해야 할 수도 있습니다 (예 : C ++의 경우 uint32_t, Java의 경우 >>> 사용).
int numberOfSetBits(int i)
{
// Java: use >>> instead of >>
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
이것은 논의 된 알고리즘 중 가장 최악의 경우 동작을 가지고 있으므로 사용 패턴이나 값을 효율적으로 처리합니다.
이 비트 SWAR 알고리즘은 단일 정수 레지스터 대신 한 번에 여러 벡터 요소에서 수행되도록 병렬화하여 SIMD가 있지만 사용 가능한 popcount 명령어가없는 CPU에서 속도를 높일 수 있습니다. (예 : Nehalem 이상뿐만 아니라 모든 CPU에서 실행되어야하는 x86-64 코드)
그러나 popcount에 벡터 명령어를 사용하는 가장 좋은 방법은 일반적으로 가변 셔플을 사용하여 각 바이트의 한 번에 4 비트에 대한 테이블 조회를 병렬로 수행하는 것입니다. (4 비트는 벡터 레지스터에 보관 된 16 개 항목 테이블을 인덱스합니다.)
Intel CPU에서 하드웨어 64 비트 popcnt 명령어는 SSSE3 PSHUFB비트 병렬 구현 보다 약 2 배 더 나은 성능을 발휘할 수 있지만 컴파일러가 올바르게 작동하는 경우 에만 가능합니다 . 그렇지 않으면 SSE가 훨씬 앞서 나올 수 있습니다. 최신 컴파일러 버전은 Intel 의 popcnt 거짓 종속성 문제를 알고 있습니다.
참조 :
https://graphics.stanford.edu/~seander/bithacks.html
https://en.wikipedia.org/wiki/Hamming_weight
http://gurmeet.net/puzzles/fast-bit-counting-routines/
http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)
또한 컴파일러의 내장 함수를 고려하십시오.
예를 들어 GNU 컴파일러에서는 다음을 사용할 수 있습니다.
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
최악의 경우 컴파일러는 함수에 대한 호출을 생성합니다. 최상의 경우 컴파일러는 동일한 작업을 더 빠르게 수행하기 위해 cpu 명령을 내 보냅니다.
GCC 내장 함수는 여러 플랫폼에서도 작동합니다. Popcount는 x86 아키텍처에서 주류가 될 것이므로 지금부터 내장 함수를 사용하는 것이 좋습니다. 다른 아키텍처는 수년간 팝 카운트를 가지고 있습니다.
x86에서는 컴파일러에게 popcnt명령에 대한 지원을 가정 -mpopcnt하거나 -msse4.2동일한 세대에 추가 된 벡터 명령을 활성화 할 수 있음을 알릴 수 있습니다 . GCC x86 옵션을 참조하십시오 . -march=nehalem(또는 -march=코드가 가정하고 조정하려는 CPU)가 좋은 선택이 될 수 있습니다. 결과 바이너리를 이전 CPU에서 실행하면 잘못된 명령 오류가 발생합니다.
바이너리를 빌드하는 머신에 최적화하려면 -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컴파일 타임에 지원 을 활성화 할 수있는 방법이 없으며를 사용 하더라도 항상 테이블 조회를 사용 합니다/Ox /arch:AVX (기술적으로에 대한 별도의 기능 비트가 있지만 SSE4.2를 의미 함 popcnt).
그러나 적어도 어디에서나 작동하는 이식 가능한 것을 얻고 올바른 대상 옵션이있는 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 에는 좋지 않습니다 .
제 생각에 "최상의"솔루션은 다른 프로그래머 (또는 2 년 후 원래 프로그래머)가 많은 의견없이 읽을 수있는 솔루션입니다. 일부가 이미 제공 한 가장 빠르고 영리한 솔루션을 원할 수도 있지만 언제든지 영리함보다 가독성을 선호합니다.
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);
}
이들은 특정 데이터 유형 크기에 의존하므로 이식성이 떨어집니다. 그러나 많은 성능 최적화는 어쨌든 이식 가능하지 않기 때문에 문제가되지 않을 수 있습니다. 이식성을 원한다면 읽기 쉬운 솔루션을 고수 할 것입니다.
Hacker 's Delight, p. 66, 그림 5-2
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;
}
~ 20-ish 명령어 (아치에 따라 다름)에서 실행되며 분기는 없습니다.
Hacker 's Delight 는 즐겁습니다! 추천.
룩업 테이블과 popcount 를 사용하지 않는 가장 빠른 방법 은 다음과 같습니다. 단지 12 개의 작업으로 설정된 비트를 계산합니다.
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;
}
두 개의 반으로 나누고 두 반쪽의 세트 비트 수를 세고 더하여 총 세트 비트 수를 계산할 수 있기 때문에 작동합니다. Divide and Conquer패러다임 이라고도합니다 . 자세히 알아 보겠습니다 ..
v = v - ((v >> 1) & 0x55555555);
2 비트의 비트 수는 0b00, 0b01또는 일 수 있습니다 0b10. 이 문제를 2 비트에서 해결해 보겠습니다 ..
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
이것이 필요한 것입니다. 마지막 열에는 2 비트 쌍마다 설정된 비트 수가 표시됩니다. 두 개의 비트 번호 인 경우 >= 2 (0b10)다음 and생산하고 0b01, 다른 사람이 생산 0b00.
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
이 문장은 이해하기 쉬워야합니다. 첫 번째 작업 후에는 2 비트마다 설정된 비트 수가 있으므로 이제 4 비트마다 해당 개수를 합산합니다.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
그런 다음 위의 결과를 합산하여 4 비트의 총 세트 비트 수를 제공합니다. 마지막 진술이 가장 까다 롭습니다.
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
좀 더 자세히 살펴 보겠습니다 ...
v + (v >> 4)
두 번째 문장과 비슷합니다. 대신 4 개의 그룹으로 설정된 비트를 계산합니다. 이전 작업으로 인해 모든 니블에 세트 비트 수가 있음을 알고 있습니다. 예를 살펴 보겠습니다. byte가 있다고 가정합니다 0b01000010. 이는 첫 번째 니블에 4 비트 세트가 있고 두 번째 니블에 2 비트 세트가 있음을 의미합니다. 이제 우리는 그 니블을 함께 추가합니다.
0b01000010 + 0b01000000
첫 번째 니블에서 바이트의 세트 비트 수를 제공 0b01100010하므로 숫자에있는 모든 바이트의 마지막 4 바이트를 마스킹합니다 (삭제).
0b01100010 & 0xF0 = 0b01100000
이제 모든 바이트에는 세트 비트 수가 있습니다. 우리는 그것들을 모두 합쳐야합니다. 요령은 0b10101010흥미로운 속성을 가진 결과를 곱하는 것 입니다. 숫자가 4 바이트 인 경우이 바이트 A B C D가 포함 된 새 숫자가 생성됩니다 A+B+C+D B+C+D C+D D. 4 바이트 숫자는 최대 32 비트를 설정할 수 있으며 0b00100000.
이제 필요한 것은 모든 바이트의 모든 세트 비트의 합계를 갖는 첫 번째 바이트이며 >> 24. 이 알고리즘은 32 bit단어 용으로 설계 되었지만 단어 용 으로 쉽게 수정할 수 있습니다 64 bit.
지루 해졌고 세 가지 접근 방식을 10 억 번 반복했습니다. 컴파일러는 gcc -O3입니다. CPU는 1 세대 Macbook Pro에 넣은 것입니다.
가장 빠른 속도는 3.7 초입니다.
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] );
}
두 번째 장소는 동일한 코드이지만 2 개의 하프 워드 대신 4 바이트를 찾습니다. 약 5.5 초가 걸렸습니다.
3 위는 8.6 초가 걸린 비트 뒤틀기 '옆으로 더하기'접근 방식입니다.
4 위는 11 초에 GCC의 __builtin_popcount ()입니다.
한 번에 1 비트를 계산하는 방법은 너무 느 렸고 완료되기를 기다리는 것이 지루했습니다.
따라서 무엇보다도 성능에 관심이 있다면 첫 번째 접근 방식을 사용하십시오. 관심이 있지만 64Kb의 RAM을 사용하기에 충분하지 않은 경우 두 번째 방법을 사용하십시오. 그렇지 않으면 읽기 쉬운 (그러나 느린) 한 번에 1 비트 접근 방식을 사용하십시오.
비트 트위들 링 방식을 사용하고 싶은 상황을 생각하기가 어렵습니다.
편집 : 유사한 결과가 여기에 있습니다 .
Java를 사용하는 경우 내장 메서드 Integer.bitCount가이를 수행합니다.
unsigned int count_bit(unsigned int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
return x;
}
이 알고리즘을 설명하겠습니다.
이 알고리즘은 Divide and Conquer Algorithm을 기반으로합니다. 8 비트 정수 213 (2 진수 11010101)이 있다고 가정하면 알고리즘은 다음과 같이 작동합니다 (매번 두 개의 이웃 블록을 병합).
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
이것은 마이크로 아키텍처를 아는 데 도움이되는 질문 중 하나입니다. 함수 호출 오버 헤드, 10 억 반복을 제거하기 위해 C ++ 인라인을 사용하여 -O3으로 컴파일 된 gcc 4.3.3에서 두 가지 변형을 시간을 측정하여 컴파일러가 중요한 것을 제거하지 않도록 모든 카운트의 실행 합계를 유지하고 타이밍에 rdtsc를 사용합니다 ( 정확한 클록주기).
인라인 int pop2 (부호없는 x, 부호없는 y)
{
x = x-((x >> 1) & 0x55555555);
y = y-((y >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
y = y + (y >> 8);
x = x + (x >> 16);
y = y + (y >> 16);
반환 (x + y) & 0x000000FF;
}
수정되지 않은 Hacker 's Delight는 12.2 기가 사이클이 걸렸습니다. 내 병렬 버전 (비트 수의 두 배)은 13.0 기가 사이클로 실행됩니다. 2.4GHz Core Duo에서 모두 총 10.5 초가 경과했습니다. 25 기가 사이클 =이 클럭 주파수에서 10 초가 조금 넘기 때문에 타이밍이 맞다고 확신합니다.
이것은이 알고리즘에 매우 나쁜 명령 종속성 체인과 관련이 있습니다. 64 비트 레지스터 쌍을 사용하면 속도를 거의 두 배로 늘릴 수 있습니다. 사실, 내가 영리하고 x + ya를 조금 더 빨리 추가하면 교대 시간을 줄일 수 있습니다. 약간의 조정이있는 64 비트 버전은 균등하게 나오지만 다시 두 배로 계산됩니다.
128 비트 SIMD 레지스터와 함께 또 다른 요소 2와 SSE 명령어 세트도 종종 영리한 지름길을가집니다.
코드가 특히 투명 할 이유가 없습니다. 인터페이스는 간단하고 알고리즘은 여러 곳에서 온라인으로 참조 할 수 있으며 포괄적 인 단위 테스트를 수행 할 수 있습니다. 그것을 우연히 발견 한 프로그래머는 무언가를 배울 수도 있습니다. 이러한 비트 작업은 기계 수준에서 매우 자연 스럽습니다.
좋아, 나는 조정 된 64 비트 버전을 벤치마킹하기로 결정했다. 이 하나의 sizeof (unsigned long) == 8
인라인 int pop2 (unsigned long x, unsigned long y)
{
x = x-((x >> 1) & 0x5555555555555555);
y = y-((y >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + y;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
반환 x & 0xFF;
}
그것은 옳은 것 같습니다 (하지만 신중하게 테스트하지는 않습니다). 이제 타이밍이 10.70 기가 사이클 /14.1 기가 사이클로 나옵니다. 이후의 숫자는 1,280 억 비트를 합산했으며이 시스템에서 경과 한 5.9 초에 해당합니다. 비 병렬 버전은 내가 64 비트 모드에서 실행 중이고 32 비트 레지스터보다 64 비트 레지스터를 약간 더 좋아하기 때문에 약간의 속도가 빨라집니다.
여기에 더 많은 OOO 파이프 라인이 있는지 보자. 이것은 조금 더 복잡했기 때문에 실제로 약간 테스트했습니다. 각 항만 합하면 64가되고 모두 합쳐지면 256이됩니다.
인라인 int pop4 (unsigned long x, unsigned long y,
부호없는 long u, 부호없는 long v)
{
열거 형 {m1 = 0x5555555555555555,
m2 = 0x3333333333333333,
m3 = 0x0F0F0F0F0F0F0F0F,
m4 = 0x000000FF000000FF};
x = x-((x >> 1) & m1);
y = y-((y >> 1) & m1);
u = u-((u >> 1) & m1);
v = v-((v >> 1) & m1);
x = (x & m2) + ((x >> 2) & m2);
y = (y & m2) + ((y >> 2) & m2);
u = (u & m2) + ((u >> 2) & m2);
v = (v & m2) + ((v >> 2) & m2);
x = x + y;
u = u + v;
x = (x & m3) + ((x >> 4) & m3);
u = (u & m3) + ((u >> 4) & m3);
x = x + u;
x = x + (x >> 8);
x = x + (x >> 16);
x = x & m4;
x = x + (x >> 32);
반환 x & 0x000001FF;
}
나는 잠시 흥분했지만 gcc는 일부 테스트에서 inline 키워드를 사용하지 않더라도 -O3와 함께 인라인 트릭을 수행하는 것으로 나타났습니다. gcc가 트릭을하게했을 때 pop4 ()에 대한 10 억 번의 호출은 12.56 기가 사이클이 걸리지 만 인수를 상수 표현식으로 접는다는 것을 확인했습니다. 더 현실적인 수치는 30 % 속도 향상을 위해 19.6gc 인 것으로 보입니다. 내 테스트 루프는 이제 다음과 같이 보입니다. 각 인수가 gcc가 트릭을 수행하지 못하도록 충분히 다른지 확인합니다.
hitime b4 = rdtsc ();
for (부호없는 long i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i)
합계 + = pop4 (i, i ^ 1, ~ i, i | 1);
hitime e4 = rdtsc ();
8.17 초에 합산 된 256 억 비트가 경과했습니다. 16 비트 테이블 조회에서 벤치마킹 한대로 3,200 만 비트에 대해 1.02 초로 작동합니다. 다른 벤치는 클럭 속도를 제공하지 않기 때문에 직접 비교할 수는 없지만 처음에 L1 캐시를 비극적으로 사용하는 64KB 테이블 에디션에서 콧물을 뽑은 것처럼 보입니다.
업데이트 : 4 개의 중복 된 줄을 더 추가하여 분명한 작업을 수행하고 pop6 ()을 만들기로 결정했습니다. 22.8gc로 나왔고, 9.5 초에 총 3,840 억 비트가 경과했습니다. 32 억 비트에 대해 800ms에서 또 다른 20 %가 있습니다.
반복적으로 2로 나누지 않는 이유는 무엇입니까?
개수 = 0
n> 0 인 동안
만약 (n % 2) == 1
카운트 + = 1
n / = 2
나는 이것이 가장 빠르지는 않다는 데 동의하지만 "최고"는 다소 모호합니다. "최고"는 명확성의 요소를 가져야하지만
Hacker 's Delight 비트 트위들 링은 비트 패턴을 작성할 때 훨씬 더 명확 해집니다.
unsigned int bitCount(unsigned int x)
{
x = ((x >> 1) & 0b01010101010101010101010101010101)
+ (x & 0b01010101010101010101010101010101);
x = ((x >> 2) & 0b00110011001100110011001100110011)
+ (x & 0b00110011001100110011001100110011);
x = ((x >> 4) & 0b00001111000011110000111100001111)
+ (x & 0b00001111000011110000111100001111);
x = ((x >> 8) & 0b00000000111111110000000011111111)
+ (x & 0b00000000111111110000000011111111);
x = ((x >> 16)& 0b00000000000000001111111111111111)
+ (x & 0b00000000000000001111111111111111);
return x;
}
첫 번째 단계에서는 홀수 비트에 짝수 비트를 더하여 각각의 비트 합계를 생성합니다. 다른 단계는 하위 청크에 고차 청크를 추가하여 최종 개수가 전체 정수를 차지할 때까지 청크 크기를 두 배로 늘립니다.
2 32 조회 테이블과 각 비트를 개별적으로 반복 하는 행복한 매체 :
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
에서 http://ctips.pbwiki.com/CountBits
이것은 수행 될 수있는 O(k)경우, k설정 비트 수이다.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
가장 빠르거나 최선의 해결책은 아니지만 제 방식으로 같은 질문을 발견하고 생각하고 생각하기 시작했습니다. 드디어 수학적 측면에서 문제를 꺼내 그래프를 그리면 이렇게 할 수 있다는 것을 깨달았습니다. 그러면 그것이주기적인 부분을 가진 함수라는 것을 알게되고, 그리고 당신은주기의 차이를 깨닫게됩니다. 여기 있습니다 :
unsigned int f(unsigned int x)
{
switch (x) {
case 0:
return 0;
case 1:
return 1;
case 2:
return 1;
case 3:
return 2;
default:
return f(x/4) + f(x%4);
}
}
찾고있는 함수를 이진수의 "가로 합"또는 "모집단 수"라고합니다. Knuth는이를 Fascicle 1A 이전, pp11-12에서 논의합니다 (Volume 2, 4.6.3- (7)에 간략한 참조가 있었음에도 불구하고).
궤적 classicus이 로부터 피터 웨 그너의 기사 "이진 컴퓨터의 계산 방식 사람을위한 기술"이다 ACM의 커뮤니케이션 , 제 3 권 (1960) 번호 5, 322 페이지 . 그는 거기에 두 개의 다른 알고리즘을 제공하는데, 하나는 "희소"로 예상되는 숫자 (즉, 적은 수를 가짐)에 최적화 된 알고리즘과 반대의 경우에 대한 알고리즘입니다.
몇 가지 공개 질문 :-
- 숫자가 음수이면?
- 숫자가 1024이면 "반복적으로 2로 나누기"방법이 10 번 반복됩니다.
다음과 같이 음수를 지원하도록 algo를 수정할 수 있습니다.
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
이제 두 번째 문제를 극복하기 위해 다음과 같이 알고리즘을 작성할 수 있습니다.
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
전체 참조는 다음을 참조하십시오.
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
private int get_bits_set(int v)
{
int c; // c accumulates the total bits set in v
for (c = 0; v>0; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c;
}
Brian Kernighan의 방법도 유용 할 것이라고 생각합니다 . 설정된 비트 수만큼 반복됩니다. 따라서 상위 비트 세트 만있는 32 비트 워드가 있으면 루프를 한 번만 통과합니다.
int countSetBits(unsigned int n) {
unsigned int n; // count the number of bits set in n
unsigned int c; // c accumulates the total bits set in n
for (c=0;n>0;n=n&(n-1)) c++;
return c;
}
1988 년에 출판 된 C 프로그래밍 언어 2nd Ed. (Brian W. Kernighan 및 Dennis M. Ritchie 작성) 연습 2-9에서이를 언급합니다. 2006 년 4 월 19 일 Don Knuth는이 방법이 "CACM 3 (1960), 322에서 Peter Wegner에 의해 처음 출판되었습니다. (또한 Derrick Lehmer에 의해 독립적으로 발견되었고 1964 년에 Beckenbach가 편집 한 책으로 출판되었습니다.)"라고 저에게 지적했습니다.
더 직관적 인 아래 코드를 사용합니다.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
논리 : n & (n-1)은 n의 마지막 설정 비트를 재설정합니다.
추신 : 흥미로운 해결책이기는하지만 이것이 O (1) 해결책이 아니라는 것을 알고 있습니다.
"최고의 알고리즘"이란 무엇을 의미합니까? 단축 코드 또는 금식 코드? 코드는 매우 우아하고 실행 시간이 일정합니다. 코드도 매우 짧습니다.
그러나 속도가 코드 크기가 아니라 주요 요소라면 다음이 더 빠를 수 있다고 생각합니다.
static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
static int bitCountOfByte( int value ){
return BIT_COUNT[ value & 0xFF ];
}
static int bitCountOfInt( int value ){
return bitCountOfByte( value )
+ bitCountOfByte( value >> 8 )
+ bitCountOfByte( value >> 16 )
+ bitCountOfByte( value >> 24 );
}
64 비트 값의 경우 더 빠르지는 않지만 32 비트 값은 더 빠를 수 있다고 생각합니다.
나는 약 1990 년에 RISC 기계에 대한 빠른 비트 수 매크로를 작성했습니다. 고급 산술 (곱하기, 나누기, %), 메모리 가져 오기 (너무 느림), 분기 (너무 느림)를 사용하지 않지만 CPU에 32 비트 배럴 시프터 (즉, >> 1 및 >> 32는 같은 양의 사이클을 사용합니다.) 작은 상수 (예 : 6, 12, 24)는 레지스터에로드하는 데 비용이 들지 않거나 저장되지 않는다고 가정합니다. 임시로 반복해서 재사용됩니다.
이러한 가정하에 대부분의 RISC 시스템에서 약 16 사이클 / 명령으로 32 비트를 계산합니다. 15 개의 명령어 / 사이클은 덧셈 수를 절반으로 줄이는 데 최소 3 개의 명령어 (마스크, 시프트, 연산자)가 필요한 것처럼 보이기 때문에 사이클 또는 명령어 수의 하한에 가깝습니다. 따라서 log_2 (32) = 5, 5 x 3 = 15 명령어는 준 하한입니다.
#define BitCount(X,Y) \
Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
Y = ((Y + (Y >> 3)) & 030707070707); \
Y = (Y + (Y >> 6)); \
Y = (Y + (Y >> 12) + (Y >> 24)) & 077;
다음은 가장 복잡한 첫 번째 단계의 비밀입니다.
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
따라서 위의 첫 번째 열 (A)을 가져 와서 오른쪽으로 1 비트 이동하고 AB에서 빼면 출력 (CD)이 나옵니다. 3 비트로의 확장은 유사합니다. 원한다면 위와 같은 8 행 부울 테이블로 확인할 수 있습니다.
- 돈 길리스
C ++를 사용하는 경우 또 다른 옵션은 템플릿 메타 프로그래밍을 사용하는 것입니다.
// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
// return the least significant bit plus the result of calling ourselves with
// .. the shifted value
return (val & 0x1) + countBits<BITS-1>(val >> 1);
}
// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
return val & 0x1;
}
사용법은 다음과 같습니다.
// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )
// another byte (this returns 7)
countBits<8>( 254 )
// counting bits in a word/short (this returns 1)
countBits<16>( 256 )
물론이 템플릿을 추가로 확장하여 다른 유형 (비트 크기 자동 감지 포함)을 사용할 수도 있지만 명확성을 위해 간단하게 유지했습니다.
편집 : 이것은 C ++ 컴파일러에서 작동 해야 하고 기본적으로 비트 수에 상수 값이 사용되는 경우 루프를 풀기 때문에 이것이 좋습니다 (즉, 가장 빠른 일반적인 방법이라고 확신합니다 당신은 찾을 수 있습니다)
특히 포춘 파일의이 예제가 마음에 듭니다.
#BITCOUNT (x) (((BX_ (x) + (BX_ (x) >> 4)) & 0x0F0F0F0F) % 255) 정의
#define BX_ (x) ((x)-(((x) >> 1) & 0x77777777)
-(((x) >> 2) & 0x33333333)
-(((x) >> 3) & 0x11111111))
너무 예뻐서 제일 좋아요!
자바 JDK1.5
Integer.bitCount (n);
여기서 n은 1이 계산되는 숫자입니다.
또한 확인,
Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 times
n = 1;
for (int i = 0; i < 16; i++) {
n = Integer.rotateLeft(n, 1);
System.out.println(n);
}
SIMD 명령어 (SSSE3 및 AVX2)를 사용하여 배열에서 비트 계산 구현을 찾았습니다. __popcnt64 내장 함수를 사용할 때보 다 2-2.5 배 더 나은 성능을 제공합니다.
SSSE3 버전 :
#include <smmintrin.h>
#include <stdint.h>
const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m128i _sum = _mm128_setzero_si128();
for (size_t i = 0; i < size; i += 16)
{
//load 16-byte vector
__m128i _src = _mm_loadu_si128((__m128i*)(src + i));
//get low 4 bit for every byte in vector
__m128i lo = _mm_and_si128(_src, F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
}
uint64_t sum[2];
_mm_storeu_si128((__m128i*)sum, _sum);
return sum[0] + sum[1];
}
AVX2 버전 :
#include <immintrin.h>
#include <stdint.h>
const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m256i _sum = _mm256_setzero_si256();
for (size_t i = 0; i < size; i += 32)
{
//load 32-byte vector
__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
//get low 4 bit for every byte in vector
__m256i lo = _mm256_and_si256(_src, F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
}
uint64_t sum[4];
_mm256_storeu_si256((__m256i*)sum, _sum);
return sum[0] + sum[1] + sum[2] + sum[3];
}
나는 항상 경쟁 프로그래밍에서 이것을 사용하며 작성하기 쉽고 효율적입니다.
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
설정된 비트를 계산하는 많은 알고리즘이 있습니다. 하지만 가장 좋은 것이 더 빠른 것 같아요! 이 페이지에서 자세한 내용을 볼 수 있습니다.
나는 이것을 제안한다 :
64 비트 명령어를 사용하여 14, 24 또는 32 비트 단어로 설정된 비트 계산
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
// option 2, for at most 24-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;
// option 3, for at most 32-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
이 방법을 사용하려면 빠른 모듈러스 분할이있는 64 비트 CPU가 필요합니다. 첫 번째 옵션은 3 개의 작업 만 수행합니다. 두 번째 옵션은 10입니다. 세 번째 옵션은 15입니다.
입력 크기에 대한 분기와 함께 미리 계산 된 바이트 비트 수 테이블을 사용하는 빠른 C # 솔루션입니다.
public static class BitCount
{
public static uint GetSetBitsCount(uint n)
{
var counts = BYTE_BIT_COUNTS;
return n <= 0xff ? counts[n]
: n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
: n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
: counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
}
public static readonly uint[] BYTE_BIT_COUNTS =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
}
다음은 모든 아키텍처에서 각 알고리즘을 벤치마킹 할 수있는 휴대용 모듈 (ANSI-C)입니다.
CPU에 9 비트 바이트가 있습니까? 문제 없습니다 :-) 현재 K & R 알고리즘과 바이트 단위 조회 테이블이라는 두 가지 알고리즘을 구현합니다. 조회 테이블은 K & R 알고리즘보다 평균 3 배 더 빠릅니다. 누군가 "Hacker 's Delight"알고리즘을 이식 가능하게 만드는 방법을 알아낼 수 있다면 자유롭게 추가하십시오.
#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );
/* List of available bitcount algorithms.
* onTheFly: Calculate the bitcount on demand.
*
* lookupTalbe: Uses a small lookup table to determine the bitcount. This
* method is on average 3 times as fast as onTheFly, but incurs a small
* upfront cost to initialize the lookup table on the first call.
*
* strategyCount is just a placeholder.
*/
enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */
extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );
#endif
.
#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique
* values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {
int count;
/* Starting with:
* 1100 - 1 == 1011, 1100 & 1011 == 1000
* 1000 - 1 == 0111, 1000 & 0111 == 0000
*/
for ( count = 0; val; ++count )
val &= val - 1;
return count;
}
/* Looks up each byte of the integer in a lookup table.
*
* The first time the function is called it initializes the lookup table.
*/
static int _tableBitCount( unsigned int val ) {
int bCount = 0;
if ( !_lookupTableInitialized ) {
unsigned int i;
for ( i = 0; i != UCHAR_MAX + 1; ++i )
_bitCountTable[i] =
( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;
}
for ( ; val; val >>= CHAR_BIT )
bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;
}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {
switch ( s ) {
case onTheFly:
_bitcount = _defaultBitCount;
break;
case lookupTable:
_bitcount = _tableBitCount;
break;
case strategyCount:
break;
}
}
/* Just a forwarding function which will call whichever version of the
* algorithm has been selected by the client
*/
int bitcount( unsigned int val ) {
return _bitcount( val );
}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming
* Weight algorithm.
*/
void benchmark( int reps ) {
clock_t start, stop;
int i, j;
static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {
setStrategy( j );
srand( 257 );
start = clock( );
for ( i = 0; i != reps * iterations; ++i )
bitcount( rand( ) );
stop = clock( );
printf
( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
reps * iterations, strategyNames[j],
( double )( stop - start ) / CLOCKS_PER_SEC );
}
}
int main( void ) {
int option;
while ( 1 ) {
printf( "Menu Options\n"
"\t1.\tPrint the Hamming Weight of an Integer\n"
"\t2.\tBenchmark Hamming Weight implementations\n"
"\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )
break;
switch ( option ) {
case 1:
printf( "Please enter the integer: " );
if ( scanf( "%d", &option ) != EOF )
printf
( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
option, option, bitcount( option ) );
break;
case 2:
printf
( "Please select number of reps ( in millions ): " );
if ( scanf( "%d", &option ) != EOF )
benchmark( option );
break;
case 3:
goto EXIT;
break;
default:
printf( "Invalid option\n" );
}
}
EXIT:
printf( "\n" );
return 0;
}
#endif
32 비트 여부? 저는 자바로이 방법을 " 코딩 인터뷰 크래킹 "4th edition exercice 5.5 (chap 5 : Bit Manipulation)를 읽은 후에 왔습니다 . 최하위 비트가 1 increment count이면 정수를 오른쪽으로 이동합니다.
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
나는 이것이 아무리 빠르더라도 상수 0x33333333을 가진 솔루션보다 더 직관적이라고 생각합니다. "최고의 알고리즘"에 대한 정의에 따라 다릅니다.
참고 URL : https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer
'Development Tip' 카테고리의 다른 글
| 명령 줄에서 MongoDB 데이터베이스를 삭제하려면 어떻게해야합니까? (0) | 2020.09.28 |
|---|---|
| 루비의 클래스 << 자기 관용구 (0) | 2020.09.28 |
| ASP.NET 웹 사이트 또는 ASP.NET 웹 응용 프로그램? (0) | 2020.09.28 |
| 파이썬에서 "명명 된 튜플"이란 무엇입니까? (0) | 2020.09.28 |
| sudo를 사용하여 쓰기 권한이없는 위치로 출력을 리디렉션하려면 어떻게해야합니까? (0) | 2020.09.28 |