비트 연산을 이용한 빠른 지수 연산

비트 연산을 이용한 빠른 지수 연산을 수행하는 방법으로는 흔히 "Exponentiation by Squaring"이라고 불리는 알고리즘이 사용됩니다. 이 알고리즘은 거듭제곱을 빠르게 계산하기 위해 분할 정복 기법을 사용하며, 특히 큰 수의 거듭제곱을 계산할 때 매우 효율적입니다.

Exponentiation by Squaring 알고리즘 설명

이 알고리즘은 지수를 2로 나누면서 제곱을 반복적으로 수행하여 거듭제곱을 계산합니다. 기본 아이디어는 다음과 같습니다:

• $n$이 짝수일 때: $x^n = (x^{n/2})^2$
• $n$이 홀수일 때: $x^n = x \cdot x^{n-1}$

단계별 절차

1. 기본 사례:
   • $ n = 0 $: $ x^0 = 1 $
   • $ n = 1 $: $ x^1 = x $
2. 재귀 사례:
   • $ n $이 짝수일 때: $x^n = (x^{n/2})^2$
   • $ n $이 홀수일 때: $ x^n = x \cdot (x^{n-1}) $

파이썬 구현 예제

비트 연산을 이용하여 이 알고리즘을 파이썬으로 구현하면 다음과 같습니다:

def fast_exponentiation(x, n):
    result = 1
    base = x
    
    while n > 0:
        if n % 2 == 1:  # n이 홀수인 경우
            result *= base
        base *= base  # base를 제곱
        n //= 2  # n을 2로 나눔 (비트 시프트 연산 n >>= 1 을 사용해도 됨)
    
    return result

# 예제 사용
x = 2
n = 10
print(f"{x}^{n} = {fast_exponentiation(x, n)}")  # 출력: 2^10 = 1024

비트 연산 활용

위의 코드에서 n //= 2 부분을 n >>= 1로 대체하면 비트 시프트 연산을 이용하게 됩니다.

def fast_exponentiation_bitwise(x, n):
    result = 1
    base = x
    
    while n > 0:
        if n & 1:  # n의 마지막 비트가 1인지 확인 (n % 2 == 1)
            result *= base
        base *= base  # base를 제곱
        n >>= 1  # n을 오른쪽으로 1비트 시프트 (n을 2로 나눔)
    
    return result

# 예제 사용
x = 2
n = 10
print(f"{x}^{n} = {fast_exponentiation_bitwise(x, n)}")  # 출력: 2^10 = 1024

이 방법을 사용하면 거듭제곱 계산을 로그 시간 복잡도로 수행할 수 있어 매우 효율적입니다.