32비트 정수에서 설정된 비트 수를 계산하는 방법은 무엇입니까?
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
숫자 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가 있지만 사용 가능한 팝카운트 명령이 없는 CPU의 속도 향상을 위해 단일 정수 레지스터 대신 여러 벡터 요소에서 동시에 수행되도록 병렬화할 수 있습니다.(예:Nehalem 이상뿐만 아니라 모든 CPU에서 실행되어야 하는 x86-64 코드입니다.)
그러나 팝카운트에 벡터 명령을 사용하는 가장 좋은 방법은 일반적으로 변수 셔플을 사용하여 각 바이트의 한 번에 4비트에 대한 테이블 조회를 병렬로 수행하는 것입니다.(4비트는 벡터 레지스터에 보관된 16개 항목 테이블을 색인화합니다).
Intel CPU에서는 하드웨어 64비트 popcnt 명령이 다른 명령보다 성능이 뛰어날 수 있습니다. SSSE3 PSHUFB 비트 병렬 구현 약 2배 정도 차이가 나지만, 컴파일러가 제대로 작동한다면.그렇지 않으면 SSE가 훨씬 앞서 나갈 수 있습니다.최신 컴파일러 버전에서는 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에 대해 효율적으로 팝카운트하는 방법을 아는 컴파일러는 ISO C++를 통해 해당 기능을 노출해야 합니다. std::bitset<>.실제로 일부 대상 CPU의 경우에는 비트 해킹 AND/shift/ADD를 사용하는 것이 더 나을 수도 있습니다.
하드웨어 팝카운트가 선택적 확장(예: x86)인 대상 아키텍처의 경우 모든 컴파일러에 std::bitset 가능한 경우 이를 활용합니다.예를 들어 MSVC에는 활성화할 방법이 없습니다. popcnt 컴파일 타임에 지원하며 항상 사용합니다. 테이블 조회, 심지어 /Ox /arch:AVX (기술적으로 SSE4.2에 대한 별도의 기능 비트가 있지만 이는 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();
}
보다 gcc, clang, icc 및 MSVC의 asm Godbolt 컴파일러 탐색기에서.
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
파워PC64 gcc -O3 -std=gnu++11 (을 위해) 방출 int 인수 버전):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
이 소스는 x86 특정 또는 GNU 특정이 아니지만 gcc/clang/icc를 사용하는 x86에 대해서만 잘 컴파일됩니다.
또한 단일 명령어 팝카운트가 없는 아키텍처에 대한 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가지 명령어(아치에 따라 다름)로 실행됩니다.
해커의 기쁨 ~이다 매우 기쁜!추천.
내 생각에 가장 빠른 방법은 조회 테이블을 사용하지 않고 팝카운트—다음입니다.단 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);
두 비트의 비트 수는 다음과 같습니다. 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개의 그룹으로 설정된 비트를 계산합니다.우리는 이전 작업으로 인해 모든 니블에 설정된 비트 수가 있다는 것을 알고 있습니다.예를 살펴보겠습니다.우리가 바이트를 가지고 있다고 가정하자 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 단어.
Java를 사용하는 경우 내장 메소드 Integer.bitCount 그렇게 할 것입니다.
나는 지루해졌고 세 가지 접근 방식을 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위는 GCC의 __builtin_popcount()로 부끄러운 11초를 기록했습니다.
한 번에 한 비트씩 계산하는 접근 방식은 엄청나게 느리고 완료될 때까지 기다리는 것이 지루해졌습니다.
따라서 무엇보다도 성능에 관심이 있다면 첫 번째 접근 방식을 사용하십시오.관심이 있지만 64Kb의 RAM을 사용할 만큼 충분하지 않은 경우 두 번째 접근 방식을 사용하십시오.그렇지 않으면 읽기 가능하지만 느린) 한 번에 한 비트 접근 방식을 사용하십시오.
조금 뒤죽박죽 접근 방식을 사용하고 싶은 상황을 생각하기는 어렵습니다.
편집하다:비슷한 결과 여기.
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;
}
이 알고리즘을 설명하겠습니다.
이 알고리즘은 분할 정복 알고리즘을 기반으로 합니다.8비트 정수 213(이진수로 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를 사용합니다( 정확한 클럭 주기).
inline int pop2(unsigned x, unsigned 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);
return (x+y) & 0x000000FF;
}
수정되지 않은 Hacker's Delight는 12.2기가사이클을 소비했습니다.내 병렬 버전(두 배의 비트로 계산)은 13.0기가사이클에서 실행됩니다.2.4GHz Core Duo에서 두 가지 모두 총 10.5초가 경과했습니다.25기가사이클 = 이 클럭 주파수에서는 10초가 조금 넘으므로 타이밍이 맞다고 확신합니다.
이는 이 알고리즘에 매우 나쁜 명령 종속성 체인과 관련이 있습니다.한 쌍의 64비트 레지스터를 사용하여 속도를 다시 거의 두 배로 높일 수 있었습니다.사실, 내가 영리하게 x+y를 조금 더 빨리 추가했다면 약간의 교대근무를 줄일 수 있었습니다.약간의 수정을 가한 64비트 버전은 대략 균등하게 나오지만 비트 수는 다시 두 배로 계산됩니다.
128비트 SIMD 레지스터를 사용하면 또 다른 2배의 요소와 SSE 명령어 세트에도 영리한 단축키가 있는 경우가 많습니다.
코드가 특별히 투명할 이유는 없습니다.인터페이스는 간단하고 알고리즘은 온라인 여러 곳에서 참조할 수 있으며 포괄적인 단위 테스트가 가능합니다.우연히 그것을 발견한 프로그래머는 뭔가를 배울 수도 있습니다.이러한 비트 작업은 기계 수준에서 매우 자연스럽습니다.
좋아, 나는 조정된 64비트 버전을 벤치마킹하기로 결정했습니다.이 단일 sizeof(unsigned long) == 8
inline 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);
return x & 0xFF;
}
그 말이 맞는 것 같습니다(하지만 주의 깊게 테스트하지는 않았습니다).이제 타이밍은 10.70기가사이클/14.1기가사이클로 나옵니다.그 이후의 숫자는 총 1,280억 비트에 달하며 이 시스템에서 경과된 5.9초에 해당합니다.비병렬 버전은 64비트 모드에서 실행 중이고 32비트 레지스터보다 64비트 레지스터를 약간 더 좋아하기 때문에 속도가 약간 향상됩니다.
여기에 OOO 파이프라인이 좀 더 있는지 살펴보겠습니다.이것은 좀 더 복잡해서 실제로 약간 테스트했습니다.각 항의 합은 64이고 모두 합하면 256입니다.
inline int pop4(unsigned long x, unsigned long y,
unsigned long u, unsigned long v)
{
enum { 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);
return x & 0x000001FF;
}
잠시 흥분했지만 일부 테스트에서 inline 키워드를 사용하지 않았음에도 불구하고 gcc가 -O3을 사용하여 인라인 트릭을 실행하고 있는 것으로 나타났습니다.gcc에서 트릭을 실행하게 하면 pop4()에 대한 10억 호출에 12.56기가사이클이 걸리지만 인수를 상수 표현식으로 접는 것이라고 판단했습니다.보다 현실적인 수치는 30%의 추가 속도 향상을 위한 19.6gc인 것으로 보입니다.내 테스트 루프는 이제 다음과 같으며, 각 인수가 gcc가 트릭을 수행하는 것을 막을 수 있을 만큼 충분히 다른지 확인합니다.
hitime b4 = rdtsc();
for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
sum += pop4 (i, i^1, ~i, i|1);
hitime e4 = rdtsc();
8.17초 동안 합산된 2,560억 비트가 경과되었습니다.16비트 테이블 조회에서 벤치마킹된 대로 3,200만 비트에 대해 1.02초로 작동합니다.다른 벤치에서는 클럭 속도를 제공하지 않기 때문에 직접 비교할 수는 없지만 L1 캐시를 비극적으로 사용하는 64KB 테이블 에디션에서 콧물을 흘린 것처럼 보입니다.
업데이트:명백한 작업을 수행하고 네 개의 중복된 줄을 더 추가하여 pop6()을 만들기로 결정했습니다.22.8gc로 나왔는데, 9.5초에 합산된 3,840억 비트가 경과되었습니다.따라서 320억 비트에 대해 800ms에 또 다른 20%가 있습니다.
왜 반복적으로 2로 나누지 않습니까?
count = 0
while n > 0
if (n % 2) == 1
count += 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;
}
첫 번째 단계에서는 짝수 비트를 홀수 비트에 추가하여 두 비트의 합을 생성합니다.다른 단계에서는 상위 청크를 하위 청크에 추가하여 전체 int를 차지하는 최종 개수를 얻을 때까지 청크 크기를 두 배로 늘립니다.
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;
}
가장 빠르거나 최선의 해결책은 아니지만, 내 방식대로 같은 질문을 발견하고 고민하기 시작했습니다.마침내 나는 수학적 측면에서 문제를 풀고 그래프를 그리면 이것이 주기적인 부분을 갖는 함수임을 발견하고 주기 사이의 차이를 깨닫는다면 이렇게 할 수 있다는 것을 깨달았습니다.그럼 여기 있습니다:
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);
}
}
이 작업은 다음에서 수행할 수 있습니다. O(k), 어디 k 설정된 비트 수입니다.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
찾고 있는 함수는 종종 이진수의 "횡합" 또는 "인구 수"라고 합니다.Knuth는 Fascicle 1A 이전, pp11-12에서 이에 대해 논의했습니다(Volume 2, 4.6.3-(7)에 간략한 참조가 있었지만).
그만큼 궤적 고전 Peter Wegner의 기사 "A Technique for Counting Ones in a Binary Computer"는 다음과 같습니다. ACM의 통신, 3권(1960) 5호, 322페이지.그는 거기에 두 가지 다른 알고리즘을 제공합니다. 하나는 "희소"(즉, 적은 수의 숫자를 가짐)할 것으로 예상되는 숫자에 최적화된 것이고 다른 하나는 반대의 경우입니다.
몇 가지 공개 질문:-
- 숫자가 음수라면?
- 숫자가 1024 이면 "반복적으로 2로 나누기" 방법이 10번 반복됩니다.
다음과 같이 음수를 지원하도록 알고리즘을 수정할 수 있습니다.
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;
}
내 생각 엔 브라이언 커니건의 방법도 유용할 것 같아요...설정된 비트 수만큼 반복됩니다.따라서 상위 비트만 설정된 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 프로그래밍 언어 2판.(브라이언 W.커니건과 데니스 M.Ritchie)는 연습 2-9에서 이를 언급했습니다.2006년 4월 19일 Don Knuth는 이 방법이 Peter Wegner에 의해 CACM 3(1960), 322에서 처음 출판되었다고 나에게 지적했습니다.(또한 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++ 컴파일러에서 작동하며 비트 수에 상수 값이 사용되는 경우 기본적으로 루프가 풀립니다. (즉, 이것이 당신이 찾을 수 있는 가장 빠른 일반적인 방법이라고 확신합니다)
나는 특히 포춘 파일에 있는 다음 예를 좋아합니다.
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
너무 예뻐서 제일 맘에 들어요!
자바 JDK1.5
정수.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 알고리즘과 바이트별 조회 테이블이라는 2가지 알고리즘을 구현하고 있습니다.조회 테이블은 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비트인가요?"를 읽은 후 방금 Java에서 이 방법을 사용했습니다.코딩 인터뷰 크래킹" 4판 연습 5.5(5장:비트 조작).최하위 비트가 1 증분인 경우 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을 사용하는 솔루션보다 더 직관적이라고 생각합니다."최고의 알고리즘"에 대한 정의에 따라 다릅니다.
