leetcode : Concatenation of Consecutive Binary Numbers

https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/

Concatenation of Consecutive Binary Numbers - LeetCode

 

비트연산 문제를 해결해 본 적이 거의 없어서 좀 까다로웠다.

아이디어는 이렇다. i를 1부터 n까지 순회시키면서 현재 i를 이진수 자릿수만큼 기존 값을 왼쪽으로 옮기고 거기에 i를 더해주는 것이다. 위 그림을 보면 쉽게 이해 가능하다. 그리고 수시로 10^9+7로 나눠주면 된다.

 

문제는 현재 i의 자릿수를 어떻게 구할거냐인데 내 친구는 log2함수를 썼다. 하지만 로그를 쓰지 않고도 추적할 수 있는 방법이 있다. 자릿수가 바뀌는 경우를 생각해보자. 자릿수가 바뀌는 경우는 1111 이렇게 1로 가득찬 상태에서 1이 더해졌을때 10000 이렇게 맨 앞자리만 1이고 나머지는 0인 형태로 바뀌는 경우밖에 없다. 10000에서 1을 뺀 1111과 10000을 &연산하면 0이 나온다. 이걸 통해 우리는 현재 i가 100...00형태인지 아닌지, 즉 자릿수가 1 늘었는지 아닌지를 알 수 있다. (i - 1) & i가 0일때마다 자릿수 추적 변수를 1 증가시켜주면 된다.

 

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        shift = 0
        answer = 0
        
        for i in range(1, n+1):
            if (i & (i-1)) == 0:
                shift += 1
            answer = ((answer << shift) + i) % (10**9 + 7)
        
        return answer