자신보다 크거나 같은 최소의 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. 수학적 방법: \( log_2 {n}  \)을 활용
• 4. CPU의 LZCNT 명령 활용

 

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

 

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

 

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

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

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

 

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

 

//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 [본문으로]