C의 정수에서 가장 높은 세트 비트 (msb)를 찾는 가장 빠르고 효율적인 방법은 무엇입니까?
정수 n이 있고 가장 중요한 비트의 위치를 알고 싶습니다 (즉, 가장 중요하지 않은 비트가 오른쪽에 있으면 가장 왼쪽의 비트가 1 인 위치를 알고 싶습니다). 가장 빠르고 효율적인 방법은 무엇입니까?
POSIX는 ffs()strings.h에서 첫 번째 세트 비트를 찾기 위해 메소드를 지원 하지만 해당 fls()메소드 가없는 것 같습니다 .
내가 누락 된이 작업을 수행하는 확실한 방법이 있습니까?
이식성을 위해 POSIX 기능을 사용할 수없는 경우는 어떻습니까?
편집 : 32 및 64 비트 아키텍처 모두에서 작동하는 솔루션은 어떻습니까 (많은 코드 목록은 32 비트 int에서만 작동하는 것처럼 보입니다).
GCC는 :
내장 함수 : int __builtin_clz (부호없는 int x)
X에서 맨 앞의 0 비트 수를 가장 큰 값으로 반환
중요한 비트 위치. X가 0이면 결과가 정의되지 않습니다.
내장 함수 : int __builtin_clzl (부호없는 long)
`__builtin_clz '와 비슷하지만 인수 유형이`unsigned
긴'.
내장 함수 : int __builtin_clzll (부호없는 long long)
`__builtin_clz '와 비슷하지만 인수 유형이`unsigned
길다 '
멋진 비트 트위들 링 알고리즘 중 하나이든 단일 명령이든 현재 플랫폼에 합리적으로 효율적인 것으로 변환 될 것으로 기대합니다.
유용한 트릭은 귀하의 의견은 경우 수 있을 제로 __builtin_clz(x | 1): 무조건 어떤 다른 사람을 수정하지 않고 낮은 비트를 출력하게 0를 들어 x=0다른 입력에 대한 출력을 변경하지 않고.
그렇게하지 않으려면 다른 옵션은 ARM GCC __clz(헤더 필요 없음) 또는 명령어 _lzcnt_u32를 지원하는 CPU 의 x86 과 같은 플랫폼 별 내장 함수 lzcnt입니다. ( 오류가 아닌 구형 CPU에서 lzcnt와 같이 디코딩되므로 bsr0이 아닌 입력에 31-lzcnt를 제공합니다.)
불행히도 입력 값에 대한 결과를 32 또는 64 (피연산자 너비에 따라)로 정의하는 비 x86 플랫폼에서 다양한 CLZ 명령어를 이식 가능하게 활용할 수있는 방법이 없습니다. x86 lzcnt도 그렇게하지만 bsr컴파일러를 사용하지 않으면 뒤집어 야하는 비트 인덱스를 생성합니다 31-__builtin_clz(x).
( "정의되지 않은 결과"는 정의되지 않은 값인 C Undefined Behavior가 아닙니다. 실제로 명령이 실행될 때 대상 레지스터에 있던 내용입니다. AMD는이를 문서화하고, Intel은 그렇지 않지만 Intel CPU는 해당 동작을 구현합니다. . 그러나 그건 하지 하지 일반적으로 GCC는 ASM에 C를 켤 때 사물이 작동하는 방법 즉, 당신이 지정하고있는 C 변수에 이전했다 뭐든간에. 참조 왜 문제 LZCNT의 "출력 종속"을 위반 하는가? )
x86을 사용하고 있고 약간의 인라인 어셈블러를 사용한다고 가정하면 인텔에서 BSR지침 ( "비트 스캔 역전")을 제공합니다. 그것은의 빠른 에 일부 (다른 사람에 microcoded) x86s. 매뉴얼에서 :
가장 중요한 세트 비트 (1 비트)에 대한 소스 피연산자를 검색합니다. 최상위 1 비트가 발견되면 해당 비트 인덱스는 대상 피연산자에 저장됩니다. 소스 피연산자는 레지스터 또는 메모리 위치 일 수 있습니다. 대상 피연산자는 레지스터입니다. 비트 인덱스는 소스 피연산자의 비트 0에서 부호없는 오프셋입니다. 컨텐츠 소스 피연산자가 0이면 대상 피연산자의 컨텐츠가 정의되지 않습니다.
PowerPC를 사용하는 경우 유사한 cntlz( "count Leading zeros") 명령이 있습니다.
gcc의 예제 코드 :
#include <iostream>
int main (int,char**)
{
int n=1;
for (;;++n) {
int msb;
asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
std::cout << n << " : " << msb << std::endl;
}
return 0;
}
이 인라인 어셈블러 튜토리얼을 참조하십시오.이 섹션은 루핑 코드보다 훨씬 빠릅니다 (섹션 9.4).
2 ^ N은 N 번째 비트 세트 (1 << N) 만있는 정수이므로 가장 높은 세트 비트의 위치 (N)를 찾는 것은 해당 정수의 정수 로그 밑수 2입니다.
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
unsigned int v;
unsigned r = 0;
while (v >>= 1) {
r++;
}
이 "명백한"알고리즘은 모든 사람에게 투명하지 않을 수도 있지만, 가장 왼쪽 비트가 시프트 될 때까지 코드가 1 비트 씩 반복적으로 시프트한다는 것을 인식하면 (C는 0이 아닌 값을 true로 처리 함) 숫자를 리턴합니다. 교대, 그것은 완벽하게 이해됩니다. 또한 둘 이상의 비트가 설정된 경우에도 작동합니다. 결과는 항상 가장 중요한 비트입니다.
해당 페이지를 아래로 스크롤하면 더 빠르고 복잡한 변형이 있습니다. 그러나 선행 제로가 많은 숫자를 처리한다는 것을 알고 있다면 C에서 비트 이동이 다소 빠르며 간단한 알고리즘은 배열 인덱싱이 필요하지 않기 때문에 순진한 접근 방식이 허용 가능한 속도를 제공 할 수 있습니다.
참고 : 64 비트 값을 사용할 때는 여분의 알고리즘 사용에 매우주의해야합니다. 이들 중 다수는 32 비트 값에 대해서만 올바르게 작동합니다.
번개가 빨리옵니다 :
int msb(unsigned int v) {
static const int pos[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};
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v = (v >> 1) + 1;
return pos[(v * 0x077CB531UL) >> 27];
}
이것은 일종의 정수 로그를 찾는 것과 같습니다. 약간의 트릭이 있지만,이를 위해 나만의 도구를 만들었습니다. 물론 목표는 속도입니다.
내 실현은 CPU에 이미 자동 비트 감지기가 있고 정수에서 부동 소수점으로 변환하는 것입니다! 사용하십시오.
double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness
이 버전은 값을 두 배로 캐스트 한 다음 지수를 읽어 비트 위치를 알려줍니다. 멋진 변화와 빼기는 IEEE 값에서 적절한 부분을 추출하는 것입니다.
부동 소수점을 사용하는 것이 약간 빠르지 만 부동 소수점은 정밀도가 낮아서 처음 24 비트 위치 만 제공 할 수 있습니다.
C ++ 또는 C에서 정의되지 않은 동작없이 안전하게 수행하려면 memcpy유형 제거를위한 포인터 캐스팅 대신 사용하십시오 . 컴파일러는 효율적으로 인라인하는 방법을 알고 있습니다.
// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?
double ff=(double)(v|1);
uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;
또는 C99 이상에서는을 사용하십시오 union {double d; uint32_t u[2];};. 그러나 C ++에서 공용체 유형 제거는 ISO C ++가 아닌 일부 컴파일러에서만 확장으로 지원됩니다.
이것은 일반적으로 0으로 시작하는 카운팅 명령의 경우 플랫폼 고유의 속도보다 느리지 만 휴대용 ISO C에는 그러한 기능이 없습니다. 일부 CPU에는 선행 0 계산 명령이 없지만 일부 CPU는 효율적으로 정수를로 변환 할 수 있습니다 double. FP 비트 패턴을 정수로 다시 입력하면 속도가 느려질 수 있습니다 (예 : PowerPC에서는 저장 / 재로드가 필요하며 일반적으로로드 적중 저장이 중단됩니다).
이 알고리즘은 SIMD를 갖는 CPU 수가 적기 때문에 SIMD 구현에 유용 할 수 있습니다 lzcnt. x86 은 AVX512CD 에서만 이러한 명령 을 받았습니다.
Kaz Kylheku는 여기
나는 63 비트 숫자 (gcc x86_64의 long long type)에 대해 두 가지 접근법을 벤치 마크하여 부호 비트에서 멀리 유지했습니다.
(나는 무언가를 위해이 "가장 높은 비트 찾기"가 필요하다.)
데이터 기반 이진 검색을 구현했습니다 (위의 답변 중 하나를 기반으로). 또한 직접 언 롤링 된 의사 결정 트리를 직접 구현했으며, 이는 즉시 피연산자가있는 코드입니다. 루프 나 테이블이 없습니다.
의사 결정 트리 (highest_bit_unrolled)는 이진 검색에서 명시 적 테스트를 수행하는 n = 0 인 경우를 제외하고 벤치 마크가 69 % 빠릅니다.
이진 검색의 0 사례에 대한 특수 테스트는 의사 결정 트리보다 48 % 빠르며, 특수 테스트는 없습니다.
컴파일러, 머신 : (GCC 4.5.2, -O3, x86-64, 2867 Mhz Intel Core i5).
int highest_bit_unrolled(long long n)
{
if (n & 0x7FFFFFFF00000000) {
if (n & 0x7FFF000000000000) {
if (n & 0x7F00000000000000) {
if (n & 0x7000000000000000) {
if (n & 0x4000000000000000)
return 63;
else
return (n & 0x2000000000000000) ? 62 : 61;
} else {
if (n & 0x0C00000000000000)
return (n & 0x0800000000000000) ? 60 : 59;
else
return (n & 0x0200000000000000) ? 58 : 57;
}
} else {
if (n & 0x00F0000000000000) {
if (n & 0x00C0000000000000)
return (n & 0x0080000000000000) ? 56 : 55;
else
return (n & 0x0020000000000000) ? 54 : 53;
} else {
if (n & 0x000C000000000000)
return (n & 0x0008000000000000) ? 52 : 51;
else
return (n & 0x0002000000000000) ? 50 : 49;
}
}
} else {
if (n & 0x0000FF0000000000) {
if (n & 0x0000F00000000000) {
if (n & 0x0000C00000000000)
return (n & 0x0000800000000000) ? 48 : 47;
else
return (n & 0x0000200000000000) ? 46 : 45;
} else {
if (n & 0x00000C0000000000)
return (n & 0x0000080000000000) ? 44 : 43;
else
return (n & 0x0000020000000000) ? 42 : 41;
}
} else {
if (n & 0x000000F000000000) {
if (n & 0x000000C000000000)
return (n & 0x0000008000000000) ? 40 : 39;
else
return (n & 0x0000002000000000) ? 38 : 37;
} else {
if (n & 0x0000000C00000000)
return (n & 0x0000000800000000) ? 36 : 35;
else
return (n & 0x0000000200000000) ? 34 : 33;
}
}
}
} else {
if (n & 0x00000000FFFF0000) {
if (n & 0x00000000FF000000) {
if (n & 0x00000000F0000000) {
if (n & 0x00000000C0000000)
return (n & 0x0000000080000000) ? 32 : 31;
else
return (n & 0x0000000020000000) ? 30 : 29;
} else {
if (n & 0x000000000C000000)
return (n & 0x0000000008000000) ? 28 : 27;
else
return (n & 0x0000000002000000) ? 26 : 25;
}
} else {
if (n & 0x0000000000F00000) {
if (n & 0x0000000000C00000)
return (n & 0x0000000000800000) ? 24 : 23;
else
return (n & 0x0000000000200000) ? 22 : 21;
} else {
if (n & 0x00000000000C0000)
return (n & 0x0000000000080000) ? 20 : 19;
else
return (n & 0x0000000000020000) ? 18 : 17;
}
}
} else {
if (n & 0x000000000000FF00) {
if (n & 0x000000000000F000) {
if (n & 0x000000000000C000)
return (n & 0x0000000000008000) ? 16 : 15;
else
return (n & 0x0000000000002000) ? 14 : 13;
} else {
if (n & 0x0000000000000C00)
return (n & 0x0000000000000800) ? 12 : 11;
else
return (n & 0x0000000000000200) ? 10 : 9;
}
} else {
if (n & 0x00000000000000F0) {
if (n & 0x00000000000000C0)
return (n & 0x0000000000000080) ? 8 : 7;
else
return (n & 0x0000000000000020) ? 6 : 5;
} else {
if (n & 0x000000000000000C)
return (n & 0x0000000000000008) ? 4 : 3;
else
return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
}
}
}
}
}
int highest_bit(long long n)
{
const long long mask[] = {
0x000000007FFFFFFF,
0x000000000000FFFF,
0x00000000000000FF,
0x000000000000000F,
0x0000000000000003,
0x0000000000000001
};
int hi = 64;
int lo = 0;
int i = 0;
if (n == 0)
return 0;
for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
int mi = lo + (hi - lo) / 2;
if ((n >> mi) != 0)
lo = mi;
else if ((n & (mask[i] << lo)) != 0)
hi = mi;
}
return lo + 1;
}
빠르고 더러운 테스트 프로그램 :
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int highest_bit_unrolled(long long n);
int highest_bit(long long n);
main(int argc, char **argv)
{
long long n = strtoull(argv[1], NULL, 0);
int b1, b2;
long i;
clock_t start = clock(), mid, end;
for (i = 0; i < 1000000000; i++)
b1 = highest_bit_unrolled(n);
mid = clock();
for (i = 0; i < 1000000000; i++)
b2 = highest_bit(n);
end = clock();
printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);
printf("time1 = %d\n", (int) (mid - start));
printf("time2 = %d\n", (int) (end - mid));
return 0;
}
-O2 만 사용하면 차이가 커집니다. 의사 결정 트리는 거의 4 배 더 빠릅니다.
또한 순진한 비트 시프 팅 코드를 벤치마킹했습니다.
int highest_bit_shift(long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}
이것은 예상대로 작은 숫자에 대해서만 빠릅니다. n == 1에 대해 가장 높은 비트가 1이라고 판단 할 때 벤치 마크는 80 % 이상 빨라졌습니다. 그러나 63 비트 공간에서 임의로 선택된 숫자의 절반에 63 비트가 설정됩니다!
입력 0x3FFFFFFFFFFFFFFFFF에서 의사 결정 트리 버전은 1보다 약간 빠르며 비트 시프터보다 1120 % 더 빠릅니다 (12.2 배).
또한 GCC 내장에 대해 의사 결정 트리를 벤치마킹하고 동일한 수에 대해 반복하지 않고 혼합 된 입력을 시도합니다. 고집하는 분기 예측이 진행되고 비현실적인 캐싱 시나리오가 반복적으로 인위적으로 더 빠를 수 있습니다.
이건 어떤가요
int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}
?
다음은 현재이 페이지에 제공된 알고리즘의 일부 (간단한) 벤치 마크입니다.
알고리즘은 부호없는 int의 모든 입력에 대해 테스트되지 않았습니다. 맹목적으로 무언가를 사용하기 전에 먼저 확인하십시오.)
내 컴퓨터에서 clz (__builtin_clz)와 asm이 가장 잘 작동합니다. asm은 clz보다 훨씬 빠르지 만 간단한 벤치 마크 때문일 수 있습니다.
//////// go.c ///////////////////////////////
// compile with: gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/***************** math ********************/
#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */ \
((unsigned) log2(a)) /* thus: do not use if a <= 0 */
#define NUM_OF_HIGHESTBITmath(a) ((a) \
? (1U << POS_OF_HIGHESTBITmath(a)) \
: 0)
/***************** clz ********************/
unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */
#define NUM_OF_HIGHESTBITclz(a) ((a) \
? (1U << POS_OF_HIGHESTBITclz(a)) \
: 0)
/***************** i2f ********************/
double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)
#define NUM_OF_HIGHESTBITi2f(a) ((a) \
? (1U << POS_OF_HIGHESTBITi2f(a)) \
: 0)
/***************** asm ********************/
unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)
#define NUM_OF_HIGHESTBITasm(a) ((a) \
? (1U << POS_OF_HIGHESTBITasm(a)) \
: 0)
/***************** bitshift1 ********************/
#define NUM_OF_HIGHESTBITbitshift1(a) (({ \
OUT = a; \
OUT |= (OUT >> 1); \
OUT |= (OUT >> 2); \
OUT |= (OUT >> 4); \
OUT |= (OUT >> 8); \
OUT |= (OUT >> 16); \
}), (OUT & ~(OUT >> 1))) \
/***************** bitshift2 ********************/
int POS[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};
#define POS_OF_HIGHESTBITbitshift2(a) (({ \
OUT = a; \
OUT |= OUT >> 1; \
OUT |= OUT >> 2; \
OUT |= OUT >> 4; \
OUT |= OUT >> 8; \
OUT |= OUT >> 16; \
OUT = (OUT >> 1) + 1; \
}), POS[(OUT * 0x077CB531UL) >> 27])
#define NUM_OF_HIGHESTBITbitshift2(a) ((a) \
? (1U << POS_OF_HIGHESTBITbitshift2(a)) \
: 0)
#define LOOPS 100000000U
int main()
{
time_t start, end;
unsigned ui;
unsigned n;
/********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/
printf("math\n");
for (ui = 0U; ui < 18; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui));
printf("\n\n");
printf("clz\n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui));
printf("\n\n");
printf("i2f\n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui));
printf("\n\n");
printf("asm\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui));
}
printf("\n\n");
printf("bitshift1\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
}
printf("\n\n");
printf("bitshift2\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
}
printf("\n\nPlease wait...\n\n");
/************************* Simple clock() benchmark ******************/
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITmath(ui);
end = clock();
printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITclz(ui);
end = clock();
printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITi2f(ui);
end = clock();
printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITasm(ui);
end = clock();
printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift1(ui);
end = clock();
printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift2(ui);
end = clock();
printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n");
return EXIT_SUCCESS;
}
최상의 성능을 절대적으로 요구하는 경우 (예 : 비트 보드와 관련된 보드 게임 AI를 작성하는 경우)에만이 방법을 사용하지만 가장 효율적인 솔루션은 인라인 ASM을 사용하는 것입니다. 설명이 포함 된 코드 는 이 블로그 게시물 의 최적화 섹션을 참조하십시오 .
[...],
bsrl어셈블리 명령어는 최상위 비트의 위치를 계산합니다. 따라서이asm문장을 사용할 수 있습니다 :asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
unsigned int
msb32(register unsigned int x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return(x & ~(x >> 1));
}
1 레지스터, 13 명령어. 믿거 나 말거나, 이것은 일반적으로 위에서 언급 한 BSR 명령보다 빠르며 선형 시간으로 작동합니다. 이것은 로그 시간입니다.
에서 http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit
나는 이것을하기 위해 루틴이 필요했고 웹을 검색하기 전에 (그리고이 페이지를 찾기 전에) 이진 검색을 기반으로 한 자체 솔루션을 생각해 냈습니다. 누군가 전에 이것을 한 것이 확실합니다! 일정한 시간에 실행되며 게시 된 "명백한"솔루션보다 빠를 수는 있지만 관심을 끌기 위해 큰 주장을하지는 않습니다.
int highest_bit(unsigned int a) {
static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
const unsigned int *mask = maskv;
int l, h;
if (a == 0) return -1;
l = 0;
h = 32;
do {
int m = l + (h - l) / 2;
if ((a >> m) != 0) l = m;
else if ((a & (*mask << l)) != 0) h = m;
mask++;
} while (l < h - 1);
return l;
}
그것은 일종의 이진 검색이며 모든 종류의 (부호없는!) 정수 유형과 함께 작동합니다.
#include <climits>
#define UINT (unsigned int)
#define UINT_BIT (CHAR_BIT*sizeof(UINT))
int msb(UINT x)
{
if(0 == x)
return -1;
int c = 0;
for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
if(static_cast<UINT>(x >> i))
{
x >>= i;
c |= i;
}
return c;
}
완료하려면 :
#include <climits>
#define UINT unsigned int
#define UINT_BIT (CHAR_BIT*sizeof(UINT))
int lsb(UINT x)
{
if(0 == x)
return -1;
int c = UINT_BIT-1;
for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
if(static_cast<UINT>(x << i))
{
x <<= i;
c ^= i;
}
return c;
}
여기에 지나치게 복잡한 답변이 있습니다. Debruin 기술은 입력이 이미 2의 거듭 제곱 일 때만 사용해야합니다. 그렇지 않으면 더 좋은 방법이 있습니다. 2 입력의 전력을 위해 Debruin은 _BitScanReverse테스트 한 프로세서 보다 훨씬 빠릅니다 . 그러나 일반적인 경우 _BitScanReverse(또는 컴파일러에서 내장 함수가 호출되는 것)가 가장 빠릅니다 (특정 CPU에서는 마이크로 코딩 할 수 있음).
내장 함수가 옵션이 아닌 경우 일반적인 입력을 처리하기위한 최적의 소프트웨어 솔루션이 있습니다.
u8 inline log2 (u32 val) {
u8 k = 0;
if (val > 0x0000FFFFu) { val >>= 16; k = 16; }
if (val > 0x000000FFu) { val >>= 8; k |= 8; }
if (val > 0x0000000Fu) { val >>= 4; k |= 4; }
if (val > 0x00000003u) { val >>= 2; k |= 2; }
k |= (val & 2) >> 1;
return k;
}
이 버전은 대부분의 다른 답변과 달리 마지막에 Debruin 조회가 필요하지 않습니다. 위치를 계산합니다.
테이블을 여러 번 반복해서 호출하면 테이블 속도가 높아져 캐시 누락의 위험이 줄어 듭니다.
u8 kTableLog2[256] = {
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};
u8 log2_table(u32 val) {
u8 k = 0;
if (val > 0x0000FFFFuL) { val >>= 16; k = 16; }
if (val > 0x000000FFuL) { val >>= 8; k |= 8; }
k |= kTableLog2[val]; // precompute the Log2 of the low byte
return k;
}
이것은 여기에 주어진 소프트웨어 답변 중 가장 높은 처리량을 산출해야하지만 때때로 전화를 걸면 첫 번째 스 니펫과 같은 테이블 프리 솔루션을 선호하십시오.
위의 답변에서 알 수 있듯이 가장 중요한 비트를 결정하는 방법에는 여러 가지가 있습니다. 그러나 지적 된 바와 같이, 방법은 32 비트 또는 64 비트 레지스터에 고유 할 가능성이있다. stanford.edu의 bithacks 페이지는 32 비트 및 64 비트 모두를위한 일을 계산하는 것이 솔루션을 제공합니다. 약간의 작업만으로 MSB를 얻기위한 견고한 아키텍처 간 접근 방식을 제공하기 위해 이들을 결합 할 수 있습니다. 64 및 32 비트 컴퓨터에서 컴파일 / 작동 된 솔루션은 다음과 같습니다.
#if defined(__LP64__) || defined(_LP64)
# define BUILD_64 1
#endif
#include <stdio.h>
#include <stdint.h> /* for uint32_t */
/* CHAR_BIT (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif /* CHAR_BIT */
/*
* Find the log base 2 of an integer with the MSB N set in O(N)
* operations. (on 64bit & 32bit architectures)
*/
int
getmsb (uint32_t word)
{
int r = 0;
if (word < 1)
return 0;
#ifdef BUILD_64
union { uint32_t u[2]; double d; } t; // temp
t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
while (word >>= 1)
{
r++;
}
#endif /* BUILD_64 */
return r;
}
연속 근사법을 사용하는 C 버전 :
unsigned int getMsb(unsigned int n)
{
unsigned int msb = sizeof(n) * 4;
unsigned int step = msb;
while (step > 1)
{
step /=2;
if (n>>msb)
msb += step;
else
msb -= step;
}
if (n>>msb)
msb++;
return (msb - 1);
}
장점 : 루프 수는 항상 동일하므로 제공된 수에 관계없이 실행 시간이 일정합니다. ( "unsigned int"를 사용할 때 4 루프)
나는이 질문은 아주 오래된,하지만 단지 구현 한 것을 알고 MSB () 함수 나 자신, 나는 대부분의 솔루션은 여기에 제시된 및 기타 웹 사이트에서 찾을 반드시 가장 효율적이다 - 효율성의 내 개인적인 정의에 대한 최소한 (참조 업데이트 하기 ). 이유는 다음과 같습니다.
대부분의 솔루션 (특히 어떤 종류의 이진 검색 체계 또는 오른쪽에서 왼쪽으로 선형 스캔을 수행하는 순진 접근 방식을 사용하는 솔루션)은 임의의 이진수에 대해 매우 긴 순서로 시작하는 솔루션이 많지 않다는 사실을 무시하는 것처럼 보입니다. 제로. 실제로 모든 비트 너비의 경우 모든 정수의 절반이 1로 시작 하고 그 중 1/4은 01로 시작 합니다. 내가 어디로 가는지 알아? 내 주장은 가장 중요한 비트 위치에서 가장 중요한 비트 위치 (왼쪽에서 오른쪽으로)에서 시작 하는 선형 스캔 은 언뜻보기에 "선형"이 아니라는 것입니다.
보여 질 수있다 (1) 임의의 비트 폭을 위해 필요한 테스트 할 것이 비트의 평균 개수가 많아야 이것이로 변환 2. 즉, 상각 시간 복잡도 O (1) 의 비트 수에 대해 (!) .
물론 최악의 경우는 여전히 O (n) 이며 이진 검색과 같은 접근 방식으로 얻는 O (log (n)) 보다 나쁘지만 최악의 경우는 거의 없으므로 대부분의 응용 프로그램에서 무시할 수 있습니다 ( 업데이트 : 그다지 중요하지는 않지만, 가능성이 높을 수 있습니다 ( 아래 업데이트 참조).
여기에 내가 생각해 낸 "순진한"접근 방식이 있습니다. 적어도 내 컴퓨터에서는 대부분의 다른 접근 방식을 능가합니다 (32 비트 정수에 대한 이진 검색 체계에는 항상 log 2 (32) = 5 단계가 필요하지만이 바보 같은 알고리즘은 덜 필요합니다 평균 2 이상)-순수한 C가 아닌 C ++ 인 경우 미안합니다.
template <typename T>
auto msb(T n) -> int
{
static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
"msb<T>(): T must be an unsigned integral type.");
for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
{
if ((n & mask) != 0)
return i;
}
return 0;
}
업데이트 : 여기에 쓴 것은 임의의 정수에대해 완벽하게 사실이지만모든 비트 조합은 똑같이 가능합니다 (제 속도 테스트는 모든 32 비트 정수의 MSB를 결정하는 데 걸린 시간을 간단히 측정했습니다), 실제 정수 예를 들어,이 함수는 객체 크기 가 2의 거듭 제곱인지또는 다음 2의 거듭 제곱을 2보다 크거나 같은지 확인하는 데 사용됩니다. 객체 크기 . 내 생각에 MSB를 사용하는 대부분의 응용 프로그램은 정수가 나타낼 수있는 최대 수보다 훨씬 작은 수를 포함한다고 생각합니다 (객체 크기는 size_t의 모든 비트를 거의 사용하지 않습니다)). 이 경우 내 솔루션은 실제로 이진 검색 방식보다 성능이 저하되므로 솔루션이 모든 정수를 빠르게 루핑하더라도 후자가 선호됩니다 .
TL; DR : 실제 정수는 아마도이 간단한 알고리즘의 최악의 경우에 대한 편견이있을 것입니다. 이는 실제로 임의의 정수에 대해 O (1) 을 상각 한다는 사실에도 불구하고 결국 성능이 더 나빠질 것입니다 .
1 인수는 다음과 같습니다 (대략 초안). n 을 비트 수 (비트 폭)로 설정하십시오. n 비트로 표현할 수 있는 총 2 개의 n 정수가 있습니다 . 거기 2 , n은 1 - 로 시작하는 정수 1 (제 1 나머지 고정되고, 1 - N 무엇이든 될 수 비트). 이러한 정수는 MSB를 결정하기 위해 루프를 한 번만 개입하면됩니다. 또한, 거기 2 개 2 - N 으로 시작하는 정수 01 2 반복, 요구 (2) 3 - N 정수로 시작하는 001 3 반복 요구 등이.
가능한 모든 정수에 필요한 모든 반복을 요약 하고 총 정수 수인 2 n으로 나누면 n 비트 정수에 대한 MSB를 결정하는 데 필요한 평균 반복 수를 얻습니다 .
(1 * 2n-1 + 2 * 2n-2 + 3 * 2n-3 + ... + n) / 2n
이 일련의 평균 반복은 실제로 수렴 적이며 무한대 로 n에 대해 2의 제한이 있습니다.
따라서, 순진한 좌에서 우 알고리즘은 실제로 임의의 수의 비트에 대해 O (1) 의 상각 된 일정한 시간 복잡도를 갖는다 .
c99 가 우리에게 주었다 log2. 따라서이 log2페이지에서 볼 수있는 모든 특수 소스 구현이 필요하지 않습니다 . 다음 log2과 같이 표준 구현을 사용할 수 있습니다 .
const auto n = 13UL;
const auto Index = (unsigned long)log2(n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)
n의 0UL요구는,뿐만 아니라에 있기 때문에 보호되어야합니다 :
-∞가 리턴되고 FE_DIVBYZERO가 발생합니다.
나는 임의 세트가 있다는 것을 확인과 예를 쓴 Index위해 ULONG_MAX여기서는 https://ideone.com/u26vsi
비주얼 스튜디오 에 대한 추론 ephemient의 GCC에만 대답 입니다 :
const auto n = 13UL;
unsigned long Index;
_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)
_BitScanReverse상태에 대한 설명서Index 는 다음과 같습니다.
발견 된 첫 번째 설정 비트 (1)의 비트 위치로로드
실제로 나는 경우 것으로 나타났습니다 n이다 0UL그가 Index설정되어0UL 그것이이 될 것과 마찬가지로, n의 1UL. 그러나의 경우에는 문서에 보장 된 유일한 n의는 0UL반환이 있다는 것입니다 :
설정된 비트가 없으면 0
따라서, log2위 의 바람직한 구현 과 유사하게이 경우 리턴 Index값을 플래그 값으로 설정해야합니다 . ULONG_MAX이 플래그 값 을 사용하는 예를 다시 작성했습니다 : http://rextester.com/GCU61409
비트 연산자를 생각하십시오.
나는 처음으로 그 질문을 이해하지 못했다. 가장 왼쪽 비트 세트 (다른 것들은 0)로 정수를 만들어야합니다. cmp가 해당 값으로 설정되어 있다고 가정합니다.
position = sizeof(int)*8
while(!(n & cmp)){
n <<=1;
position--;
}
Josh의 벤치 마크를 확장하면 다음과 같이 clz를 향상시킬 수 있습니다
/***************** clz2 ********************/
#define NUM_OF_HIGHESTBITclz2(a) ((a) \
? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
: 0)
asm과 관련하여 : bsr과 bsrl이 있습니다 (이것은 "긴"버전입니다). 정상적인 것은 조금 더 빠를 수 있습니다.
당신이하려는 것은 정수의 정수 log2를 계산하는 것입니다.
#include <stdio.h>
#include <stdlib.h>
unsigned int
Log2(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1; int k=0;
for( step = 1; step < bits; ) {
n |= (n >> step);
step *= 2; ++k;
}
//printf("%ld %ld\n",x, (x - (n >> 1)) );
return(x - (n >> 1));
}
한 번에 1 비트 이상을 검색 할 수 있는지 확인하십시오.
unsigned int
Log2_a(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1;
int step2 = 0;
//observe that you can move 8 bits at a time, and there is a pattern...
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//}
//}
//}
for( step2=0; x>1L<<step2+8; ) {
step2+=8;
}
//printf("step2 %d\n",step2);
for( step = 0; x>1L<<(step+step2); ) {
step+=1;
//printf("step %d\n",step+step2);
}
printf("log2(%ld) %d\n",x,step+step2);
return(step+step2);
}
이 방법은 이진 검색을 사용합니다.
unsigned int
Log2_b(unsigned long x)
{
unsigned long n = x;
unsigned int bits = sizeof(x)*8;
unsigned int hbit = bits-1;
unsigned int lbit = 0;
unsigned long guess = bits/2;
int found = 0;
while ( hbit-lbit>1 ) {
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
//when value between guess..lbit
if( (x<=(1L<<guess)) ) {
//printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
hbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
//when value between hbit..guess
//else
if( (x>(1L<<guess)) ) {
//printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
lbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
}
if( (x>(1L<<guess)) ) ++guess;
printf("log2(x%ld)=r%d\n",x,guess);
return(guess);
}
더 읽기 쉬운 또 다른 이진 검색 방법
unsigned int
Log2_c(unsigned long x)
{
unsigned long v = x;
unsigned int bits = sizeof(x)*8;
unsigned int step = bits;
unsigned int res = 0;
for( step = bits/2; step>0; )
{
//printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
while ( v>>step ) {
v>>=step;
res+=step;
//printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
}
step /= 2;
}
if( (x>(1L<<res)) ) ++res;
printf("log2(x%ld)=r%ld\n",x,res);
return(res);
}
이것들을 테스트하고 싶기 때문에
int main()
{
unsigned long int x = 3;
for( x=2; x<1000000000; x*=2 ) {
//printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
}
return(0);
}
'아직도'접근 방식이기 때문에 이것을 넣는 것은 이미 주어진 다른 사람들과는 다른 것 같습니다.
-1이면 x==0그렇지 floor( log2(x))않으면를 반환 합니다 (최대 결과 31)
32 비트에서 4 비트 문제를 줄인 다음 테이블을 사용하십시오. 아마도 우아하지만 실용적 일 것입니다.
이것은 __builtin_clz이식성 문제 로 사용하고 싶지 않을 때 사용하는 것 입니다.
더 작게 만들기 위해 루프를 사용하여 매번 4 ~ r을 추가하여 최대 7 반복을 줄일 수 있습니다. 또는 (64 비트의 경우)와 같은 일부 하이브리드 : 루프를 8로 줄이고 테스트를 4로 줄입니다.
int log2floor( unsigned x ){
static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
int r = 0;
unsigned xk = x >> 16;
if( xk != 0 ){
r = 16;
x = xk;
}
// x is 0 .. 0xFFFF
xk = x >> 8;
if( xk != 0){
r += 8;
x = xk;
}
// x is 0 .. 0xFF
xk = x >> 4;
if( xk != 0){
r += 4;
x = xk;
}
// now x is 0..15; x=0 only if originally zero.
return r + wtab[x];
}
와우, 그것은 많은 답변이었습니다. 오래된 질문에 답한 것에 대해 죄송합니다.
int result = 0;//could be a char or int8_t instead
if(value){//this assumes the value is 64bit
if(0xFFFFFFFF00000000&value){ value>>=(1<<5); result|=(1<<5); }//if it is 32bit then remove this line
if(0x00000000FFFF0000&value){ value>>=(1<<4); result|=(1<<4); }//and remove the 32msb
if(0x000000000000FF00&value){ value>>=(1<<3); result|=(1<<3); }
if(0x00000000000000F0&value){ value>>=(1<<2); result|=(1<<2); }
if(0x000000000000000C&value){ value>>=(1<<1); result|=(1<<1); }
if(0x0000000000000002&value){ result|=(1<<0); }
}else{
result=-1;
}
이 답변은 다른 답변과 매우 유사합니다 ... 아.
내 겸손한 방법은 매우 간단합니다.
MSB (x) = INT [로그 (x) / 로그 (2)]
번역 : x의 MSB는 (Base x의 Log를 Base 2의 Log로 나눈 값)의 정수 값입니다.
이것은 모든 프로그래밍 언어에 쉽고 빠르게 적용 할 수 있습니다. 계산기에서 작동하는지 직접 확인하십시오.
코드:
// x>=1;
unsigned func(unsigned x) {
double d = x ;
int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
printf( "The left-most non zero bit of %d is bit %d\n", x, p);
}
또는 Y = 1을 설정하여 FPU 명령어 FYL2X (Y * Log2 X)의 정수 부분을 가져옵니다.
귀하의 질문은 정수 (아래 v라고 함)에 대한 것이며 부호없는 정수가 아니라고 가정합니다.
int v = 612635685; // whatever value you wish
unsigned int get_msb(int v)
{
int r = 31; // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.
while (!(v & 0x8000000) && r--) { // mask of the highest bit
v <<= 1; // multiply integer by 2.
}
return r; // will even return -1 if no bit was set, allowing error catch
}
부호를 고려하지 않고 작동하게하려면 추가 'v << = 1;'을 추가하면됩니다. 루프 전에 (그리고 r 값을 30으로 변경하십시오). 내가 잊어 버린 경우 알려주십시오. 나는 그것을 테스트하지 않았지만 정상적으로 작동해야합니다.
다른 포스터 는 바이트 단위 조회를 사용하여 조회 테이블 을 제공했습니다 . 경우에 당신은 여기에 사용하는 솔루션입니다 (대신 256 조회 항목의 메모리 32K의 비용으로) 좀 더 성능을 견디다 할 15 비트 룩업 테이블 에서, C # 7 에 대한 .NET은 .
흥미로운 부분은 테이블을 초기화하는 것입니다. 프로세스 수명 동안 비교적 작은 블록이기 때문에을 사용하여 관리되지 않는 메모리를 할당 Marshal.AllocHGlobal합니다. 보시다시피, 최대 성능을 위해 전체 예제는 기본으로 작성됩니다.
readonly static byte[] msb_tab_15;
// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
var p = new byte[0x8000];
for (byte n = 0; n < 16; n++)
for (int c = (1 << n) >> 1, i = 0; i < c; i++)
p[c + i] = n;
msb_tab_15 = p;
}
위의 코드를 통해 테이블을 한 번 초기화해야합니다. 읽기 전용이므로 단일 글로벌 사본을 동시에 액세스하기 위해 공유 할 수 있습니다. 이 표를 사용하면 정수 로그 2를 신속하게 조회 할 수 있습니다. 여기서는 모든 다양한 정수 폭 (8, 16, 32 및 64 비트)에 대해 여기서 찾고 있습니다.
0'가장 높은 세트 비트'의 개념이 정의되지 않은 유일한 정수인에 대한 테이블 항목에 값이 제공 -1됩니다. 이 구분은 아래 코드에서 0 값 상위 단어를 올바르게 처리하는 데 필요합니다. 더 이상 고민하지 않고 다양한 정수 프리미티브 각각에 대한 코드는 다음과 같습니다.
ulong (64 비트) 버전
/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 0x40) - 1; // handles cases v==0 and MSB==63
int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}
uint (32 비트) 버전
/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
if ((int)v <= 0)
return (int)((v >> 26) & 0x20) - 1; // handles cases v==0 and MSB==31
int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}
위의 다양한 과부하
public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];
이것은 전문 성능 테스트 하니스와 비교 한 수많은 대안에 대해 .NET 4.7.2에서 최고의 성능을 나타내는 완벽하고 작동하는 솔루션입니다. 이들 중 일부는 아래에 언급되어 있습니다. 테스트 파라미터는 모든 65 비트 위치의 균일 한 밀도, 즉 0 ... 31/63 더하기 값 0(결과 -1을 생성 함)이었습니다. 목표 인덱스 위치 아래 의 비트 는 무작위로 채워졌습니다. 테스트는 JIT 최적화가 활성화 된 x64 전용 릴리스 모드였습니다.
그것이 나의 공식적인 대답의 끝입니다. 다음은 위의 코드의 성능과 정확성을 검증하기 위해 실행 한 테스트와 관련된 대체 테스트 후보를위한 소스 코드 링크 및 참고 사항입니다.
위에서 제공 한 Tab16A로 코딩 된 버전은 많은 실행에서 일관된 승자였습니다. 활발한 작업 / 스크래치 형태의 다양한 후보는 여기 , 여기 및 여기 에서 찾을 수 있습니다 .
후보 1 명. 최고 One_Tab16A 622,496 후보 2 명. 최고 One_Tab16C 628,234 후보 3 명. 최고 One_Tab8A 649,146 후보 4 명. 최고 One_Tab8B 656,847 후보 5 명. 최고 One_Tab16B 657,147 후보자 6 명. 최고 One_Tab16D 659,650 7 _highest_one_bit_UNMANAGED.HighestOne_U 702,900 8 de_Bruijn.IndexOfMSB 709,672 9 _old_2. 최고 One_Old2 715,810 10 _test_A.HighestOne8 757,188 11 _old_1.HighestOne_Old1 757,925 12 _test_A.HighestOne5 (안전하지 않은) 760,387 13 _test_B.HighestOne8 (안전하지 않은) 763,904 14 _test_A.HighestOne3 (안전하지 않은) 766,433 15 _test_A.HighestOne1 (안전하지 않은) 767,321 16 _test_A.HighestOne4 (안전하지 않은) 771,702 17 _test_B.HighestOne2 (안전하지 않은) 772,136 18 _test_B.HighestOne1 (안전하지 않은) 772,527 19 _test_B.HighestOne3 (안전하지 않은) 774,140 20 _test_A.HighestOne7 (안전하지 않은) 774,581 21 _test_B.HighestOne7 (안전하지 않은) 775,463 22 _test_A.HighestOne2 (안전하지 않은) 776,865 23 개 후보자 최다 1_NoTab 777,698 24 _test_B.HighestOne6 (안전하지 않은) 779,481 25 _test_A.HighestOne6 (안전하지 않은) 781,553 26 _test_B.HighestOne4 (안전하지 않은) 785,504 27 _test_B.HighestOne5 (안전하지 않은) 789,797 28 _test_A.HighestOne0 (안전하지 않은) 809,566 29 _test_B.HighestOne0 (안전하지 않은) 814,990 30 _highest_one_bit.HighestOne 824,345 30 _bitarray_ext.RtlFindMostSignificantBit 894,069 31 명 후보. 최고 One_Naive 898,865
ntdll.dll!RtlFindMostSignificantBitP / Invoke 를 통한 끔찍한 성능은 다음과 같습니다.
[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);
전체 실제 기능이 있기 때문에 너무 나쁩니다.
RtlFindMostSignificantBit:
bsr rdx, rcx
mov eax,0FFFFFFFFh
movzx ecx, dl
cmovne eax,ecx
ret
이러한 5 가지 라인에서 비롯된 성능 저하를 상상할 수 없으므로 관리 / 기본 전환 처벌에 대한 책임이 있습니다. 또한이 테스트 short에서 128 바이트 (및 256 바이트) byte(8 비트) 조회 테이블 보다 32KB (및 64KB) (16 비트) 직접 조회 테이블을 선호한다는 사실에 놀랐습니다 . 다음은 16 비트 조회에서보다 경쟁력이 있다고 생각했지만 후자는 지속적으로이 성능을 능가했습니다.
public static int HighestOne_Tab8A(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;
int j;
j = /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
return j + msb_tab_8[v >> j];
}
마지막으로 지적해야 할 것은 deBruijn 방법이 더 나아지지 않았다는 사실에 충격을 받았다는 것입니다. 이것이 내가 이전에 널리 사용했던 방법입니다.
const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
N_bsr64 = 0x03F79D71B4CB0A89;
readonly public static sbyte[]
bsf64 =
{
63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5,
},
bsr64 =
{
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,
};
public static int IndexOfLSB(ulong v) =>
v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;
public static int IndexOfMSB(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;
v |= v >> 1; v |= v >> 2; v |= v >> 4; // does anybody know a better
v |= v >> 8; v |= v >> 16; v |= v >> 32; // way than these 12 ops?
return bsr64[(v * N_bsr64) >> 58];
}
이 SO 질문에서 얼마나 우수하고 훌륭한 deBruijn 방법 에 대한 많은 토론 이 있으며, 나는 동의하는 경향이있었습니다. 내 추측은 deBruijn 및 직접 조회 테이블 메소드 (가장 빠른 것으로 밝혀 짐)는 모두 테이블 조회를 수행해야하며 둘 다 매우 최소 분기를 수행하지만 deBruijn 만 64 비트 곱하기 연산을 수행한다는 것입니다. 나는 IndexOfMSBdeBruijn이 아닌 여기 에서만 기능을 테스트했지만 IndexOfLSB더 적은 수의 작업 (위 참조)이 있기 때문에 후자가 훨씬 더 나은 기회를 얻길 기대하며 LSB에 계속 사용할 것입니다.
'Programming' 카테고리의 다른 글
| 정규식 옵션 문자를 일치시키는 방법 (0) | 2020.07.28 |
|---|---|
| Firefox 및 Opera의 웹 폰트 스무딩 및 앤티 앨리어싱 (0) | 2020.07.28 |
| 컴파일 된 언어와 해석 된 언어의 차이점은 무엇입니까? (0) | 2020.07.28 |
| DTO와 DAO 개념과 MVC [폐쇄] (0) | 2020.07.28 |
| Microsoft Excel ActiveX 컨트롤이 비활성화 되었습니까? (0) | 2020.07.28 |