비트 조작, 해밍 거리 (Python Algorithm Interview 19장)

algorithm

파이썬 알고리즘 인터뷰 19장을 정리한 내용입니다.

Hamming Distance

  • 해밍거리는 같은 길이를 가진 두 개의 문자열에서 같은 위치에 있지만 서로 다른 문자의 개수이다
  • 컴퓨터 통신에서 문자열 전송 시 에러 검출에 사용되는 방법 중 하나이다

비트 조작

부울 연산자

pic1.png

  • 기본적인 부울 연산으로 AND , OR , NOT 이 있다

#71 해밍 거리

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

입력

1
2
x = 1
y = 4
  • 해밍 거리는 두 정수 또는 두 문자열의 차이를 말하며 자연어 처리에서도 많이 사용된다
  • "karolin"과 "kathrin"의 차이는 3이고 1011101 과 1001001 의 차이는 2다
  • 문자열의 경우 해밍 거리는 다른 자리의 문자 개수가 되며, 이진수의 경우 다른 위치의 비트 개수가 된다
1
2
def H_distance(x: int, y: int) -> int:
    return bin(x ^ y).count('1')
  • XOR 연산을 이용해 풀이가 가능하다
  • 이진수로 변경한 후 XOR 연산을 하면 다른 위치는 1이 될 것이다
  • 1의 개수를 리턴하면 된다

#72 두 정수의 합

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

입력

1
2
a = 1
b = 2

전가산기 구현

:——–:|:———-:
스크린샷, 2021-08-17 15-46-33.png | 스크린샷, 2021-08-17 15-47-54.png

  • 왼쪽 그림은 전가산기의 회로도의 진리표이다
  • Q1 , Q2, Q3 에 회로도의 중간값을 계산한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def sumOfTwoNum(a: int, b: int) -> int:
    # + - 연산자는 사용할 수 없다
    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_MAX:
        result = ~(result ^ MASK)

    return result

  • 논리 회로도에 따라 전가산기를 구현해 준다

  • 정수를 이진수로 변경하기 위한 전처리가 필요하다

    1. bin() 함수를 이용해 정수를 이진수로 바꿔준다
    2. 이진수로 변환하면 0b 식별자가 붙기 때문에 슬라이싱으로 분리해준다
    3. a & MASK 에서 MASK는 비트 마스크로, 음수 처리를 위해 2의 보수로 만들어주는 역할을 한다. 여기서는 입력값을 32비트 정수로 가정했으므로 MASK는 0xFFFFFFFF 로 하였으며, 이 값과 AND 연산을 하면 2의 보수 값을 얻을 수 있다
    1
    2
    3
    4
    5
    >>> bin(1 & MASK)
    '0b1'

    >>>bin(-1 & MASK)
    'Øb11111111111111111111111111111111'
    • 양수는 마스킹해도 동일하지만 계산하기 쉽게 하기위해 앞의 자리수를 zfill(32) 를 사용하여 0을 채워준다

  • 낮은 자릿수부터 하나씩 전가산기를 통과하면서 결과를 채워나간다

  • 32비트로 가정하였기 때문에 32번 반복한다

  • 마지막 반복이 끝난 후 carry 값이 남아있으면 자릿수가 하나 올라간 것이기 때문에 1을 추가해준다

  • 만약 1을 추가해줘 33비트가 되어도 마스킹 작업을 해줘 32비트를 맞춰줄 수 있다

  • result 는 낮은 자릿수부터 채웠기 때문에, 뒤집어 준 후 십진수로 바꿔준다

  • 양의 정수 최댓값은 0x7FFFFFFF 이므로, 만약 32번째 비트가 1이면 이 값보다 큰 값이 되며 다시 마스킹 값과 XOR 한 후 NOT 연산을 해서 음수로 만들어 준다

간소한 구현

1
2
3
4
5
6
7
8
9
10
11
12
def simple(a: int, b: int) -> int:
    MASK = 0xFFFFFFFF
    INT_MAX = 0x7FFFFFFF

    # 합, 자릿수 처리
    while b != 0:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK

    # 음수 처리
    if a > INT_MAX:
        a = ~(a ^ MASK)
    return a
  • 앞서 풀이한 코드에서 2의 보수를 만들기 위한 MASK 를 사용하였다
  • a 는 carry 값을 고려하지 않는 a 와 b 의 합이 담기게 하고 b 는 자릿수를 올려가면서 carry 값이 담기게 한다
  • 마지막에는 음수처리를 해준다
  • 전가산기를 구현한 코드보다 간소하지만 실행시간은 차이가 나지 않는다

#73 UTF-8 검증

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

입력

1
data = [197, 130, 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def UTP(data: list) -> bool:
    # 문자 바이트 만큼 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

스크린샷, 2021-08-19 02-03-30.png

  • 표는 UTF-8 바이트 순서의 이진 포맷이다
  • 첫 바이트가 1110 으로 시작한다면 3바이트 문자이며 첫 바이트를 제외하고 다음에 오는 2바이트는 모두 10 으로 시작해야 한다
  • first 첫 바이트를 가리키며 첫 바이트가 0으로 시작한다면 1바이트 문자이고 110 으로 시작하면 2바이트 문자가 된다
  • check 함수는 파라미터로 size 를 받아 해당 사이즈만큼 바이트가 10으로 시작하는지 판별한다
  • 조건에 맞지 않으면 FALSE 를 리턴한다