64비트 정수용 log2 고속 컴퓨팅
뛰어난 프로그래밍 리소스인 비트 트위들링 헥스는 32비트 정수의 log2를 계산하는 다음 방법을 제안합니다(여기서).
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
static const char LogTable256[256] =
{
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};
unsigned int v; // 32-bit word to find the log of
unsigned r; // r will be lg(v)
register unsigned int t, tt; // temporaries
if (tt = v >> 16)
{
r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}
라고 언급하고 있습니다.
룩업 테이블 메서드는 32비트 값의 로그를 찾기 위해 약 7개의 작업만 수행하면 됩니다.64비트 용량으로 확장할 경우 약 9회 작업이 필요합니다.
그러나 안타깝게도 알고리즘을 64비트 정수로 확장하기 위해 실제로 어떤 방법을 사용해야 하는지에 대한 추가 정보는 제공하지 않습니다.
이런 종류의 64비트 알고리즘이 어떻게 생겼는지 힌트는 없나요?
고유 함수는 매우 빠르지만, 컴파일러에 의존하지 않는 진정한 크로스 플랫폼 구현에는 여전히 부족합니다.관심 있는 분들을 위해 제가 직접 이 주제를 연구하면서 얻은 가장 빠른 분기 없는 CPU 추상화 DeBrujn 알고리즘입니다.
const int tab64[64] = {
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};
int log2_64 (uint64_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}
다음으로 낮은 2의 거듭제곱으로 반올림하는 부분은 2의 거듭제곱에서, 후행 0의 수를 얻는 부분은 BitScan에서 가져왔습니다.(bb & -bb)이 코드는 1로 설정된 오른쪽 끝의 비트를 골라내는 것입니다.이것은 값을 2의 다음 거듭제곱으로 반올림한 후에는 필요하지 않습니다).
참고로 32비트 구현은
const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31};
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}
다른 계산 방법과 마찬가지로 log2에서는 입력값이 0보다 커야 합니다.
GCC를 사용하는 경우 이 경우 룩업테이블은 불필요합니다.
GCC에는 선행 제로의 양을 결정하기 위한 내장 함수가 있습니다.
내장 기능:
최상위 비트 위치에서 시작하는 x의 선행 0비트 수를 반환합니다.0으로 하다
다음과 같이 정의할 수 있습니다.
#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
부호 없이 긴 인트라에 사용할 수 있습니다.결과는 반올림됩니다.
x86 및 AMD64 GCC에서는 명령어로 컴파일되므로 솔루션이 매우 빠릅니다(룩업 테이블보다 훨씬 빠릅니다).
작업 예:
#include <stdio.h>
#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
int main(void) {
unsigned long long input;
while (scanf("%llu", &input) == 1) {
printf("log(%llu) = %u\n", input, LOG2(input));
}
return 0;
}
컴파일 출력 : https://godbolt.org/z/16GnjszMs
Magic Number를 blue force로 강제하여 곱셈 및 룩업을 사용하는 O(lg(N) 연산에서 N비트 정수의 로그 기반 2를 64비트로 변환하려고 했습니다.말할 필요도 없이 그것은 시간이 걸렸다.
그리고 데스몬드의 답을 찾아 그의 마법 번호를 시작점으로 삼기로 했다.6코어 프로세서가 있기 때문에 0x07부터 병렬로 실행했습니다.EDD5E59A4E28C2 / 6배수나는 그것이 즉시 무언가를 발견했다는 것에 놀랐다.알고보니 0x07EDD5E59A4E28C2/2가 동작.
여기 0x07의 코드가 있습니다.EDD5E59A4E28C2를 사용하면 시프트와 뺄셈을 절약할 수 있습니다.
int LogBase2(uint64_t n)
{
static const int table[64] = {
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, 63 };
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return table[(n * 0x03f6eaf2cd271461) >> 58];
}
만약 당신이 c++의 답을 찾고 있고, 당신이 여기에 도착했다면, 그것은 결국 0을 세는 것이기 때문에, 당신은 그것을 얻었다고 godbolt.org의 콜은 말합니다.bsr.std::countl_zeroC++20부터 이용할 수 있습니다.-std=gnu++2a컴파일러 명령줄로 이동
Base-2 정수 로그
이것은 64비트 부호 없는 정수에 대해 수행하는 작업입니다.이것은 최상위 비트의 인덱스에 해당하는 2진수 로그의 바닥을 계산합니다.이 방법은 log₂64 = 6단계에서 항상 실행되는 롤되지 않은 루프를 사용하기 때문에 많은 수의 경우 매우 빠릅니다.
기본적으로, 이 방법은 {0 k k 5 5: 2^(2^k) } = { 2 ,², 2 2, 2 ⁶, 2 , } = { 4294967296, 65536, 256, 16, 4, 1 } 의 순서로 작은 제곱을 차감하고 k 의 지수 값을 차감하는 것입니다.
int uint64_log2(uint64_t n)
{
#define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }
int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;
#undef S
}
유효하지 않은 입력값 0(첫 번째 입력값)을 지정하면 -1이 반환됩니다.-(n == 0)확인중입니다).로 기동하는 것을 전혀 예상하지 못한 경우n == 0, 대신할 수 있습니다.int i = 0;이니셜라이저 및 추가assert(n != 0);기능 시작 시.
Base-10 정수 로그
base-10 정수 로그는 마찬가지로 계산할 수 있습니다.로그는 log '2'가 19.2659이므로 테스트하는 최대 제곱은 10'입니다.(주의: 이것은 본질적으로 느린 정수 나눗셈을 사용하기 때문에 base-10 정수 대수를 달성하는 가장 빠른 방법은 아닙니다.보다 빠른 구현은 기하급수적으로 증가하는 값을 가진 축전지(acculator)를 사용하여 사실상 이진 검색을 수행하는 것입니다.)
int uint64_log10(uint64_t n)
{
#define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }
int i = -(n == 0);
S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
return i;
#undef S
}
다음은 임시 장치를 추가로 사용하지 않는 매우 작고 빠른 확장 기능입니다.
r = 0;
/* If its wider than 32 bits, then we already know that log >= 32.
So store it in R. */
if (v >> 32)
{
r = 32;
v >>= 32;
}
/* Now do the exact same thing as the 32 bit algorithm,
except we ADD to R this time. */
if (tt = v >> 16)
{
r += (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
r += (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}
여기 체인으로 만든 것이 있습니다.ifs. 추가 일시적 사용 없음.하지만 가장 빠르지 않을 수도 있어.
if (tt = v >> 48)
{
r = (t = tt >> 8) ? 56 + LogTable256[t] : 48 + LogTable256[tt];
}
else if (tt = v >> 32)
{
r = (t = tt >> 8) ? 40 + LogTable256[t] : 32 + LogTable256[tt];
}
else if (tt = v >> 16)
{
r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}
이걸 가져가세요.
typedef unsigned int uint;
typedef uint64_t ulong;
uint as_uint(const float x) {
return *(uint*)&x;
}
ulong as_ulong(const double x) {
return *(ulong*)&x;
}
uint log2_fast(const uint x) {
return (uint)((as_uint((float)x)>>23)-127);
}
uint log2_fast(const ulong x) {
return (uint)((as_ulong((double)x)>>52)-1023);
}
: 입력 정수 력력 。x is float조각으로 재해석합니다.IEEE float형식은 30-23 비트의 지수를 바이어스 127이 있는 정수로 저장하므로 23비트를 오른쪽으로 이동하고 바이어스를 빼면 log2(x)를 얻을 수 있습니다.입력의 64비트 정수 의 경우x is double여기서 지수는 비트 62-52(오른쪽 52비트)이며 지수 바이어스는 1023입니다.
이것은 2009년 3월 22일에 SPWolly에서 약간 수정된 것입니다(자세한 내용은 게시물을 참조하십시오).
double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>52)-1023; // assumes x86 endianness
참고: 일부 사용자는 일부 상황에서 컴파일할 경우 오답이 발생할 수 있다고 지적했습니다.
알고리즘은 기본적으로 어떤 바이트가 최상위 1비트를 포함하는지 찾아내고 검색에서 해당 바이트를 검색하여 바이트의 로그를 찾은 다음 바이트 위치에 추가합니다.
32비트 알고리즘의 간단한 버전을 다음에 나타냅니다.
if (tt = v >> 16)
{
if (t = tt >> 8)
{
r = 24 + LogTable256[t];
}
else
{
r = 16 + LogTable256[tt];
}
}
else
{
if (t = v >> 8)
{
r = 8 + LogTable256[t];
}
else
{
r = LogTable256[v];
}
}
다음은 동등한 64비트알고리즘입니다
if (ttt = v >> 32)
{
if (tt = ttt >> 16)
{
if (t = tt >> 8)
{
r = 56 + LogTable256[t];
}
else
{
r = 48 + LogTable256[tt];
}
}
else
{
if (t = ttt >> 8)
{
r = 40 + LogTable256[t];
}
else
{
r = 32 + LogTable256[ttt];
}
}
}
else
{
if (tt = v >> 16)
{
if (t = tt >> 8)
{
r = 24 + LogTable256[t];
}
else
{
r = 16 + LogTable256[tt];
}
}
else
{
if (t = v >> 8)
{
r = 8 + LogTable256[t];
}
else
{
r = LogTable256[v];
}
}
}
오리지널보다 더 좋은 사이즈 타입의 알고리즘을 생각해 냈습니다.
unsigned int v = 42;
unsigned int r = 0;
unsigned int b;
for (b = sizeof(v) << 2; b; b = b >> 1)
{
if (v >> b)
{
v = v >> b;
r += b;
}
}
★★★★★★b = sizeof(v) << 2b자형 v자형 v자형이다. 여기서는 곱셈 대신 시프트를 사용했습니다(마음에 들었기 때문에).
검색 테이블을 알고리즘에 추가하여 속도를 높일 수 있지만 이는 개념 증명에 가깝습니다.
언급URL : https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
'IT이야기' 카테고리의 다른 글
| 터미널을 사용하여 Mac OS X에서 C 프로그램을 실행하는 방법 (0) | 2022.06.18 |
|---|---|
| "역할 컬렉션을 느릿느릿 초기화하지 못했습니다" 최대 절전 모드 예외 해결 방법 (0) | 2022.06.18 |
| 화살표 연산자 '->'는 Java에서 무엇을 합니까? (0) | 2022.06.18 |
| Fortran은 많은 계산을 위해 C보다 최적화가 더 쉽습니까? (0) | 2022.06.18 |
| &((구조명*)NULL -> b)는 C11에서 정의되지 않은 동작을 야기합니까? (0) | 2022.06.18 |