어떤 정수의 밑을 2로 하는 로그값 $log_{2}x$을 정확하게 구하는 방법

어떤 정수 n이 주어졌을때, n보다 작거나 같으면서 가장 가까운 2의 거듭제곱이 필요할때가 있다

 

구체적으로 $2^{x} = n$을 만족하는 정수 x를 찾고 싶을 때가 있다.

 

제일 쉬운 방법은?

 

import math

n = int(input())

print(int(math.log2(n)))

 

근데 얘는 문제가 n이 엄청 크면 실수오차 발생으로 틀릴 수 있다는거

 

이를 피하는 방법은 2씩 직접 곱해서 찾는 방법이 있고

 

import math

n = int(input())

x = 0
v = 1

while v < n:
    
    v *= 2
    
    if v > n:
    
        break
        
    x += 1
    
print(x)

 

 

그런데 이 방법은 O(logN)이다.

 

메소드 중에 bit_length()라는 메소드가 있다

 

어떤 정수를 이진수로 표현할때 그 이진수의 비트 수를 반환함

 

예를 들어 10 = 1010(2)니까 10의 bit_length()값은 4이다

 

 

 

int(math.log2(n))은 무엇을 의미하는가?

 

$2^{x} <= n$을 만족하는 가장 큰 정수 x이다.

 

즉, n을 이진수로 나타낼때, n의 최상위 비트를 나타내는 것으로, n의 비트 길이 - 1과 같다.

 

n = int(input())

print(n.bit_length()-1)

 

 

항상 정확하게 O(1)에 계산하며, 보통은 math.log2보다 훨씬 빠르다.