[python] 2의 n제곱인지 확인

문제

https://school.programmers.co.kr/learn/courses/30/lessons/181857

프로그래머스

나의 풀이

 

2의 제곱수인지 확인하는 법 

•  2는 비트로 나타냈을 때:  1 = 0001, 2 = 0010, 4 = 0100, 8 = 1000, 16 = 1 0000, 32 = 11 0000, 64 = 100 0000 ...
•  2의 제곱수 규칙: 왼쪽에 1이고 나머지는 0임
•  만약 n을 2의 제곱수라고 했을 때, 이전 값인 n-1과 곱하게 되면 맨 왼쪽 수는 0이 된다.
•  2의 제곱수인지 알고 싶다면 n&(n-1)해서 0인지 확인하면 됨

 

def solution(arr):
    n = len(arr)
    li = [ 2**i for i in range(30)]
    
    if n&(n-1)==0:
        return arr
    else:
        cnt = 0
        for i in li:
            if i > n:
                cnt = i
                break
        
        for i in range(cnt-n):
            arr.append(0)
        return arr

 

인상적인 풀이

def solution(arr):
    n = len(arr)
    if n & (n - 1) == 0: 
        return arr
    m = 1
    while m < n:
        m <<= 1
    return arr + [0] * (m - n)

진짜 깔끔하다.

 

만약 2의 제곱수가 아니라면

m이라는 변수에 1부터 2,4,8,16... 으로 2의 제곱수가 되게하면서,

n보다 커질때까지 2의 제곱이 된다.

 

그렇게 구해진 m에 배열의 길이를 제외하여 뒤에 붙여야될 0의 갯수를 구함;;

대단...

 

참고로

비트 연산자(Bitwise Operators)는

&(and), |(or), ^(xor), ~(not), <<(왼쪽 비트단위 밀기), >>(오른쪽 비트단위 밀기)가 있다.