자신보다 크거나 같은 최소의 2의 제곱수는?

주어진 수보다 크거나 같은 최소의 2의 제곱수를 찾아야 될 경우가 있다.

대표적으로 FFT를 기반으로 하는 신호처리의 준비단계.

적절한 개수를 지정해놓고 DFT를 할 수도 있지만, 역시 미친듯한 속도를 내려면 2의 제곱수가 짱짱맨이다.

 

https://en.wikipedia.org/wiki/Power_of_two 에서 빌려옴

 

사실, 요즘 컴퓨팅 환경에서는 이를 위한 가장 빠른 방법[...] 따윈 알아볼 의미가 크게는 없다.

x86/x64 환경이라면 어셈블리 단위에서 LZCNT(Count Leading Zeros) 명령을  지원하기 때문이다.

Visual C++라면 __lzcnt64() 등의 함수로, GCC라면 __builtin_ia32_lzcnt_u64() 등의 함수로 사용할 수 있다.

 

하지만, 세상은 언제나 그렇게 만만하진 않은 법.

파이썬이나 매틀랩 같은 언어에서는 이런 계열의 함수를 지원하지 않고 있다^[각주:1].

 

그래서 네 가지의 방식들을 C++와 C#으로 각각 구현하여 약 20억번씩(정확히는 0x8000000 회) 수행한 시간을 측정해봤다.

• 1. 단순 shift: 0이 될 때까지 우측으로 shift하여 횟수 카운트
• 2. 우측으로 shift 하면서 or로 합침
• 3. 수학적 방법: $lo{g}_{2}n$을 활용
• 4. CPU의 LZCNT 명령 활용

 

실제 수행해본 결과^[각주:2]는 아래와 같았다.

 

3번의 경우 C++는 long double로, C#은 double로 구현하여 성능 차이가 발생함

 

당연히 4번(LZCNT)가 가장 빠르지만, 놀랍게도 2번 방식 역시 상당히 쓸만한 수준의 성능을 보여줬다.

20억회 정도 돌린 결과라는 점을 생각해보면 LZCNT 등의 명령을 못 쓰는 경우엔 바로 2번으로 가야 한다.

게다가, C# 에서는 2번이 4번보다 오히려 약간 빠른 성능을 보여줬다.

 

C++ 버전으로 작성된 코드들은 아래와 같다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

//1. 단순 shift 연산 uint64_t FindPower2_1(const uint64_t n) {     uint64_t p = 1;     while (p < n) {         p <<= 1;     }       return p; }   //2. 우측으로 shift 하면서 or로 합침 uint64_t FindPower2_2(const uint64_t n) {     if (!n) {         return 1;     }     uint64_t ret = n - 1;     ret |= (ret >> 1);     ret |= (ret >> 2);     ret |= (ret >> 4);     ret |= (ret >> 8);     ret |= (ret >> 16);     ret |= (ret >> 32);       return ret + 1; }   //3. log2() uint64_t FindPower2_3(const uint64_t n) {     if (!n) {         return 1;     }     const long double p = ceill(log2l((long double)n));     return (uint64_t)powl(2, p); }   //4. leading zero uint64_t FindPower2_4(const uint64_t n) {     return 0x8000000000000000ULL >> (__lzcnt64(n - 1) - 1); }

 

 

1. 어쩌면 있는데 내가 못 찾았을 수도 있음 [본문으로]
2. AMD Ryzen9 5900X, 64GB [본문으로]