설정된 최하위 비트 위치
정수로 설정된 최하위 비트의 위치를 효율적으로 결정할 방법을 찾고 있습니다. 예를 들어 0x0FF0의 경우 4가 됩니다.
간단한 구현은 다음과 같습니다.
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
어떻게 사이클을 짜낼지 생각나는 거 없어?
(주의: 이 질문은 그런 것을 즐기는 사람들을 위한 것이지, xyzzoptimization이 나쁘다고 말하는 사람들을 위한 것이 아닙니다.
[편집] 아이디어 감사합니다!다른 것도 몇 가지 배웠어요그러자!
Bit Twiddling Hacks는 성능/최적화에 대한 논의를 첨부하여 우수한 비트 Twiddling Hacks 컬렉션을 제공합니다.제가 가장 좋아하는 문제 해결 방법은 (그 사이트에서) "다중화 및 검색"입니다.
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
참고 자료:
- "De Bruijn Sequences to Index a Computer Word" (브루인 시퀀스를 사용하여 컴퓨터 워드의 1을 색인화) - 상기 코드가 작동하는 이유에 대해 설명합니다.
- "Board Representation" > "Bitboards" > "BitScan" - 체스 프로그래밍에 특히 초점을 맞춘 이 문제의 상세 분석
대부분의 현대 아키텍처에는 가장 낮은 세트비트 또는 가장 높은 세트비트의 위치를 찾거나 선행 0의 수를 세는 등의 명령이 있습니다.
이 수업의 한 가지 교육만 있으면 다른 수업들을 저렴하게 모방할 수 있다.
을 내어 , 그 사실을 .x & (x-1)x 내의 가장 x 는 x 의 설정 비트를 클리어 합니다.( x & ~(x-1) )아키텍처, 워드 길이 등에 관계없이 가장 낮은 설정 비트만 반환합니다.이를 알기 위해 하드웨어 count-leading-zero/highest-set-bit를 사용하여 가장 낮은 설정 비트를 찾는 것은 명시적인 지시가 없는 경우 간단합니다.
관련된 하드웨어가 전혀 지원되지 않는 경우, 여기에 제시된 카운트 선두 제로 또는 비트 트위들링 해크 페이지의 카운트 선두 제로 중 하나의 멀티 앤 룩업 실장은 위의 ID를 사용하여 최저 설정 비트를 제공하도록 3차적으로 변환할 수 있으며 브랜치리스라는 장점이 있습니다.
다음은 몇 가지 솔루션을 비교한 벤치마크입니다.
제 머신은 Windows 7 64비트를 실행하는 인텔 i530 (2.9GHz)입니다.32비트 버전의 MinGW로 컴파일했습니다.
$ gcc --version
gcc.exe (GCC) 4.7.2
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop. Time = 2.91 (Original questioner)
De Bruijn multiply. Time = 1.16 (Tykhyy)
Lookup table. Time = 0.36 (Andrew Grant)
FFS instruction. Time = 0.90 (ephemient)
Branch free mask. Time = 3.48 (Dan / Jim Balter)
Double hack. Time = 3.41 (DocMax)
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop. Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table. Time = 0.35
FFS instruction. Time = 0.68
Branch free mask. Time = 3.49
Double hack. Time = 0.92
내 코드:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 65536
#define NUM_ITERS 5000 // Number of times to process array
int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
if (value == 0)
continue;
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
total += pos + 1;
}
}
return total;
}
int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
static const int MultiplyDeBruijnBitPosition[32] =
{
1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
};
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int c = nums[i];
total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
}
}
return total;
}
unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
unsigned mask = 1;
for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
if (num & mask) {
return cnt;
}
}
return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int value = nums[i];
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
unsigned char *bytes = (unsigned char *)&value;
if (bytes[0])
total += lowestBitTable[bytes[0]];
else if (bytes[1])
total += lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
total += lowestBitTable[bytes[2]] + 16;
else
total += lowestBitTable[bytes[3]] + 24;
}
}
return total;
}
int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
total += __builtin_ffs(nums[i]);
}
}
return total;
}
int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
}
}
return total;
}
int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
double d = value ^ (value - !!value);
total += (((int*)&d)[1]>>20)-1022;
}
}
return total;
}
int main() {
unsigned nums[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++) {
nums[i] = rand() + (rand() << 15);
}
for (int i = 0; i < 256; i++) {
lowestBitTable[i] = get_lowest_set_bit(i);
}
clock_t start_time, end_time;
int result;
start_time = clock();
result = find_first_bits_naive_loop(nums);
end_time = clock();
printf("Naive loop. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_de_bruijn(nums);
end_time = clock();
printf("De Bruijn multiply. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_lookup_table(nums);
end_time = clock();
printf("Lookup table. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_ffs_instruction(nums);
end_time = clock();
printf("FFS instruction. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_branch_free_mask(nums);
end_time = clock();
printf("Branch free mask. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_double_hack(nums);
end_time = clock();
printf("Double hack. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}
내장된 ffs를 사용해 보는 것은 어떨까요? (Linux에서 man 페이지를 가져왔습니다만, 그것보다 더 폭넓게 이용할 수 있습니다.)
ffs(3) - Linux man 페이지
이름.
ffs - 단어에서 설정된 첫 번째 비트 찾기
개요
#include <strings.h> int ffs(int i); #define _GNU_SOURCE #include <string.h> int ffsl(long int i); int ffsll(long long int i);묘사
ffs() 함수는 단어 i의 첫 번째(중요하지 않은) 비트세트의 위치를 반환합니다.최하위 비트는 위치 1이고 최상위 위치(예: 32 또는 64)입니다.함수 ffsl()과 ffsl()은 같은 처리를 하지만 크기가 다를 수 있습니다.
반환값
이 함수는 첫 번째 비트 세트의 위치를 반환합니다. i에 비트가 설정되어 있지 않으면 0을 반환합니다.
준거
4.3BSD, POSIX.1-2001.
메모들
의 시제품은 .
<string.h>.
11년 후 드디어 실현: countr_zero
잘했다 C++20
지점이 있을 때마다 CPU는 어떤 지점을 사용할지 추측해야 합니다.명령 파이프에는 추측된 경로로 이어지는 명령이 로드됩니다.CPU가 잘못 추측한 경우 명령 파이프가 플러시되므로 다른 브랜치를 로드해야 합니다.
상단의 심플한 while 루프를 고려합니다.추측은 루프를 유지하는 것입니다.루프를 벗어날 때 적어도 한 번은 틀립니다.그러면 지침 파이프가 플러싱됩니다.이 동작은 루프가 반복될 때마다 명령 파이프를 플러시할 것이라고 추측하는 것보다 약간 낫습니다.
손실되는 CPU 사이클의 양은 프로세서의 종류에 따라 크게 다릅니다.단, CPU 사이클의 손실은 20~150회입니다.
다음으로 더 나쁜 그룹은 값을 더 작은 조각으로 나누고 몇 개의 분기를 추가함으로써 몇 번의 반복을 줄일 수 있다고 생각하는 그룹입니다.각 브랜치에는 명령 파이프를 플러시할 기회가 추가되어 20~150 클럭 사이클이 소요됩니다.
테이블에서 값을 검색하면 어떤 일이 일어나는지 생각해 보겠습니다.적어도 함수가 처음 호출되었을 때는 이 값이 현재 캐시 내에 없을 수 있습니다.즉, 값이 캐시에서 로드되는 동안 CPU가 정지합니다.이것도 기계마다 다릅니다.새로운 인텔 칩은 현재 스레드가 캐시 로드가 완료될 때까지 기다리는 동안 스레드를 교환할 수 있는 기회로 사용됩니다.이 작업은 명령 파이프 플러시보다 비용이 많이 들 수 있지만 이 작업을 여러 번 수행할 경우 한 번만 발생할 수 있습니다.
확실히 가장 빠른 상수 시간 해법은 결정론적 수학이 수반되는 해법이다.순수하고 우아한 솔루션.
이미 해결되었다면 사과드립니다.
XCODE AFIK를 제외하고 사용하는 모든 컴파일러에는 포워드 비트스캔과 리버스 비트스캔의 컴파일러 기능이 있습니다.이러한 명령어는 캐시 미스, 브랜치 미스 예측 및 기타 프로그래머가 생성한 장애 블록이 없는 대부분의 하드웨어에서 단일 어셈블리 명령으로 컴파일됩니다.
Microsoft 의 _BitScanForward _ _BitScanReverse 。
GCC는 __builtin_ffs, __builtin_clz, __builtin_ctz이다.
또한, 논의 중인 주제에 대해 충분한 지식이 없는 경우, 답변을 게시하거나 새로운 사람을 오도하는 것을 삼가해 주십시오.
해결책을 제공하는 것을 완전히 잊어버려서 죄송합니다.이 작업을 위한 어셈블리 레벨 지침이 없는 IPAD에서 사용하는 코드는 다음과 같습니다.
unsigned BitScanLow_BranchFree(unsigned value)
{
bool bwl = (value & 0x0000ffff) == 0;
unsigned I1 = (bwl * 15);
value = (value >> I1) & 0x0000ffff;
bool bbl = (value & 0x00ff00ff) == 0;
unsigned I2 = (bbl * 7);
value = (value >> I2) & 0x00ff00ff;
bool bnl = (value & 0x0f0f0f0f) == 0;
unsigned I3 = (bnl * 3);
value = (value >> I3) & 0x0f0f0f0f;
bool bsl = (value & 0x33333333) == 0;
unsigned I4 = (bsl * 1);
value = (value >> I4) & 0x33333333;
unsigned result = value + I1 + I2 + I3 + I4 - 1;
return result;
}
여기서 이해해야 할 것은 비싼 것은 비교가 아니라 비교 후에 발생하는 지점입니다.이 경우와의 비교는 0 또는1의 값으로 강제됩니다.== 0이며, 결과는 나뭇가지 양쪽에서 발생할 수 있는 계산을 결합하는 데 사용됩니다.
편집:
위의 코드는 완전히 망가져 있습니다.이 코드는 기능하며 브랜치프리(최적화된 경우)입니다.
int BitScanLow_BranchFree(ui value)
{
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
return i16 + i8 + i4 + i2 + i1 + i0;
}
0이 지정되면 -1이 반환됩니다.0을 신경 쓰지 않거나 0에 대해 31을 얻으면 i0 계산을 삭제하여 시간을 절약합니다.
x86 어셈블리 명령이 있습니다(bsf이 됩니다
최적화?!
사이드 노트:
이 레벨에서의 최적화는 본질적으로 아키텍처에 의존합니다.오늘날의 프로세서는 너무 복잡하기 때문에(분기 예측, 캐시 누락, 파이프라인 측면에서) 어떤 코드가 어떤 아키텍처에서 더 빨리 실행될지 예측하기가 매우 어렵습니다.운용을 32개에서9개로 줄이면 일부 아키텍처의 퍼포먼스가 저하될 수 있습니다.단일 아키텍처에서 최적화된 코드를 사용하면 다른 아키텍처에서 더 나쁜 코드가 발생할 수 있습니다.특정 CPU에 맞게 최적화하거나 그대로 두고 컴파일러가 더 좋다고 생각하는 것을 선택하게 하는 것이 좋다고 생각합니다.
이를 위한 가장 빠른 솔루션(비내부/비어셈블러)은 가장 낮은 바이트를 찾아 256 엔트리 룩업테이블에서 그 바이트를 사용하는 것입니다.이렇게 하면 최악의 경우 4개의 조건부 명령과 최적의 경우 1의 성능을 얻을 수 있습니다.이는 최소한의 명령일 뿐만 아니라 최신 하드웨어에서 가장 중요한 브랜치 수이기도 합니다.
테이블(8비트 엔트리 256개)에는 0 ~255 범위의 각 번호에 대한 LSB 인덱스가 포함되어 있어야 합니다.값의 각 바이트를 확인하고 0이 아닌 가장 낮은 바이트를 찾은 다음 이 값을 사용하여 실제 인덱스를 검색합니다.
여기에는 256바이트의 메모리가 필요하지만, 이 기능의 속도가 매우 중요하기 때문에 256바이트의 메모리는 가치가 있습니다.
예.
byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};
unsigned GetLowestBitPos(unsigned value)
{
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
byte* bytes = (byte*)value;
if (bytes[0])
return lowestBitTable[bytes[0]];
else if (bytes[1])
return lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
return lowestBitTable[bytes[2]] + 16;
else
return lowestBitTable[bytes[3]] + 24;
}
"The Art of Programming, part 4"의 "Magic masks"를 사용하여 N비트 번호에 대해 O(log(n) 시간 내에 수행하는 "Magic masks"를 사용하여 이 영리한 기술을 발견했습니다.[로그(n) 여유 공간 포함]세트 비트를 체크하는 일반적인 솔루션은 O(n)이거나 룩업테이블에 O(n) 여유 공간이 필요하기 때문에 이 방법을 사용하는 것이 좋습니다.
매직 마스크:
m0 = (...............01010101)
m1 = (...............00110011)
m2 = (...............00001111)
m3 = (.......0000000011111111)
....
주요 아이디어:x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + ...의 후행 0의 수
int lastSetBitPos(const uint64_t x) {
if (x == 0) return -1;
//For 64 bit number, log2(64)-1, ie; 5 masks needed
int steps = log2(sizeof(x) * 8); assert(steps == 6);
//magic masks
uint64_t m[] = { 0x5555555555555555, // .... 010101
0x3333333333333333, // .....110011
0x0f0f0f0f0f0f0f0f, // ...00001111
0x00ff00ff00ff00ff, //0000000011111111
0x0000ffff0000ffff,
0x00000000ffffffff };
//Firstly extract only the last set bit
uint64_t y = x & -x;
int trailZeros = 0, i = 0 , factor = 0;
while (i < steps) {
factor = ((y & m[i]) == 0 ) ? 1 : 0;
trailZeros += factor * pow(2,i);
++i;
}
return (trailZeros+1);
}
세트비트를 검색한 비슷한 투고에서 영감을 얻어 다음을 제안합니다.
unsigned GetLowestBitPos(unsigned value)
{
double d = value ^ (value - !!value);
return (((int*)&d)[1]>>20)-1023;
}
장점:
- 루프 없음
- 분기 없음
- 일정한 시간 내에 실행
- 그렇지 않으면 부적합한 결과를 반환하여 value=0을 처리합니다.
- 두 줄의 코드만
단점:
- 코드화된 엔디안성이 거의 없다고 가정합니다(상수를 변경하여 고정할 수 있음).
- 는 더블이 실제*8 IEEE 플로트라고 가정합니다(IEEE 754).
업데이트: 코멘트에서 지적한 바와 같이 유니언은 (적어도 C의 경우) 보다 깔끔한 구현이며 다음과 같습니다.
unsigned GetLowestBitPos(unsigned value)
{
union {
int i[2];
double d;
} temp = { .d = value ^ (value - !!value) };
return (temp.i[1] >> 20) - 1023;
}
이 경우 32비트 int와 리틀 엔디안 스토리지를 모든 용도로 사용할 수 있다고 가정합니다(x86 프로세서).
조작이 32 미만인 최악의 경우에서도 실행할 수 있습니다.
원칙:2비트 이상의 비트를 체크하는 것은 1비트를 체크하는 것과 마찬가지로 효율적입니다.
예를 들어, 먼저 어떤 그룹에 속해 있는지 확인한 다음 해당 그룹에서 가장 작은 비트에서 가장 큰 비트로 각 비트를 확인해야 합니다.
최악의 경우 한 번에 2비트를 체크하는 경우(Nbits/2) + 1개의 체크 합계를 체크합니다.
최악의 경우 한 번에 3비트를 체크하는 경우(Nbits/3) + 총 2개의 체크가 있습니다.
4인 1조로 체크하는 것이 가장 좋습니다.최악의 경우 32개가 아닌 11개의 수술이 필요할 겁니다
이 그룹화 아이디어를 사용하는 경우 알고리즘의 1회 검사에서2회 검사로 넘어갑니다.하지만 최상의 경우 1개의 체크박스를 추가로 사용하면 최악의 경우 비용을 절감할 수 있습니다.
주의: 루프를 사용하지 않고 풀로 씁니다.그렇게 하는 것이 효율적이기 때문입니다.
int getLowestBitPos(unsigned int value)
{
//Group 1: Bits 0-3
if(value&0xf)
{
if(value&0x1)
return 0;
else if(value&0x2)
return 1;
else if(value&0x4)
return 2;
else
return 3;
}
//Group 2: Bits 4-7
if(value&0xf0)
{
if(value&0x10)
return 4;
else if(value&0x20)
return 5;
else if(value&0x40)
return 6;
else
return 7;
}
//Group 3: Bits 8-11
if(value&0xf00)
{
if(value&0x100)
return 8;
else if(value&0x200)
return 9;
else if(value&0x400)
return 10;
else
return 11;
}
//Group 4: Bits 12-15
if(value&0xf000)
{
if(value&0x1000)
return 12;
else if(value&0x2000)
return 13;
else if(value&0x4000)
return 14;
else
return 15;
}
//Group 5: Bits 16-19
if(value&0xf0000)
{
if(value&0x10000)
return 16;
else if(value&0x20000)
return 17;
else if(value&0x40000)
return 18;
else
return 19;
}
//Group 6: Bits 20-23
if(value&0xf00000)
{
if(value&0x100000)
return 20;
else if(value&0x200000)
return 21;
else if(value&0x400000)
return 22;
else
return 23;
}
//Group 7: Bits 24-27
if(value&0xf000000)
{
if(value&0x1000000)
return 24;
else if(value&0x2000000)
return 25;
else if(value&0x4000000)
return 26;
else
return 27;
}
//Group 8: Bits 28-31
if(value&0xf0000000)
{
if(value&0x10000000)
return 28;
else if(value&0x20000000)
return 29;
else if(value&0x40000000)
return 30;
else
return 31;
}
return -1;
}
unsigned GetLowestBitPos(unsigned value)
{
if (value & 1) return 1;
if (value & 2) return 2;
if (value & 4) return 3;
if (value & 8) return 4;
if (value & 16) return 5;
if (value & 32) return 6;
if (value & 64) return 7;
if (value & 128) return 8;
if (value & 256) return 9;
if (value & 512) return 10;
if (value & 1024) return 11;
if (value & 2048) return 12;
if (value & 4096) return 13;
if (value & 8192) return 14;
if (value & 16384) return 15;
if (value & 32768) return 16;
if (value & 65536) return 17;
if (value & 131072) return 18;
if (value & 262144) return 19;
if (value & 524288) return 20;
if (value & 1048576) return 21;
if (value & 2097152) return 22;
if (value & 4194304) return 23;
if (value & 8388608) return 24;
if (value & 16777216) return 25;
if (value & 33554432) return 26;
if (value & 67108864) return 27;
if (value & 134217728) return 28;
if (value & 268435456) return 29;
if (value & 536870912) return 30;
if (value & 1073741824) return 31;
return 0; // no bits set
}
모든 숫자의 50%가 코드 첫 줄에 반환됩니다.
모든 숫자의 75%는 코드의 처음 두 줄에서 반환됩니다.
모든 숫자의 87%가 코드의 처음 3줄로 반환됩니다.
모든 숫자의 94%가 코드의 처음 4줄로 반환됩니다.
모든 숫자의 97%가 코드의 처음 5줄로 반환됩니다.
기타.
이 "루프"는 이 스레드에 게시된 대부분의 알고리즘보다 97%의 테스트 케이스에서 더 빠릅니다.
이 코드의 최악의 경우 시나리오가 얼마나 비효율적인지에 대해 불평하는 사람들은 그 상태가 얼마나 드물게 발생하는지를 이해하지 못한다고 생각한다.
바이너리 검색을 사용하는 이유는 무엇입니까?이것은, 5회의 조작 후에 항상 완료됩니다(int 사이즈를 4 바이트로 상정).
if (0x0000FFFF & value) {
if (0x000000FF & value) {
if (0x0000000F & value) {
if (0x00000003 & value) {
if (0x00000001 & value) {
return 1;
} else {
return 2;
}
} else {
if (0x0000004 & value) {
return 3;
} else {
return 4;
}
}
} else { ...
} else { ...
} else { ...
C++11을 사용할 수 있는 경우 컴파일러가 대신 작업을 수행할 수 있습니다.
constexpr std::uint64_t lssb(const std::uint64_t value)
{
return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}
결과는 1 기반 인덱스입니다.
최근에 싱가포르 수상이 페이스북에 작성한 프로그램을 올렸는데, 한 줄 언급할 것이 있습니다.
로직은 단순히 "value & -value"입니다.예를 들어 0x0FF0과 0x0010에 해당하는 (F00F+1)이 있다고 가정하면 가장 낮은1은 4번째 비트에 있습니다.:)
리소스가 있는 경우 속도를 향상시키기 위해 메모리를 희생할 수 있습니다.
static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
return bitPositions[value];
}
주의: 이 테이블은 최소 4GB(반환 타입을 그대로 두면 16GB)를 소비합니다.unsigned1개의 제한된 자원(RAM)을 다른 자원(실행 속도)과 교환하는 예를 나타냅니다.
휴대성을 유지하고, 가능한 한 빨리 실행할 필요가 있는 경우는, 이 방법을 추천합니다.대부분의 실제 애플리케이션에서 4GB 테이블은 비현실적입니다.
@anton-tykhyy가 제공하는 링크에서 다른 방법(계수 분할 및 검색)을 특별히 언급할 필요가 있습니다.이 방법은 DeBrujn multiply 및 lookup method와 성능이 매우 유사하며 약간이나마 중요한 차이가 있습니다.
계수분할 및 조회
unsigned int v; // find the number of trailing zeros in v
int r; // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];
계수 나눗셈 및 조회 메서드는 v=0x00000000 및 v=FFFFFF에 대해 서로 다른 값을 반환하는 반면 DeBrujn 곱셈 및 조회 메서드는 두 입력 모두에서 0을 반환합니다.
테스트:-
unsigned int n1=0x00000000, n2=0xFFFFFFFF;
MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */
Chess Programming BitScan 페이지와 내가 직접 측정한 결과에 따르면, 빼기와 xor가 부정과 마스크보다 더 빠릅니다.
(후행 제로를 카운트하는 경우보다 주의해 주십시오.0현재 가지고 있는 메서드는 반환됩니다.63반면 negate와 마스크는0.)
64비트 감산 및 xor를 다음에 나타냅니다.
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];
참고로 negate 및 mask 방식의 64비트 버전을 다음에 나타냅니다.
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];
하위 비트가 설정되어 있는지 확인할 수 있습니다.그렇다면 나머지 비트의 하위 순서를 살펴봅니다. 예:
32bit int - 처음 16개 중 하나가 설정되어 있는지 확인합니다.이 경우 처음 8개 중 하나가 설정되어 있는지 확인합니다. 설정되어 있는 경우, ...
그렇지 않은 경우 상위 16개 중 하나라도 설정되어 있는지 확인합니다.
기본적으로 바이너리 검색입니다.
단일 x86 명령으로 실행하는 방법에 대해서는 여기를 참조하십시오.단, 최하위 세트비트를 검색하려면BSF('비트 스캔 포워드') 명령 대신BSR에 기재되어 있습니다.
하지만 가장 빠른 해결책은 아니지만 꽤 좋은 것 같습니다.
적어도 그것은 가지가 없다.;)
uint32 x = ...; // 0x00000001 0x0405a0c0 0x00602000
x |= x << 1; // 0x00000003 0x0c0fe1c0 0x00e06000
x |= x << 2; // 0x0000000f 0x3c3fe7c0 0x03e1e000
x |= x << 4; // 0x000000ff 0xffffffc0 0x3fffe000
x |= x << 8; // 0x0000ffff 0xffffffc0 0xffffe000
x |= x << 16; // 0xffffffff 0xffffffc0 0xffffe000
// now x is filled with '1' from the least significant '1' to bit 31
x = ~x; // 0x00000000 0x0000003f 0x00001fff
// now we have 1's below the original least significant 1
// let's count them
x = x & 0x55555555 + (x >> 1) & 0x55555555;
// 0x00000000 0x0000002a 0x00001aaa
x = x & 0x33333333 + (x >> 2) & 0x33333333;
// 0x00000000 0x00000024 0x00001444
x = x & 0x0f0f0f0f + (x >> 4) & 0x0f0f0f0f;
// 0x00000000 0x00000006 0x00000508
x = x & 0x00ff00ff + (x >> 8) & 0x00ff00ff;
// 0x00000000 0x00000006 0x0000000d
x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
// 0x00000000 0x00000006 0x0000000d
// least sign.bit pos. was: 0 6 13
이것은 @Anton Tykhyy 답변에 관한 것입니다.
C++11 constexpr 실장에서는 캐스트를 배제하고 64비트 결과를 32비트로 잘라 VC++17의 경고를 삭제합니다.
constexpr uint32_t DeBruijnSequence[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
constexpr uint32_t ffs ( uint32_t value )
{
return DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
0x1과 0x0이 모두0을 반환하는 문제를 회피하려면 0을 반환해야 합니다.
constexpr uint32_t ffs ( uint32_t value )
{
return (!value) ? 32 : DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
그러나 컴파일러가 콜을 전처리할 수 없거나 전처리하지 않을 경우 계산에 몇 가지 사이클이 추가됩니다.
마지막으로, 관심 있는 경우, 다음은 코드가 의도한 대로 수행하는지 확인하기 위한 정적 어설션 목록입니다.
static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");
로그를 찾는 데 다소 비용이 많이 들지만 간단한 대안이 하나 있습니다.
if(n == 0)
return 0;
return log2(n & -n)+1; //Assuming the bit index starts from 1
언급URL : https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set
'programing' 카테고리의 다른 글
| C 콤마 연산자 사용 (0) | 2022.07.17 |
|---|---|
| 검색 중인 항목은 이전 결과에 따라 다릅니다. (0) | 2022.07.17 |
| size of ( )를 사용하지 않고 이 코드를 사용하여 어레이 크기를 결정하는 방법 (0) | 2022.07.17 |
| 로거 스태틱파이널을 선언하는 이유는 무엇입니까? (0) | 2022.07.17 |
| vuex를 사용하는 vue/axios에서 글로벌 http 응답 오류 처리 (0) | 2022.07.17 |