binary gap

binary gap문제.

이렇게 생겼다. (링크)
아래는  python으로 짜본거.

from math import log
def tz(n): #trailing zeros
    return int(log(n - (n&(n-1)), 2)) #= int(log(n& -n, 2))
 
def binarygap(n):
    sol = 0
    while True:
        n = n >> (tz(n) + 1)
        if n == 0 : break
        sol = max(sol, tz(n))
    return sol

위에 trailing zeros 얻는 과정(n- (n&(n-1)))이 약간 tricky한데, 천천히 생각해보면 알 수 있다.
아래는 n&-n의 계산된 몇가지 예시. 보면 대충 알 수 있다.
>>> for i in range(1, 40):
...     print bin(i), bin(i & -i)
... 
0b1 0b1
0b10 0b10
0b11 0b1
0b100 0b100
0b101 0b1
0b110 0b10
0b111 0b1
0b1000 0b1000
0b1001 0b1
0b1010 0b10
0b1011 0b1
0b1100 0b100
0b1101 0b1
0b1110 0b10
0b1111 0b1
0b10000 0b10000
0b10001 0b1
0b10010 0b10
0b10011 0b1
0b10100 0b100
0b10101 0b1
0b10110 0b10
0b10111 0b1
0b11000 0b1000
0b11001 0b1
0b11010 0b10
0b11011 0b1
0b11100 0b100
0b11101 0b1
0b11110 0b10
0b11111 0b1
0b100000 0b100000
0b100001 0b1
0b100010 0b10
0b100011 0b1
0b100100 0b100
0b100101 0b1
0b100110 0b10
0b100111 0b1

비트를 하나하나 순차적으로 검사해도 O(log n)이라 연산을 저렇게 tricky하게 해도 complexity의 이득은 없다. worst case에서는 둘 다 O(log n). best case에서 큰 차이가 난다. O(log log n)

비슷한 원리로, binary로 나타냈을 때 1이 몇개 나오는지 맞추는 문제도 있다.
python코드는 다음과 같다.

def howmany1s(n) :
     count = 0
     while(n >0):
             n = n&(n-1)
             count += 1
     return count