설정된 최하위 비트의 위치
정수로 설정된 최하위 비트의 위치를 결정하는 효율적인 방법을 찾고 있습니다. 예를 들어 0x0FF0의 경우 4입니다.
간단한 구현은 다음과 같습니다.
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
어떤 아이디어를 꺼낼 수 있습니까?
(참고 :이 질문은 그러한 것들을 즐기는 사람들을위한 것이며 xyzoptimization이 악하다고 말해주지는 않습니다.)
[편집] 아이디어 주셔서 감사합니다 모두! 나도 몇 가지 다른 것을 배웠다. 멋있는!
Bit Twiddling Hacks 는 성능 / 최적화 토론이 첨부 된 뛰어난 비트 트위들 링 해킹 모음을 제공합니다. 해당 사이트에서 귀하의 문제에 대해 내가 가장 좋아하는 솔루션은«multiply and lookup»입니다.
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 시퀀스를 사용하여 1을 색인화 "-위의 코드가 작동하는 이유에 대한 설명.
- " Board Representation> Bitboards> BitScan "-체스 프로그래밍에 특히 중점을 둔이 문제에 대한 자세한 분석
내장 ff를 사용하지 않는 이유는 무엇 입니까? (저는 Linux에서 매뉴얼 페이지를 가져 왔지만 그보다 더 널리 사용 가능합니다.)
ffs (3)-Linux 매뉴얼 페이지
이름
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)입니다. ffsll () 및 ffsl () 함수는 동일하지만 크기가 다른 인수를 사용합니다.
반환 값
이 함수는 첫 번째 비트 세트의 위치를 반환하거나 i에 비트가 설정되지 않은 경우 0을 반환합니다.
준수
4.3BSD, POSIX.1-2001.
노트
BSD 시스템에는에 프로토 타입이
<string.h>있습니다.
이를 수행하는 x86 어셈블리 명령어 ( bsf)가 있습니다. :)
더 최적화?!
사이드 노트 :
Optimization at this level is inherently architecture dependent. Today's processors are too complex (in terms of branch prediction, cache misses, pipelining) that it's so hard to predict which code is executed faster on which architecture. Decreasing operations from 32 to 9 or things like that might even decrease the performance on some architectures. Optimized code on a single architecture might result in worse code in the other. I think you'd either optimize this for a specific CPU or leave it as it is and let the compiler to choose what it thinks it's better.
Most modern architectures will have some instruction for finding the position of the lowest set bit, or the highest set bit, or counting the number of leading zeroes etc.
이 수업에 대한 지시가 하나라도 있으면 다른 수업을 저렴하게 흉내낼 수 있습니다.
종이로 작업하면서 x & (x-1)x에서 가장 낮은 세트 비트를 지우고, ( x & ~(x-1) )구조, 워드 길이 등에 관계없이 가장 낮은 세트 비트 만 반환한다는 것을 인식하십시오. 이것을 알고 있으면 하드웨어 카운트를 사용하는 것이 쉽지 않습니다. 명시적인 지시가없는 경우 가장 낮은 세트 비트를 찾으려면 -zeroes / high-set-bit입니다.
관련 하드웨어 지원이 전혀없는 경우 여기 또는 Bit Twiddling Hacks (비트 Twiddling 해킹) 페이지 에있는 카운트 선도 0의 곱셈 및 조회 구현은 위의 ID를 사용하여 가장 낮은 세트 비트를 제공하도록 간단히 변환 할 수 있습니다. 가지가없는 장점이 있습니다.
위, 벤치 마크가 아닌 수많은 솔루션. 당신은 사람들 스스로 부끄러워해야합니다 ;-)
내 컴퓨터는 Windows 7 64 비트를 실행하는 Intel i530 (2.9 GHz)입니다. 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);
}
이것에 대한 가장 빠른 (내재적 / 비 어셈블러) 솔루션은 가장 낮은 바이트를 찾은 다음 256 바이트 조회 테이블에서 해당 바이트를 사용하는 것입니다. 이렇게하면 4 개의 조건부 명령어 중 최악의 성능과 1의 최상의 경우가 제공됩니다.이 명령어는 가장 적은 명령어 일뿐만 아니라 최신 하드웨어에서 가장 중요한 분기의 수가 가장 적습니다.
테이블 (256 8 비트 항목)에는 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;
}
OMG는 이것을 막 나선했습니다.
이러한 대부분의 예가 부족한 것은 모든 하드웨어의 작동 방식에 대한 약간의 이해입니다.
분기가있을 때마다 CPU는 어떤 분기가 수행 될지 추측해야합니다. 지시 파이프에는 추측 경로를 안내하는 지시 사항이로드됩니다. CPU가 잘못 추측하면 명령 파이프가 플러시되고 다른 분기를로드해야합니다.
상단의 간단한 while 루프를 고려하십시오. 추측은 루프 내에서 유지됩니다. 루프를 떠날 때 적어도 한 번 잘못됩니다. 이 명령 파이프를 플러시합니다. 이 동작은 루프를 떠날 것이라고 추측하는 것보다 약간 낫습니다.이 경우 모든 반복에서 명령 파이프를 플러시합니다.
손실되는 CPU주기의 양은 프로세서 유형에 따라 크게 다릅니다. 그러나 20에서 150 사이의 CPU주기가 손실 될 것으로 예상 할 수 있습니다.
다음으로 더 나쁜 그룹은 값을 작은 조각으로 나누고 더 많은 분기를 추가하여 몇 번의 반복을 절약하려고 생각하는 곳입니다. 이러한 각 분기는 명령 파이프를 플러시하고 추가로 20 ~ 150 클럭 사이클을 소비 할 수있는 추가 기회를 추가합니다.
테이블에서 값을 찾을 때 어떤 일이 발생하는지 고려해 보겠습니다. 최소한 함수가 처음 호출 될 때 값이 현재 캐시에없는 것 같습니다. 이는 값이 캐시에서로드되는 동안 CPU가 정지되었음을 의미합니다. 다시 말하지만 이것은 기계마다 다릅니다. 새로운 인텔 칩은 실제로 이것을 현재 스레드가 캐시로드가 완료되기를 기다리는 동안 스레드를 교환 할 수있는 기회로 사용합니다. 이 작업은 명령 파이프 세척보다 비용이 많이 들지만이 작업을 여러 번 수행하는 경우 한 번만 발생할 가능성이 있습니다.
분명히 가장 빠른 상수 시간 솔루션은 결정적 수학을 포함하는 솔루션입니다. 순수하고 우아한 솔루션.
이것이 이미 다루어 졌다면 사과드립니다.
XCODE AFAIK를 제외하고 내가 사용하는 모든 컴파일러에는 정방향 비트 캔과 역방향 비트 캔 모두에 대한 컴파일러 내장 기능이 있습니다. 이들은 캐시 미스, 분기 미스 예측 및 다른 프로그래머가 생성 한 걸림돌이없는 대부분의 하드웨어에서 단일 어셈블리 명령어로 컴파일됩니다.
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과 함께 0 또는 1의 값으로 강제되며 결과는 분기의 양쪽에서 발생한 수학을 결합하는 데 사용됩니다.
편집하다:
위의 코드는 완전히 고장났습니다. 이 코드는 작동하며 여전히 분기가 없습니다 (최적화 된 경우).
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 계산을 제거하고 시간을 절약하십시오.
세트 비트 검색 과 관련된 이 유사한 게시물에서 영감을 얻어 다음을 제공합니다.
unsigned GetLowestBitPos(unsigned value)
{
double d = value ^ (value - !!value);
return (((int*)&d)[1]>>20)-1023;
}
장점 :
- 루프 없음
- 분기 없음
- 일정한 시간에 실행
- 범위를 벗어난 결과를 반환하여 값 = 0을 처리합니다.
- 두 줄의 코드 만
단점 :
- 코딩 된 엔디안이 거의없는 것으로 가정합니다 (상수를 변경하여 수정 가능)
- double이 실수 * 8 IEEE float (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 비트 정수를 가정합니다 (x86 프로세서 생각).
최악의 경우 32 개 미만의 작업으로 수행 할 수 있습니다.
원리 : 2 비트 이상을 점검하는 것은 1 비트를 점검하는 것만 큼 효율적입니다.
예를 들어 어떤 그룹을 먼저 그룹화했는지 확인한 다음 해당 그룹에서 각 비트를 최소에서 최대로 확인하는 것을 막을 수는 없습니다.
따라서 ...
한 번에 2 비트를 확인하면 최악의 경우 (Nbits / 2) + 1 개의 총 검사입니다.
한 번에 3 비트를 검사하면 최악의 경우 (Nbits / 3) + 총 2 검사입니다.
...
최적은 4 개 그룹을 체크인하는 것입니다. 최악의 경우 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;
}
왜 바이너리 검색을 사용하지 않습니까? 이것은 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 { ...
또 다른 방법 (계수 분할 및 조회)은 @ anton-tykhyy가 제공 한 동일한 링크 에서 특별한 언급이 필요합니다 . 이 방법은 성능면에서 DeBruijn 곱하기 및 조회 방법과 매우 유사하지만 약간의 차이가 있습니다.
계수 나누기와 조회
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 = FFFFFFFF에 대해 서로 다른 값을 반환하지만 DeBruijn은 곱하기 및 조회 방법이 두 입력에서 모두 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 */
에 따르면 체스 BitScan 페이지 프로그래밍 빼고 XOR, 내 자신의 측정은 빨리 무효화 이상과 마스크입니다.
(에서 후행 0을 세는 것보다 0, 내가 가지고있는 메소드는 반환 63하지만 negate 및 mask는 반환합니다 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
"프로그래밍 기술, 파트 4"에서 '매직 마스크'를 사용하여이 영리한 트릭을 발견했습니다.이 기법은 n 비트 수에 대해 O (log (n)) 시간에 수행합니다. [log (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] + ...
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);
}
C ++ 11을 사용할 수있는 경우 컴파일러가 때로는 작업을 수행 할 수 있습니다. :)
constexpr std::uint64_t lssb(const std::uint64_t value)
{
return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}
결과는 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;
return 31;
}
모든 숫자의 50 %가 첫 번째 코드 줄에 반환됩니다.
모든 숫자의 75 %가 코드의 처음 2 줄에 반환됩니다.
모든 숫자의 87 %가 코드의 처음 3 줄에 반환됩니다.
모든 숫자의 94 %가 코드의 처음 4 줄에 반환됩니다.
모든 숫자의 97 %는 처음 5 줄의 코드로 반환됩니다.
기타
이 코드의 최악의 시나리오가 얼마나 비효율적인지에 대해 불평하는 사람들은 그 조건이 얼마나 드문 지 이해하지 못한다고 생각합니다.
이것은 @Anton Tykhyy 답변과 관련이 있습니다.
다음은 캐스트를 없애고 64 비트 결과를 32 비트로 잘라서 VC ++ 17에 대한 경고를 제거하는 C ++ 11 constexpr 구현입니다.
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을 반환합니다.
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
최근에 나는 싱가포르 프리미어가 페이스 북에 쓴 프로그램을 게시 한 것을 보았습니다.
논리는 단순히 "value & -value"이며, 0x0FF0이 있고 0FF00 & (F00F + 1)이 0x0010과 같다고 가정하면 가장 낮은 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 unsigned). 하나의 제한된 자원 (RAM)을 다른 하나의 자원 (실행 속도)으로 거래하는 예입니다.
기능을 휴대 가능한 상태로 유지하고 최대한의 비용으로 최대한 빨리 실행해야하는 경우이 방법을 사용할 수 있습니다. 대부분의 실제 응용 프로그램에서 4GB 테이블은 비현실적입니다.
참고 URL : https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set
'developer tip' 카테고리의 다른 글
| Java 패키지에서 특성 파일로드 (0) | 2020.08.03 |
|---|---|
| 자동 레이아웃 : Top Layout Guide가 아닌 Superview에 구속 조건을 추가 하시겠습니까? (0) | 2020.08.02 |
| 레이아웃 XML 파일에 포함을 사용할 때 ID를 지정하는 방법 (0) | 2020.08.02 |
| UILabel은 레이블 크기에 맞게 텍스트를 자동 축소하지 않습니다. (0) | 2020.08.02 |
| Windows 용 Docker가 드라이브를 공유 할 수 있도록 Windows 방화벽 설정 (0) | 2020.08.02 |