배열의 길이를 2의 거듭제곱으로 만들기: 이진수의 보수, & 연산

 

문제

출처 : 프로그래머스

 

 

풀이

 

def solution(arr):
    l = len(arr)
    while bin(l).count('1') != 1:
        l += l & (-l)
    return arr + [0] * (l - len(arr))

 

이진수 풀이법이 마음에 들었는데, 이해가 안되는 부분이 있었고 공부하다보니 2의 보수를 복습할 수 있었다.

2의 보수란, 십진수 12를 -12로 만들 때는 -만 붙이면 되지만 12를 이진수로 표현할 때는 -가 없으므로 이를 표현하기 위한 방법을 말한다.

기존 이진수의 bit들을 반대로 만들고, 맨 끝에 +1을 하면 된다.

 

이진수로:   00001100 (12)
 l      =  00001100
-l      =  11110100  (2의 보수 표현)

 

또한 l & -l 연산을 하면 2의 보수의 정의에 따라 맨 오른쪽 끝의 1만 남는다.

l        = 00001100
-l       = 11110100
--------------------
l & -l   = 00000100  ← 바로 이 값이 오른쪽에서 가장 먼저 나오는 1 (값 4)

 

 

 

* str에 .count()로 문자열의 개수를 셀 수도 있다!