파이썬 알고리즘 인터뷰 - 비트 연산

비트 조작

부울 연산자

• AND, OR, NOT은 기본 부울 연산자로, 연산들을 서로 결합하거 조합해 다른 보조 연산을 만들어 낼 수 있다. 대표적으로 XOR이 보조 연산에 해당한다.
• XOR은 단순한 보조 연산을 넘어 디지털 논리 게이트에서 매우 중요한 위치를 차지한다.

비트 연산자

True & False # AND
True | False # OR
True ^ False # XOR
~True

• 비트 연산자 ~는 부울 변수에 적용하면 True는 1로 간주되어 -2가 된다.

2의 보수

• 2의 보수는 컴퓨터가 음수를 저장하기 위해 일반적으로 취하는 여러 방법 중 하나이다.
• 4비트로 숫자를 표현할 때, 양수만 저장한다면 0부터 15까지 0000~1111로 저장하면 되지만 음수도 저장하기 위해선 비트의 절반을 쪼개서 음수 몫으로 할당하고 맨 앞 비트를 부호 비트로 사용한다(MSB). 즉, 양수의 경우 0xxx를 사용하고 음수의 경우 1xxx를 사용한다.
• 4비트로 2의 보수를 표현하기 위해선 비트마스크 MASK를 이용한다. 비트마스크는 자릿수 만큼의 최댓값을 표현한 값이다.

MASK = 0xF
bin(-1 & MASK)
# >>> '0b1111'

• 파이썬은 내부적으로 부호를 별도 필드로 갖고 있으며 비트 연산이 필요할 때만 2의 보수로 변환하는 작업을 한다.

5 & -4
# >>> 4

bin(0b0101 & 0b1100)
# >>> 0b100

2의 보수 수학연산

• 2의 보수 수학 연산은 가산 역 연산이라 부를 수 있다. 양수를 음수로, 음수를 양수로 바꾸는 작업을 말한다. 비트 연산자 NOT을 이용한 후 1을 더하면 된다. 즉 0111의 2의 보수 연산은 1000 + 1 = 1001이 된다.

bin(0b0101 ^ ~0b1100)
# >>> '-0b1010'

• 이 값이 0b0110이 아닌 이유는 입력값이 4비트 포맷이 아니기 때문에 오버플로가 발생했기 때문이다. 4비트 포맷에선 0b1100은 -4를 뜻하는데 양수 12를 가정했기 때문에 문제가 발생했다.

bin(0b00000101 ^ 0b11110011)
# >>> '0b11110110'

• 8비트 포맷으로 바꿔서 적용하면 XOR 값이 정확히 출력된다. 이 값은 -10이다. 앞서 결과였던 -0b1010도 -10이므로 동일하다.

싱글 넘버

• 딱 하나를 제외하고 모든 엘리먼트는 2개씩 있다. 1개인 엘리먼트를 찾아라.

예제

• 입력: [2, 2, 1]
• 출력: 1

풀이 1. XOR 풀이

• 단 1개의 엘리먼트를 찾는 데 적당한 연산자는 XOR이다. XOR은 입력값이 서로 다르면 True, 같으면 False가 되는 논리 게이트 연산자다. 이를 10진수에 적용하면 다음과 같은 결과를 확인할 수 있다.

0 ^ 0
# >>> 0
4 ^ 0
# >>> 4
4 ^ 4
# >>> 0

• XOR은 두번 등장한 엘리먼트는 0으로 초기화되고 한 번만 등장하는 엘리먼트는 그 값을 온전히 보존한다. 즉 배열의 모든 값을 XOR하면 단 한 번만 등장하는 엘리먼트만 그 값이 남게 된다.

def solution(nums):
    result = 0
    for num in nums:
        result ^= num

    return result

해밍 거리

• 두 정수를 입력받아 몇 비트가 다른지 계산하라.

예제

• 입력: x = 1, y = 4

• 출력: 2

• 설명

  • 1 (0 0 0 1)
  • 4 (0 1 0 0)
  • 2번째 비트와 4번째 비트가 다르므로 정답은 2이다.

풀이 1. XOR 풀이

• 해밍 거리는 두 정수 또는 두 문자열의 차이를 말한다. 예를 들어 'Karolin'과 'Kathrin'의 차이는 3이다. 문자열의 경우 해밍 거리는 다른 자리의 문자 개수가 되며, 이진수의 경우 다른 위치의 비트 개수가 된다.
• XOR 연산을 이용하면 비트가 서로 다른 자리는 1이 되므로 1의 전체 개수를 리턴하면 된다.

