Skip to main content

BIT Hacks - 자연수 승수 계산을 비트연산으로 빠르게 하는 법

· 4 min read

자연수 승수 연산에 한해, 비트연산 트릭을 활용하여 C++에서 기본으로 제공하는 pow() 함수보다 빠르게 계산하는 방법을 알아봅니다.

featured

TL;DR​

double pow_int(double base, int exp)
{
    double result = 1.;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

01_result

원리​

실수 aa와 자연수 nn에 대하여, ana^n을 계산하는 경우를 살펴보겠습니다.

여기서 nn은 2진법 변환을 통해 다음과 같이 표현할 수 있습니다.

n=∑k=0bk×2k, where bk=0 or 1n = \sum_{k=0} b_k \times 2^k, \text{ where } b_k = 0 \text{ or } 1

위 식을 이용하면 ana^n은 다음과 같이 변형됩니다.

an=a∑k=0bk×2ka^n = a^{\sum_{k=0} b_k \times 2^k} =∏k=0abk×2k(∵xm+n=xm×xn)= \prod_{k=0} a^{b_k \times 2^k} \quad (\because x^{m+n} = x^m \times x^n) =∏k=0(a2k)bk(∵xmn=(xm)n)= \prod_{k=0} (a^{2^k})^{b_k} \quad (\because x^{mn} = (x^m)^n) =(b0×a)×(b1×a2)×(b2×(a2)2)×(b3×((a2)2)2)×⋯= (b_0 \times a) \times (b_1 \times a^2) \times (b_2 \times (a^2)^2) \times (b_3 \times ((a^2)^2)^2) \times \cdots

이 식의 의미를 해석해보면 다음과 같습니다.

  1. nn을 2진법으로 나타내었을 때 낮은 자리수부터 확인(b0,b1,...b_0, b_1, ...)

  2. 매 bkb_k를 확인할 때마다, a,a2,(a2)2,...a, a^2, (a^2)^2, ...의 형태로 계속 제곱해 나감

  3. bkb_k가 00이면 그냥 넘어가고,

    bkb_k가 11이면 2에서 구한 a2ka^{2^k}를 누적하여 곱함

예시​

353^5를 계산해보겠습니다. 여기서 a=3a=3이고, n=5n=5가 됩니다.

  1. 먼저, nn을 2진법으로 변환하여 bkb_k들을 구합니다.
n=5=1+4=1×20+0×21+1×22n=5=1+4=1 \times 2^0 + 0 \times 2^1 + 1 \times 2^2 i.e. b0=1,b1=0,b2=1, and bk=0 for k≥3\text{i.e. } b_0=1, b_1=0, b_2 = 1, \text{ and } b_k = 0 \text{ for } k \geq 3

  1. 이제 낮은 자리 수부터 확인하며 누적곱 작업을 수행합니다.

    1. 누적곱의 초기 값은 곱셈의 항등원인 1로 설정합니다.

    2. aa는 3입니다.

      b0b_0을 확인합니다. b0b_0가 11이므로, 1에 3을 곱합니다.

      결과는 3이 됩니다.

    3. a2a^2는 9입니다.

      b1b_1을 확인합니다. b1b_1가 00이므로, 아무것도 곱하지 않습니다.

      결과는 여전히 3입니다.

    4. (a2)2(a^2)^2는 81입니다.

      b2b_2을 확인합니다. b2b_2가 11이므로, 3에 81을 곱합니다.

      결과는 243이 됩니다.

    5. 이후의 bkb_k들은 모두 00이므로 이후에는 아무것도 곱하지 않습니다.

    6. 따라서 최종 결과는 243입니다.

코드로의 적용(C++)​

위 내용을 코드로 변환하면 다음과 같습니다.

변수명의 의미를 고려하여, 위 식에서 aa를 base로, nn을 exp로 명명하였습니다.

double pow_int(double base, int exp)
{
    double result = 1.;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

  1. 누적곱을 수행하기 위한 result 변수의 초기 값을 곱셈의 항등원인 1로 설정합니다.

  2. exp 값이 유효한 동안 while 반복문을 수행합니다.

    1. exp를 2진법으로 표현하였을 때 의 가장 낮은 자리수를 구합니다. (exp & 1)

      만약 이 값이 1이라면, bib_i가 1인 경우에 해당합니다. 따라서, 현재의 base 값을 result에 누적하여 곱합니다.

      만약 이 값이 0이라면, bib_i가 0인 경우에 해당합니다. 따라서 result에 아무것도 곱하지 않고 넘어갑니다.

      예를 들어, exp의 b0b_0 값이 1이었다면, while 반복문을 맨 처음 수행할 때 이 if 조건이 참이 되어, result *= base; 구문이 수행되고, 위 설명에서 aa를 곱해주는 것과 동일한 작업이 이루어집니다.

    2. exp를 오른쪽으로 한 칸 비트시프트를 수행합니다. (exp >>= 1;)

      이를 통해, 방금 살펴본 bib_i가 버려지고, 그 다음 자리에 해당하는 bi+1b_{i+1}이 가장 낮은 자리로 옮겨지는 과정이 반복됩니다.

    3. base를 제곱합니다. (base *= base;)

      이를 통해 (...(a2)2)...)2(...(a^2)^2)...)^2에 해당하는 반복 연산이 수행됩니다.

  3. 최종적으로 누적곱이 수행된 결과를 반환합니다. (return result;)

pow() 함수와의 비교용 예시 코드​

코드​

#include <iostream>

double pow_int(double base, int exp)
{
    double result = 1.;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

int main()
{
    const int N = 100000000;
    double base = 12.345;
    int exp = 67;
    double result1, result2;

    std::cout << base << "^" << exp << "\n\n";

    auto startT1 = clock();
    for (int i = 0; i < N; ++i)
        result1 = pow(base, exp);
    auto endT1 = clock();
    std::cout << "Calculated by pow() function\n";
    std::cout << "Answer: " << result1 << "\n";
    std::cout << "Elapsed time: " << (endT1 - startT1) << " ms\n\n";
    
    auto startT2 = clock();
    for (int i = 0; i < N; ++i)
        result2 = pow_int(base, exp);
    auto endT2 = clock();
    std::cout << "Calculated by pow_int() function\n";
    std::cout << "Answer: " << result2 << "\n";
    std::cout << "Elapsed time: " << (endT2 - startT2) << " ms\n\n";

    return 0;
}

결과​

i5-9500 @ 3.00GHz 기준

01_result