C++에서 정수 log2()를 수행하는 방법은 무엇입니까?
https://stackoverflow.com/questions/994593
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
C++ 표준 라이브러리에서는 부동 소수점 로그 방법만 찾았습니다.이제 로그를 사용하여 이진 트리에서 인덱스 수준을 찾습니다( floor(2log(index)) ).
코드(C++):
int targetlevel = int(log(index)/log(2));
일부 가장자리 요소(값이 2^n인 요소)의 경우 log가 n.0 대신 n-1.999999999999를 반환할까봐 걱정됩니다.이 두려움이 맞나요?항상 정답을 반환하도록 내 명령문을 수정하려면 어떻게 해야 합니까?
해결책
대신이 방법을 사용할 수 있습니다.
int targetlevel = 0;
while (index >>= 1) ++targetlevel;
참고 : 이것은 인덱스를 수정합니다. 변경되지 않으면 다른 임시 int를 만듭니다.
코너 케이스는 인덱스가 0 일 때입니다. 아마도 별도로 확인하고 예외를 던지거나 인덱스 == 0 인 경우 오류를 반환해야 할 것입니다.
다른 팁
최신 x86 또는 x86-64 플랫폼을 사용하고 있다면(아마도 그럴 것입니다) 다음을 사용하세요. bsr 부호 없는 정수에서 가장 높은 세트 비트의 위치를 반환하는 명령어입니다.이는 log2()와 정확히 동일하다는 것이 밝혀졌습니다.다음은 호출하는 짧은 C 또는 C++ 함수입니다. bsr 인라인 ASM 사용:
#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
uint32_t y;
asm ( "\tbsr %1, %0\n"
: "=r"(y)
: "r" (x)
);
return y;
}
빠른 정수 로그를 원한다면2 작동, 다음 기능 mylog2() 부동 소수점 정확도에 대해 걱정하지 않고도 할 것입니다.
#include <limits.h>
static unsigned int mylog2 (unsigned int val) {
if (val == 0) return UINT_MAX;
if (val == 1) return 0;
unsigned int ret = 0;
while (val > 1) {
val >>= 1;
ret++;
}
return ret;
}
#include <stdio.h>
int main (void) {
for (unsigned int i = 0; i < 20; i++)
printf ("%u -> %u\n", i, mylog2(i));
putchar ('\n');
for (unsigned int i = 0; i < 10; i++)
printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));
return 0;
}
위의 코드에는 또한 작은 테스트 하네스가 있으므로 동작을 확인할 수 있습니다.
0 -> 4294967295
1 -> 0
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 2
8 -> 3
9 -> 3
10 -> 3
11 -> 3
12 -> 3
13 -> 3
14 -> 3
15 -> 3
16 -> 4
17 -> 4
18 -> 4
19 -> 4
4294967286 -> 31
4294967287 -> 31
4294967288 -> 31
4294967289 -> 31
4294967290 -> 31
4294967291 -> 31
4294967292 -> 31
4294967293 -> 31
4294967294 -> 31
4294967295 -> 31
돌아올 것입니다 UINT_MAX 정의되지 않은 결과의 표시로 0의 입력 값의 경우,이를 확인해야 할 사항입니다 (유효한 서명되지 않은 정수는 높은 로그가 있습니다).
그건 그렇고, 정확히이를 수행 할 수있는 미친 듯이 빠른 해킹이 있습니다 (2의 보완 번호로 가장 높은 비트를 찾으십시오) 여기. 나는 속도가 본질이 아니라면 그것들을 사용하는 것을 제안하지 않을 것입니다 (나는 가독성을 선호합니다). 그러나 당신은 그것들이 존재한다는 것을 알고 있어야합니다.
Base-2 정수 로그
다음은 64 비트 부호없는 정수를 위해하는 일입니다. 이것은 Base-2 로그의 바닥을 계산하며, 이는 가장 중요한 비트의 색인과 동일합니다. 이 방법은입니다 담배를 피우고 빠릅니다 로그 64 = 6 단계에서 항상 실행되는 롤링되지 않은 루프를 사용하기 때문에 많은 숫자의 경우.
본질적으로, 그것이하는 일은 시퀀스에서 점진적으로 작은 사각형을 빼는 것입니다 {0 ≤ k ≤ 5 : 2^(2^k)} = {2³², 2¹, 2 ⁸, 2⁴, 2², 2¹} = {4294967296, 65536, 256 , 16, 4, 2, 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¹⁶입니다.
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
}
이것은 위의 의견에 제안되었습니다. GCC Buildins 사용 :
static inline int log2i(int x) {
assert(x > 0);
return sizeof(int) * 8 - __builtin_clz(x) - 1;
}
static void test_log2i(void) {
assert_se(log2i(1) == 0);
assert_se(log2i(2) == 1);
assert_se(log2i(3) == 1);
assert_se(log2i(4) == 2);
assert_se(log2i(32) == 5);
assert_se(log2i(33) == 5);
assert_se(log2i(63) == 5);
assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
}
나는 당신이 사용하고있는 공식의 부동 소수점 정확도에 아무런 문제가 없었습니다 (그리고 1에서 2까지의 숫자를 빠르게 점검합니다.31 -1은 오류를 찾지 못했지만 걱정이된다면이 기능을 대신 사용할 수 있습니다.이 기능은 동일한 결과를 반환하고 내 테스트에서 약 66% 빠릅니다.
int HighestBit(int i){
if(i == 0)
return -1;
int bit = 31;
if((i & 0xFFFFFF00) == 0){
i <<= 24;
bit = 7;
}else if((i & 0xFFFF0000) == 0){
i <<= 16;
bit = 15;
}else if((i & 0xFF000000) == 0){
i <<= 8;
bit = 23;
}
if((i & 0xF0000000) == 0){
i <<= 4;
bit -= 4;
}
while((i & 0x80000000) == 0){
i <<= 1;
bit--;
}
return bit;
}
int targetIndex = floor(log(i + 0.5)/log(2.0));
이것은 표준이 아니거나 반드시 휴대용이지만 일반적으로 작동합니다. 얼마나 효율적인지 모르겠습니다.
정수 지수를 부유 식 점수의 충분한 정밀도로 변환하십시오. 정밀도가 충분하다고 가정하면 표현이 정확합니다.
IEEE 부동 소수점 번호의 표현을 찾고 지수를 추출한 다음 기본 2 로그를 찾기 위해 필요한 조정을하십시오.
C ++ 11을 사용하는 경우 ConstExPR 기능으로 만들 수 있습니다.
constexpr std::uint32_t log2(std::uint32_t n)
{
return (n > 1) ? 1 + log2(n >> 1) : 0;
}
위의 비슷한 답변이 있습니다. 이 답변
- 64 비트 숫자로 작동합니다
- 반올림 유형을 선택할 수 있습니다
- 테스트/샘플 코드를 포함합니다
기능 :
static int floorLog2(int64_t x)
{
assert(x > 0);
return 63 - __builtin_clzl(x);
}
static int ceilLog2(int64_t x)
{
if (x == 1)
// On my system __builtin_clzl(0) returns 63. 64 would make more sense
// and would be more consistent. According to stackoverflow this result
// can get even stranger and you should just avoid __builtin_clzl(0).
return 0;
else
return floorLog2(x-1) + 1;
}
테스트 코드 :
for (int i = 1; i < 35; i++)
std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
<<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;
이 함수는 숫자 간격을 나타내는 데 필요한 비트의 수를 결정합니다 : [0..maxValue].
unsigned binary_depth( unsigned maxvalue )
{
int depth=0;
while ( maxvalue ) maxvalue>>=1, depth++;
return depth;
}
결과에서 1을 빼면 얻을 수 있습니다 floor(log2(x)),, 그것은 정확한 표현 log2(x) 언제 x 2의 힘입니다.
엑스와이Y-1
00-1
110
221
321
432
532
632
732
843
나무를 얼마나 깊이 투사합니까? 정수 값으로 강제하기 위해 숫자로 Say ... +/- 0.00000001의 범위를 설정할 수 있습니다.
2^N 값을 계산할 때 (부동 소수점 포인트가 가장 가까운 2의 전력으로 라운드 이후) 계산할 때 로그 2가 정확도를 잃지 않아야하기 때문에 실제로 1.99999999와 같은 숫자를 누르지 않을 것이라고 확신합니다.
내가 쓴이 기능 여기
// The 'i' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
unsigned int log2Val = 0 ;
// Count push off bits to right until 0
// 101 => 10 => 1 => 0
// which means hibit was 3rd bit, its value is 2^3
while( x>>=1 ) log2Val++; // div by 2 until find log2. log_2(63)=5.97, so
// take that as 5, (this is a traditional integer function!)
// eg x=63 (111111), log2Val=5 (last one isn't counted by the while loop)
return log2Val ;
}
이것은 오래된 게시물이지만 한 줄 알고리즘을 공유합니다.
unsigned uintlog2(unsigned x)
{
unsigned l;
for(l=0; x>1; x>>=1, l++);
return l;
}
재 작성 토드 레먼더 일반적인 대답 :
#include <climits>
template<typename N>
constexpr N ilog2(N n) {
N i = 0;
for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
}
return i;
}
Clang -O3 루프를 풀어줍니다.
0000000100000f50 pushq %rbp
0000000100000f51 movq %rsp, %rbp
0000000100000f54 xorl %eax, %eax
0000000100000f56 cmpl $0xffff, %edi
0000000100000f5c setg %al
0000000100000f5f shll $0x4, %eax
0000000100000f62 movl %eax, %ecx
0000000100000f64 sarl %cl, %edi
0000000100000f66 xorl %edx, %edx
0000000100000f68 cmpl $0xff, %edi
0000000100000f6e setg %dl
0000000100000f71 leal (,%rdx,8), %ecx
0000000100000f78 sarl %cl, %edi
0000000100000f7a leal (%rax,%rdx,8), %eax
0000000100000f7d xorl %edx, %edx
0000000100000f7f cmpl $0xf, %edi
0000000100000f82 setg %dl
0000000100000f85 leal (,%rdx,4), %ecx
0000000100000f8c sarl %cl, %edi
0000000100000f8e leal (%rax,%rdx,4), %eax
0000000100000f91 xorl %edx, %edx
0000000100000f93 cmpl $0x3, %edi
0000000100000f96 setg %dl
0000000100000f99 leal (%rdx,%rdx), %ecx
0000000100000f9c sarl %cl, %edi
0000000100000f9e leal (%rax,%rdx,2), %ecx
0000000100000fa1 xorl %eax, %eax
0000000100000fa3 cmpl $0x1, %edi
0000000100000fa6 setg %al
0000000100000fa9 orl %ecx, %eax
0000000100000fab popq %rbp
언제 n 일정하고 결과는 컴파일 시간으로 계산됩니다.
플로팅 포인트 수가 작동하는 방식 (Crudely, Mantissa * 2^지수)을 감안할 때, 2의 전력 인 2^127의 숫자는 오류없이 정확하게 표시됩니다.
이것은 사소하지만 오히려 해킹 된 솔루션을 제공합니다. 부동 소수점 번호의 비트 패턴을 정수로 해석하고 지수를보십시오. 이것은 위의 David Thornley의 해결책입니다.
float f = 1;
for (int i = 0; i < 128; i++)
{
int x = (*(int*)(&f)>>23) - 127;
int l = int(log(f) / log(2));
printf("i = %d, log = %d, f = %f quick = %d\n",
i, l, f, x);
f *= 2;
}
사실이 아닙니다 어느 정수는 플로트로 표시 될 수 있습니다. Mantissa가 표현할 수있는 것보다 비트가 적습니다. 32 비트 플로트에서는 23 비트 가치가 있습니다.
