[파이썬 알고리즘 인터뷰] 비트 조작

• 부울 연산자: NOT, AND, OR (기본), XOR (보조)
  
  • 기본 연산자를 조합해 보조 연산 가능
  • XOR: TT, FF 일때는 F 반환, TF, FT 일때는 T 반환

# XOR
x = y = True
(x and not y) or (not x and y)
>>> False

 

• 비트 연산자
  • ~ : (2의 보수) - 1, 십진수로는 -x-1, 부울 변수 True에 적용하면 -1-1 = -2

True & False # Bitwise AND
>>> False
True | False # Bitwise OR
>>> True
True ^ True # Bitwise XOR
>>> False
~ True # Bitwise NOT
>>> -2

# 십진수와 마찬가지로 연산
bin(0b0110 + 0b0010)
>>> '0b1000'
bin(0b0011 * 0b0101)
>>> '0b1111'
# 시프팅
bin(0b1101 >> 2)
>>> '0b11'
bin(0b1101 << 2)
>>> '0b110100'
# 밑에서 설명
bin(0b0101 ^ ~0b1100)
>>> '-0b1010' # 0b0110

• 우리가 예상한 0b0110이 나오려면 ~0b1100이 0b0011이 되어야 하는데, 컴퓨터는 그렇게 계산하지 않음
  • 자릿수 만큼의 최댓값을 지닌 MASK를 만들고 그 값과 XOR 연산해야 예상대로 진행됨
  • 0b1100 ^ 0b1111 하면 0b0011

# 자릿수 제한 비트 연산
MASK = 0b1111
bin(0b0101 ^ (0b1100 ^ MASK))
>>> '0b110'

 

• 파이썬의 진법 표현

# 이진수(binary) ↔ 십진수 (decimal)
bin(87) # '0b1010111'
int('0b1010111', 2) # 87
int('1010111', 2) # 87

a = 87

b = 0b1010111
b # 87

# 16진수 (hexadecimal) ↔ 십진수
hex(87) # '0x57'

c = 0x57
c # 87

# id(a) = id(b) = id(c)

• 16진수로 10 ~ 15는 A ~ F로 표현

 

• 2의 보수: 컴퓨터가 음수를 저장하기 위해 일반적으로 취하는 여러 방법 중 하나
  • 4비트로 숫자 표현 가정: 16개 숫자 표현 가능
  • 양수만 표현한다면 0000 ~ 1111 (0 ~ 15)
  • 음수도 저장한다면 맨 앞 비트는 부호비트 -> 양수는 0xxx, 음수는 1xxx
    • n비트일 때 표현 범위는 -2^(n-1) ~ 2^(n-1) - 1

0	1	2	3	4	5	6	7
0000	0001	0010	0011	0100	0101	0110	0111

-1	-2	-3	-4	-5	-6	-7	-8
1000	1001	1010	1011	1100	1101	1110	1111

# 십진수 x를 4비트 2의 보수로 표현
# 2^4 = 16^1이므로 F한개
MASK = 0xF
bin(x & MASK)

• 파이썬은 내부적으로 비트 연산이 필요할 때만 2의 보수로 변환하는 작업 수행, 실제 2의 보수 값 보여주진 않음
• 숫자를 4비트로 표현하든 32비트로 표현하든 비트 연산 결과 동일
  • 십진수 -> n비트 2의 보수 -> 비트 연산 -> 십진수

 

• 비트 연산자 NOT (~): 십진수를 2의 보수로 표현 후 1 뺀 것
• 기준 비트 내에서 정확히 1을 0으로, 0을 1로 바꿔줌 (2의 보수 포맷)
• ~ x = -x - 1 (십진수 포맷)

 

• 2의 보수 수학 연산: 십진수를 2의 보수로 표현 후 ~ 연산하고 1 더한 것
• 양수를 음수로, 음수를 양수로 바꾸는 연산 (십진수 포맷)
• ex) 7 -> 0111 -> 1000(=~0111) -> 1001
  • 0111 + 1001 = 10000 -> 0000 (4비트 연산이므로 초과한 자릿수 무시)

136. Single Number

- 배열의 모든 값 XOR -> 0 ^ x(십진수) = x, 교환/결합법칙 성립

• a ^= b ↔ a = a ^ b

461. Hamming Distance

- XOR 연산 후 이진수 포맷에서 1 개수

 

371. Sum of Two Integers

- 전가산기 구현

* 마스킹은 십진수끼리

• zfill(), rjust()

393. UTF-8 Validation

- 첫 바이트로 이후 바이트 형태 판별하는 과정 반복

 

191. Number of 1 Bits

- count()

- n &= n - 1 -> n 과 n - 1 을 AND 연산하면 1비트씩 빠진다

 

• XOR을 이용한 변수 스왑

x, y = 9, 4
x = x ^ y
y = x ^ y
x = x ^ y
x, y
>>> (4, 9)