1. 문제 소개

1611. Minimum One Bit Operations to Make Integers Zero

2. 나의 풀이

처음 문제를 보았을 때에 발견한 규칙은 다음과 같았다.

input	0	1	2	3	4	5	6	7
output	0	1	3	2	7	6	5	4

이처럼 비트가 바뀔 때마다 일종의 Jump가 일어난다는 점이다.
검색을 해보니 그레이 코드(Gray Code)와 관련이 있었는데 그레이 코드는 다음과 같다.

그레이 코드(Gray Code)는 인접한 수 사이의 이진 표현이 한 비트만 다른 코드 체계이다.
예를 들어, 0에서 1로, 1에서 3으로 넘어갈 때처럼 한 번에 한 비트만 바뀌는 순서로 배열된다.
이 문제에서의 연산 규칙이 바로 이 그레이 코드 전이 규칙과 동일하기 때문에,
주어진 수 n을 0으로 만드는 최소 연산 횟수는 결국 그레이 코드의 역함수(inverse Gray Code) 값을 구하는 것과 같았다.
코드는 아래와 같은 이진연산으로 구현했는데, 이진연산에 익숙하지 않아 참고해가며 풀었다.
시간복잡도는 $O(log n)$이다.

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        def f(n):
            if n == 0:
                return 0
            msb = n.bit_length() - 1
            mask = 1 << msb
            return (1 << (msb + 1)) - 1 - f(n ^ mask)
        return f(n)

3. 다른 풀이

가장 간결해 보이는 코드를 가져왔다.

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        ans = 0
        while n:
            ans ^= n
            n >>= 1
        return ans

4. 결론

비트연산자는 도통 모르겠다.
익숙하지 않아서 그런 것 같다.