def solution(x, y):
    return bin(x ^ y).count('1')

두 정수의 합

• 두 정수 a와 b의 합을 구하라. + 또는 - 연산자는 사용할 수 없다.

예제

• 입력: a = 1, b = 2
• 출력: 3

풀이 1. 전가산기 구현

• 두 정수의 합을 구하는 데 덧셈이나 뺄셈을 사용할 수 없기 때문에 비트 연산만으로 풀이해야 하는 문제다.
• 먼저 정수를 bin으로 2진수로 변환한 뒤 '0b'는 필요없기 때문에 [2:] 슬라이싱을 통해 앞 두자리를 제거해준다. 그 후 .zfill(32)를 이용해 32비트 자릿수를 맞춰준다.
• 이렇게 처리한 값을 뒷부분 부터 하나씩 전가산기를 통과하면서 결과를 채워나가면 된다.

def sum(a, b):
    MASK = 0xFFFFFFFF
    INT_MAX = 0x7FFFFFFF # 양의 정수 최댓값

    a_bin = bin(a & MASK)[2:].zfill(32)
    b_bin = bin(b & MASK)[2:].zfill(32)

    result = []
    carry = 0
    sum = 0
    for i in range(32):
        A = int(a_bin[31 - i])
        B = int(b_bin[31 - i])

        # 전가산기 구현
        Q1 = A & B
        Q2 = A ^ B
        Q3 = Q2 & carry
        sum = carry ^ Q2
        carry = Q1 | Q3

        result.append(str(sum))
    if carry == 1:
        result.append('1')

    # 초과 자릿수 처리
    result = int(''.join(result[::-1]), 2) & MASK
    # 음수 처리
    if result > INT_MASK:
        result = ~(result ^ MASK)

    return result

UTF-8 검증

• 입력값이 UTF-8 문자열이 맞는지 검증하라.

예제

• data = [197, 130, 1] 이 값은 11000101 10000010 00000001로 표현되며 2바이트 문자 다음에 오는 1바이트 문자로 모두 2개며 정상이다.

풀이 1. 첫 바이트를 기준으로 한 판별

바이트 수	바이트 1	바이트 2	바이트 3	바이트 4
1	0xxxxxxx
2	110xxxxx	10xxxxxx
3	1110xxxx	10xxxxxx	10xxxxxx
4	11110xxx	10xxxxxx	10xxxxxx	10xxxxxx

• 이 표를 기준으로 첫 바이트가 1110으로 시작한다면 3바이트 문자이므로, 첫 바이트를 제외하고 뒤따르는 2바이트는 모두 10으로 시작해야 유효한 UTF-8 문자가 된다.

def solution(data):
    # 문자 바이트만큼 10으로 시작 판별
    def check(size):
        for i in range(start + 1, start + size + 1):
            if i >= len(data) or (data[i] >> 6) != 0b10:
                return False
        return True

    start = 0
    while start < len(data):
        # 첫 바이트 기준 총 문자 바이트 판별
        first = data[start]
        if (first >> 3) == 0b11110 and check(3):
            start += 4
        elif (first >> 4) == 0b1110 and check(2):
            start += 3
        elif (first >> 5) == 0b110 and check(1):
            start += 2
        elif (first >> 7) == 0:
            start += 1
        else:
            return False
    return True

1비트의 개수

• 부호 없는 정수형을 입력받아 1비트의 개수를 출력하라

예제

• 입력: 11111111111111111111111111111101
• 출력: 31

풀이 1. 1의 개수 계산

• 다음과 같이 이진수에서 1의 개수를 헤아리는 정도로 매우 쉽게 풀이할 수 있다.

def solution(n):
    return bin(n).count('1')

풀이 2. 비트 연산

• 파이썬의 문자열 기능을 사용하지 않고 비트 연산만으로 1비트의 개수를 헤아린다.
• 비트는 1을 뺀 값과 and 연산을 할 때마다 비트가 1씩 빠지게 된다. 그렇다면 0이 될 때 까지 이 작업을 반복하면 전체 비트에서 1의 개수가 몇개인지 할 수 있다.

def solution(n):
    count = 0
    while n:
        # 1을 뺀 값과 AND 연산 횟수 측정
        n &= n - 1
        count += 1
    return count