빠른 로그 기준 2개의 상한 계산
빠른 계산 방법은 무엇입니까?(long int) ceiling(log_2(i))입력 및 출력이 64비트 정수인 경우부호 있는 정수 또는 부호 없는 정수에 대한 솔루션을 사용할 수 있습니다.가장 좋은 방법은 여기서 볼 수 있는 것과 유사한 약간 비틀거리는 방법이 될 것이라고 생각하지만, 제 자신의 방법을 시도하기보다는 이미 잘 테스트된 것을 사용하고 싶습니다.일반적인 해결책은 모든 양의 값에 적용됩니다.
예를 들어, 2,3,4,5,6,7,8의 값은 1,2,2,3,3,3입니다.
편집: 지금까지 가장 좋은 방법은 임의의 수의 기존 빠른 비트백 또는 레지스터 방법을 사용하여 정수/플로어 로그 베이스 2(MSB의 위치)를 계산한 다음, 입력이 2의 거듭제곱이 아닌 경우 1을 추가하는 것으로 보입니다. 빠른 는 2의 거 듭 곱 빠 비 단 검 사 는 위 트 른 제 에 대 한 ▁the ▁2 ▁for 는 사 검 ▁is(n&(n-1)).
편집 2: 정수 로그와 선행 영점 방법에 대한 좋은 자료는 헨리 S의 해커 기쁨의 섹션 5-3과 11-4입니다.워렌.이것이 제가 찾은 가장 완벽한 치료법입니다.
편집 3: 이 기술은 유망해 보입니다: https://stackoverflow.com/a/51351885/365478
편집 4: C23은 분명히 stdc_first_(선행/추종)_(1/0)을 추가하고 있습니다.
gcc로 제한할 수 있는 경우 선행 0비트의 수를 반환하고 약간의 작업으로 원하는 작업을 수행하는 데 사용할 수 있는 내장 함수 집합이 있습니다.
int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)
이 알고리즘은 이미 게시되었지만 다음 구현은 매우 소형이므로 분기가 없는 코드로 최적화되어야 합니다.
int ceil_log2(unsigned long long x)
{
static const unsigned long long t[6] = {
0xFFFFFFFF00000000ull,
0x00000000FFFF0000ull,
0x000000000000FF00ull,
0x00000000000000F0ull,
0x000000000000000Cull,
0x0000000000000002ull
};
int y = (((x & (x - 1)) == 0) ? 0 : 1);
int j = 32;
int i;
for (i = 0; i < 6; i++) {
int k = (((x & t[i]) == 0) ? 0 : j);
y += k;
x >>= k;
j >>= 1;
}
return y;
}
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
printf("%d\n", ceil_log2(atol(argv[1])));
return 0;
}
Windows에서 64비트 프로세서를 컴파일하는 경우에는 이 작업이 가능해야 합니다._BitScanReverse64는 고유 함수입니다.
#include <intrin.h>
__int64 log2ceil( __int64 x )
{
unsigned long index;
if ( !_BitScanReverse64( &index, x ) )
return -1LL; //dummy return value for x==0
// add 1 if x is NOT a power of 2 (to do the ceil)
return index + (x&(x-1)?1:0);
}
32비트의 경우 _BitScanReverse64를 _BitScanReverse로 1번 또는 2번 호출하여 에뮬레이트할 수 있습니다.x(long*)&x(1)[1]의 상위 32비트를 확인한 다음, 필요한 경우 하위 32비트를(long*)&x(0)로 확인합니다.
접근법을 합니다.log2, 하기 위해 반올림 인 조정을 결합한 입니다.lg_down()아래와 같이
/* base-2 logarithm, rounding down */
static inline uint64_t lg_down(uint64_t x) {
return 63U - __builtin_clzl(x);
}
/* base-2 logarithm, rounding up */
static inline uint64_t lg_up(uint64_t x) {
return lg_down(x - 1) + 1;
}
기본적으로 반올림 결과에 1을 더하는 것은 2의 정확한 거듭제곱을 제외한 모든 값에 대해 이미 올바른 것입니다(그 경우 이후).floor그리고.ceil접근 방식은 동일한 답변을 반환해야 하므로 입력 값에서 1을 빼면 충분합니다(다른 경우에는 답변이 변경되지 않습니다).
은 보통 한 거듭제곱을 이는의예일 2정을곱명시적으 2빠하다식간다는보니릅듭거가추로반으확적한▁a예의▁this▁of▁by:▁(▁value가추e▁the(aches더▁than▁that다▁usually빠▁is▁explicit니▁adjust▁for▁the릅▁two▁slightly▁faster:▁exact).!!(x & (x - 1))용어). 비교 및 조건부 연산 또는 분기를 피하며, 인라인할 때 단순할 가능성이 더 높으며, 벡터화 등에 더 적합합니다.
는 대부분의 합니다. "count leading bits" 기능은 "count leading bits" 기능을 합니다.__builtin_clzl도 비슷한 " 그나다플비예것은제을다공니합한슷폼랫른러예(다▁but:니제▁something공합▁offer▁similar것").BitScanReverse비주얼 스튜디오 (Visual Studio).
불행하게도, 이 많은 사람들이 다음에 대한 잘못된 답을 반환합니다.log(1)이 그때에로 에.__builtin_clzl(0)이는 gcc 문서에 기반한 정의되지 않은 동작입니다.물론 일반적인 "count leading zero" 함수는 0에서 완벽하게 정의된 동작을 가지고 있지만, gcc 내장형은 x86의 BMI ISA 확장 이전에는 정의되지 않은 동작 자체를 사용했을 것이기 때문에 이러한 방식으로 정의됩니다.
당신이 알고 있다면 이 문제를 해결할 수 있을 것입니다.lzcnt를사한지침을 lzcntx86을 은 x86을 .bsr처음부터 실수를 하고, 아마도 "count leading zero" 명령어가 있는 경우 액세스할 수 있는 방법을 제공할 것입니다.
#include "stdafx.h"
#include "assert.h"
int getpos(unsigned __int64 value)
{
if (!value)
{
return -1; // no bits set
}
int pos = 0;
if (value & (value - 1ULL))
{
pos = 1;
}
if (value & 0xFFFFFFFF00000000ULL)
{
pos += 32;
value = value >> 32;
}
if (value & 0x00000000FFFF0000ULL)
{
pos += 16;
value = value >> 16;
}
if (value & 0x000000000000FF00ULL)
{
pos += 8;
value = value >> 8;
}
if (value & 0x00000000000000F0ULL)
{
pos += 4;
value = value >> 4;
}
if (value & 0x000000000000000CULL)
{
pos += 2;
value = value >> 2;
}
if (value & 0x0000000000000002ULL)
{
pos += 1;
value = value >> 1;
}
return pos;
}
int _tmain(int argc, _TCHAR* argv[])
{
assert(getpos(0ULL) == -1); // None bits set, return -1.
assert(getpos(1ULL) == 0);
assert(getpos(2ULL) == 1);
assert(getpos(3ULL) == 2);
assert(getpos(4ULL) == 2);
for (int k = 0; k < 64; ++k)
{
int pos = getpos(1ULL << k);
assert(pos == k);
}
for (int k = 0; k < 64; ++k)
{
int pos = getpos( (1ULL << k) - 1);
assert(pos == (k < 2 ? k - 1 : k) );
}
for (int k = 0; k < 64; ++k)
{
int pos = getpos( (1ULL << k) | 1);
assert(pos == (k < 1 ? k : k + 1) );
}
for (int k = 0; k < 64; ++k)
{
int pos = getpos( (1ULL << k) + 1);
assert(pos == k + 1);
}
return 0;
}
@egosys에서 언급한 gcc 내장형을 사용하여 몇 가지 유용한 매크로를 만들 수 있습니다.빠르고 거친 바닥(log2(x)) 계산을 위해 다음을 사용할 수 있습니다.
#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
비슷한 천장(log2(x))의 경우 다음을 사용합니다.
#define FAST_LOG2_UP(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
후자는 내장형에 대한 이중 호출을 피하기 위해 더 많은 gcc 특성을 사용하여 추가로 최적화할 수 있지만, 여기에 필요한지 잘 모르겠습니다.
다음 코드 스니펫은 지원 컴파일러(Clang)를 사용하여 컴파일할 때 컴파일러 내장형을 사용하기 위해 @dgobbi's와 같은 플레인-C 메서드를 확장하는 안전하고 휴대 가능한 방법입니다.메서드의 맨 위에 이 옵션을 놓으면 메서드가 사용 가능할 때 기본 제공 기능을 사용합니다.기본 제공 기능을 사용할 수 없는 경우 메소드는 표준 C 코드로 되돌아갑니다.
#ifndef __has_builtin
#define __has_builtin(x) 0
#endif
#if __has_builtin(__builtin_clzll) //use compiler if possible
return ((sizeof(unsigned long long) * 8 - 1) - __builtin_clzll(x)) + (!!(x & (x - 1)));
#endif
진정한 가장 빠른 솔루션:
63개 항목으로 구성된 이진 검색 트리입니다.이것들은 0에서 63까지의 2의 거듭제곱입니다.트리를 만드는 일회성 생성 함수입니다.잎은 검정력의 로그 기저 2(기본적으로 숫자 1-63)를 나타냅니다.
정답을 찾으려면 트리에 숫자를 입력하고 항목보다 큰 리프 노드로 이동합니다.리프 노드가 정확히 같으면 결과는 리프 값입니다.그렇지 않으면 결과는 잎 값 + 1입니다.
복잡도는 O(6)로 고정됩니다.
정수 출력을 사용하여 정수(64비트 또는 다른 비트)의 로그 베이스 2를 찾는 것은 설정된 가장 중요한 비트를 찾는 것과 같습니다. 왜죠?로그 베이스 2는 1에 도달하기 위해 숫자를 2로 나눌 수 있는 횟수이기 때문입니다.
설정된 MSB를 찾는 한 가지 방법은 0이 될 때까지 매번 오른쪽으로 1씩 비트 시프트하는 것입니다.또 다른 더 효율적인 방법은 비트 마스크를 통해 일종의 이진 검색을 수행하는 것입니다.
MSB 이외에 다른 비트가 설정되어 있는지 확인하면 천장 부분을 쉽게 해결할 수 있습니다.
아래 코드는 입력 x > = 1 동안 작동합니다. 입력 clog2(0)는 정의되지 않은 답을 얻을 것입니다(로그(0)는 무한이므로 의미가 있습니다...). 다음을 원할 경우 (x == 0)에 대한 오류 검사를 추가할 수 있습니다.
unsigned int clog2 (unsigned int x)
{
unsigned int result = 0;
--x;
while (x > 0) {
++result;
x >>= 1;
}
return result;
}
그런데 log2의 바닥 코드는 비슷합니다: (다시, x > = 1로 가정합니다.)
unsigned int flog2 (unsigned int x)
{
unsigned int result = 0;
while (x > 1) {
++result;
x >>= 1;
}
return result;
}
글을 쓸 때 x86-64에 대한 가장 빠른 방법을 알려드릴 것이고, 인수 < 2^63에 맞는 빠른 층이 있다면 일반적인 기술을 알려드릴 것이고, 전체 범위를 신경쓰신다면 아래를 참고하시기 바랍니다.
저는 다른 답변의 품질이 낮은 것에 대해 놀랐습니다. 왜냐하면 그 답변들은 바닥을 얻는 방법을 알려주지만 (조건부 및 모든 것을 사용하는) 매우 비싼 방법으로 천장까지 변형시키기 때문입니다.
를 들어 빨리 수 , 를 들어 그로바닥수있, 를들어경을 사용하면,__builtin_clzll바닥은 다음과 같이 매우 쉽게 확보할 수 있습니다.
unsigned long long log2Floor(unsigned long long x) {
return 63 - __builtin_clzll(x);
}
unsigned long long log2Ceiling(unsigned long long x) {
return log2Floor(2*x - 1);
}
x가 정확히 2의 거듭제곱이 아닌 한 결과에 1을 더하기 때문에 작동합니다.
다음과 같은 천장의 다른 구현은 컴파일러 탐색기에서 x86-64 어셈블리어의 차이를 참조하십시오.
auto log2CeilingDumb(unsigned long x) {
return log2Floor(x) + (!!(x & (x - 1)));
}
제공:
log2Floor(unsigned long): # @log2Floor(unsigned long)
bsr rax, rdi
ret
log2CeilingDumb(unsigned long): # @log2CeilingDumb(unsigned long)
bsr rax, rdi
lea rcx, [rdi - 1]
and rcx, rdi
cmp rcx, 1
sbb eax, -1
ret
log2Ceiling(unsigned long): # @log2Ceiling(unsigned long)
lea rax, [rdi + rdi]
add rax, -1
bsr rax, rax
ret
전체 범위의 경우 이전 답변에 나와 있습니다.return log2Floor(x - 1) + 1와 비교하여 의 명령어를 .x86-64에서는 명령어를 사용할 수 없습니다.
저는 64비트 "가장 높은 비트"의 여러 구현을 벤치마킹했습니다.가장 "지점 없는" 코드는 사실 가장 빠른 것이 아닙니다.
은 나의 이것나입니다.highest-bit.c원본 파일:
int highest_bit_unrolled(unsigned long long n)
{
if (n & 0xFFFFFFFF00000000) {
if (n & 0xFFFF000000000000) {
if (n & 0xFF00000000000000) {
if (n & 0xF000000000000000) {
if (n & 0xC000000000000000)
return (n & 0x8000000000000000) ? 64 : 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_bs(unsigned long long n)
{
const unsigned 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;
}
int highest_bit_shift(unsigned long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}
static int count_ones(unsigned long long d)
{
d = ((d & 0xAAAAAAAAAAAAAAAA) >> 1) + (d & 0x5555555555555555);
d = ((d & 0xCCCCCCCCCCCCCCCC) >> 2) + (d & 0x3333333333333333);
d = ((d & 0xF0F0F0F0F0F0F0F0) >> 4) + (d & 0x0F0F0F0F0F0F0F0F);
d = ((d & 0xFF00FF00FF00FF00) >> 8) + (d & 0x00FF00FF00FF00FF);
d = ((d & 0xFFFF0000FFFF0000) >> 16) + (d & 0x0000FFFF0000FFFF);
d = ((d & 0xFFFFFFFF00000000) >> 32) + (d & 0x00000000FFFFFFFF);
return d;
}
int highest_bit_parallel(unsigned long long n)
{
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return count_ones(n);
}
int highest_bit_so(unsigned long long x)
{
static const unsigned long long t[6] = {
0xFFFFFFFF00000000ull,
0x00000000FFFF0000ull,
0x000000000000FF00ull,
0x00000000000000F0ull,
0x000000000000000Cull,
0x0000000000000002ull
};
int y = (((x & (x - 1)) == 0) ? 0 : 1);
int j = 32;
int i;
for (i = 0; i < 6; i++) {
int k = (((x & t[i]) == 0) ? 0 : j);
y += k;
x >>= k;
j >>= 1;
}
return y;
}
int highest_bit_so2(unsigned long long value)
{
int pos = 0;
if (value & (value - 1ULL))
{
pos = 1;
}
if (value & 0xFFFFFFFF00000000ULL)
{
pos += 32;
value = value >> 32;
}
if (value & 0x00000000FFFF0000ULL)
{
pos += 16;
value = value >> 16;
}
if (value & 0x000000000000FF00ULL)
{
pos += 8;
value = value >> 8;
}
if (value & 0x00000000000000F0ULL)
{
pos += 4;
value = value >> 4;
}
if (value & 0x000000000000000CULL)
{
pos += 2;
value = value >> 2;
}
if (value & 0x0000000000000002ULL)
{
pos += 1;
value = value >> 1;
}
return pos;
}
는 이은입니다.highest-bit.h:
int highest_bit_unrolled(unsigned long long n);
int highest_bit_bs(unsigned long long n);
int highest_bit_shift(unsigned long long n);
int highest_bit_parallel(unsigned long long n);
int highest_bit_so(unsigned long long n);
int highest_bit_so2(unsigned long long n);
그리고 메인 프로그램(복사 및 붙여넣기 모두 죄송합니다):
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "highest-bit.h"
double timedelta(clock_t start, clock_t end)
{
return (end - start)*1.0/CLOCKS_PER_SEC;
}
int main(int argc, char **argv)
{
int i;
volatile unsigned long long v;
clock_t start, end;
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_unrolled(v);
}
end = clock();
printf("highest_bit_unrolled = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_parallel(v);
}
end = clock();
printf("highest_bit_parallel = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_bs(v);
}
end = clock();
printf("highest_bit_bs = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_shift(v);
}
end = clock();
printf("highest_bit_shift = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_so(v);
}
end = clock();
printf("highest_bit_so = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_so2(v);
}
end = clock();
printf("highest_bit_so2 = %6.3fs\n", timedelta(start, end));
return 0;
}
저는 이 다양한 인텔 x86 박스를 구형과 신형으로 사용해 보았습니다.
그highest_bit_unrolled(search)는 (unrolled binary search)보다 훨씬 빠른 highest_bit_parallel(무장애 비트ops).은 이은보빠다니릅다것보다 .highest_bit_bs루프가 함), (검색 루프가 발생함), (검색 루프가 발생함)보다 .highest_bit_shift(이동 및 카운트 루프를 반복합니다.)
highest_bit_unrolled또한 승인된 SO 답변의 속도가 빠릅니다.highest_bit_so및에서 ()입니다.highest_bit_so2).
벤치마크는 연속적인 비트를 커버하는 1비트 마스크를 순환합니다.이는 언롤링된 이진 검색에서 분기 예측을 물리치기 위한 것으로, 현실적입니다. 실제 프로그램에서는 입력 사례가 비트 위치의 인접성을 나타내지 않을 것 같습니다.
오래된 오된것대결다니입에 가 있습니다.Intel(R) Core(TM)2 Duo CPU E4500 @ 2.20GHz:
$ ./highest-bit
highest_bit_unrolled = 6.090s
highest_bit_parallel = 9.260s
highest_bit_bs = 19.910s
highest_bit_shift = 21.130s
highest_bit_so = 8.230s
highest_bit_so2 = 6.960s
모델의 Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz:
highest_bit_unrolled = 1.555s
highest_bit_parallel = 3.420s
highest_bit_bs = 6.486s
highest_bit_shift = 9.505s
highest_bit_so = 4.127s
highest_bit_so2 = 1.645s
하드웨어의 는 ""입니다.highest_bit_so2에 더 가까워집니다.highest_bit_unrolled최신 하드웨어에서 사용할 수 있습니다.같지는 ; 지금은 주이완같않지다니습지.highest_bit_so, 말정뒤고지, 더느니다보다 .highest_bit_parallel.
것, 가장빠것은른것.highest_bit_unrolled분기가 가장 많은 코드를 포함합니다.고유한 전용 코드 조각을 사용하여 서로 다른 조건 집합에 도달한 모든 반환 값.
"모든 가지를 피하라"는 직관이 항상 옳은 것은 아닙니다.현대적인 (그리고 더 이상 현대적이지 않은) 프로세서는 분기에 의해 방해받지 않기 위해 상당한 교활함을 포함합니다.
highest_bit_unrolled2011년 12월 TXR 언어로 도입되었습니다(실수 있음, 디버깅 이후).
최근에 저는 브랜치가 없는 더 멋지고 더 컴팩트한 코드가 더 빠르지 않을까 생각하기 시작했습니다.
저는 그 결과에 다소 놀랐습니다.
틀림없이, 코드는 정말로 다음과 같아야 합니다.#ifdefGNU C를 위한 -ing과 일부 컴파일러 프리미티브를 사용하지만 이식성에 관한 한 그 버전은 유지됩니다.
80비트 또는 128비트 플로트를 사용할 수 있는 경우 해당 유형으로 캐스트한 다음 지수 비트를 읽습니다.이 링크에는 세부 정보(최대 52비트 정수)와 몇 가지 다른 방법이 있습니다.
http://graphics.stanford.edu/ ~seander/bithacks.html #IntegerLogIEEE64 Float
또한 ffmpeg 소스를 확인합니다.저는 그들이 매우 빠른 알고리즘을 가지고 있다는 것을 압니다. 사이즈로 할 수 , 와 같은 것을 쉽게 할 수 .if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x);
단순 선형 검색은 평균 2개 미만의 비교(모든 정수 크기에 대해)가 필요하기 때문에 균등하게 분포된 정수에 대한 옵션일 수 있습니다.
/* between 1 and 64 comparisons, ~2 on average */
#define u64_size(c) ( \
0x8000000000000000 < (c) ? 64 \
: 0x4000000000000000 < (c) ? 63 \
: 0x2000000000000000 < (c) ? 62 \
: 0x1000000000000000 < (c) ? 61 \
...
: 0x0000000000000002 < (c) ? 2 \
: 0x0000000000000001 < (c) ? 1 \
: 0 \
)
최상위 비트에 대한 일종의 이진 검색입니다.
stanford.edu 에 게시된 비트 단위 운영 해킹에 대한 좋은 참조: 비트 트위들링 해킹.이 참조에는 log2 값을 계산하기 위한 여러 알고리즘을 포함하여 많은 예가 있습니다.여기에는 이와 유사한 접근법과 더 나은 접근법이 포함됩니다.
저는 가장 중요한 비트에 대한 일종의 이진 검색이 간단한 솔루션의 최대 60개 이상의 루프보다 빠를 것이라는 생각을 했습니다.이 이동합니다.n각 반복마다 MSB에서 0이 되는 마지막 이동 값의 절반까지.
값의 경우 비트의 6회 . 즉, 는 64비트, floor log2입니다. 이는 다음의 플로어 로그2입니다.n.
제가 측정한 바와 같이, 이 접근 방식의 성능은 아래의 두 번째 예의 단순 루프보다 별로 좋지 않았습니다.
// floor log2 in 6 max iterations for unsigned 64-bit values.
//
int floor_log2(unsigned long long n)
{
int shval = 32;
int msb = 0;
while (shval) {
if (n >> shval) {
msb += shval;
n >>= shval;
}
shval >>= 1;
}
return msb;
}
int ceil_log2(unsigned long long n)
{
return floor_log2(2 * n - 1);
}
간단한 알고리즘:
int floor_log2_simple(unsigned long long n)
{
int c = 0;
while (n) {
n >>= 1;
c++;
}
return c - 1;
}
Rust에 구현된 동일한 알고리즘은 거의 동일하게 수행되었습니다.상위 접근 방식은 약간 더 나은 성능을 발휘했지만 평균적으로 몇 나노초밖에 차이가 나지 않았습니다.알고리즘을 아무리 조정해도 더 나은 성능을 제공하지 못했습니다.
음...
언급URL : https://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling
'programing' 카테고리의 다른 글
| Vuex에서 사용자 지정 개체 메서드를 사용하는 방법은 무엇입니까? (0) | 2023.07.15 |
|---|---|
| 원격 저장소에서 로컬 Git 분기를 삭제한 후 삭제 (0) | 2023.07.15 |
| TypeScript에서 제네릭 배열을 어떻게 정의합니까? (0) | 2023.07.15 |
| 상대 레이아웃의 백분율 너비 (0) | 2023.07.15 |
| Springboot 1.X와 Springboot 2.0의 차이점 (0) | 2023.07.15 |