📚 2의 보수 - 컴퓨터가 음수를 저장하기 위한 방법
🔎 컴퓨터에서 양수, 음수 표현 방법
4bit에서 컴퓨처가 양수와 음수를 저장하기 위해 맨 앞 비트를 부호 비트로 사용하여 다음과 같이 양수와 음수를 표현한다고 가정하자.
10진수 5를 4bit 이진수로 표현 => 0101
10진수 -5를 4bit 이진수로 표현 => 1101
5 + (-5) = 0,
두 수의 합은 10000(bit칸을 넘어가면 0000이 되어 값은 0) 또는 0000이 되어야 함. 하지만 0101 + 1101 = 10010이 됨 = >따라서 다음과 같이 표현하면 X
10진수 5는 그대로 0101로 표현한다고 하면, 더해서 0이 되는 값은 1011 !
따라서 10진수 -5는 1011로 표현됨.
그럼 10진수 -5는 1011로 표현하는 방법을 논리화 하면,
=> 0101(=10진수 5)에서 1을 0으로 0을 1로 바꿔줌(보수) + 1 = 1010 + 0001 = 1011
=> -x = x의 보수 + 1
🔎 파이썬은 내부적으로 2의 보수를 어떻게 표현할까?
파이썬은 임의 정밀도를 지원하기 때문에 부호는 별도 필드로 갖고 있으며, 비트 연산이 필요할 때만 2의 보수로 변환하는 작업을 함.
print(bin(5)) #0b1출력
print(bin(-5)) #-0b1출력
print(bin(5-5)) #0b0출력🔎 파이썬에서 2의 보수 출력하기
#0b는 2진수, 0x는 16진수 표현 / 15(십진수) = 1111(이진수) = F(16진수) / 0xF = 4bit 2진수로 표현하면 1111
#파이썬은 비트 연산할때 2의 보수로 변환하므로 비트 마스크 0b1111을 만들어 &연산한다
#(0b1111와 &연산하면 그대로 출력되니까!)
MASK = 0xF
print(bin(5 & MASK)) #0b101
print(bin(-5 & MASK)) #0b1011📌 70) 싱글 넘버 ( 리트코드 136. Single Number )
✔ 풀이 (XOR풀이)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
#XOR연산 입력값이 여러 개일 때, 1이 홀수 개면 1 짝수개면(0개 포함) 0 으로 결과가 나옴
#따라서 2번씩 나오는 숫자들의 자릿수 비트는 0이 되고 1번만 나오는 숫자의 자릿수 비트는 1이 됨
result ^= num
return result📌 71) 해밍 거리 ( 리트코드 461. Hamming Distance )
✔ 풀이 (XOR풀이)
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
#x^y는 10진수로 반환 -> bin(10진수)는 10진수를 2진수로 표현한 문자열 반환
#XOR은 두 비트가 다를 때 1
return bin(x^y).count('1')📌 72) 두 정수의 합 ( 리트코드 371. Sum of Two Integers )
✔ 풀이1 (전가산기 구현)
class Solution:
def getSum(self, a: int, b: int) -> int:
MASK = 0xFFFFFFFF #16진수 비트 마스크
INT_MAX = 0x7FFFFFFF #양수 중 제일 큰 수
#십진수 a, b를 2진수 문자열로 표현 & 앞의 0b를 제거하고 32bit를 만들어 주는 전처리과정
a_bin = bin(a & MASK)[2:].zfill(32)
b_bin = bin(b & MASK)[2:].zfill(32)
result = []
carry, sum_bit = 0, 0
for i in range(32): #맨 마지막 비트부터 계산 -> 총 32bit 이므로 32번 반복
A, B = int(a_bin[31 - i]), int(b_bin[31 - i])
Q1 = A ^ B
sum_bit = carry ^ Q1
result.append(str(sum_bit))
Q2 = A & B
Q3 = Q1 & carry
carry = Q2 | Q3
result = int(''.join(result[::-1]), 2) #이진수 문자열을 숫자로 변환
if result > INT_MAX: #음수일경우
#result ^ MASK는 result의 0을 1로, 1을 0으로 바꿔줌
#그 값을 Not연산 => ~x(십진수) = -x(십진수) -1
result = ~(result ^ MASK)
return result✔ 풀이2 (간소한 구현)
class Solution:
def getSum(self, a: int, b: int) -> int:
MASK = 0xFFFFFFFF #32bit 비트 마스크
INT_MAX = 0x7FFFFFFF #양수 최대값
while b:
a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
if a > INT_MAX:
a = ~(a ^ MASK)
return a📌 73) UTF-8 검증 ( 리트코드 393. UTF-8 Validation )
✔ 풀이 (첫 바이트를 기준으로 한 판별)
class Solution:
def validUtf8(self, data: List[int]) -> bool:
def check(size): #size=확인 할 바이트 개수
for i in range(start + 1, start + size + 1):
if i >= len(data) or (data[i] >> 6) != 0b10: #앞 비트 2개가 10이어야 함
return False
return True
start = 0 #data의 0인덱스가 시작점
while start < len(data):
first = data[start]
if (first >> 3) == 0b11110 and check(3): #4바이트로 표현
start += 4
elif (first >> 4) == 0b1110 and check(2): #3바이트로 표현
start += 3
elif (first >> 5) == 0b110 and check(1): #2바이트로 표현
start += 2
elif (first >> 7) == 0b0: #1바이트로 표현
start += 1
else:
return False
return True📌 74) 1비트의 개수 ( 리트코드 191. Number of 1 Bits)
✔ 풀이1 (1의 개수 계산)
class Solution:
def hammingWeight(self, n: int) -> int:
#bin()은 ()의 수를 이진수로 표현한 문자열을 반환
return bin(n).count('1')✔ 풀이2 (비트 연산)
class Solution:
def hammingWeight(self, n: int) -> int:
#이진수에서 1을 뺀 값과 and연산 하면 비트가 1씩 빠지게 됨
cnt = 0
while n: #1트씩 빠지다가 결국엔 0이 됨
n &= n - 1
cnt += 1
return cnt🔮 XOR을 이용한 변수 스왑
x, y = 4, 9 #0100, 1001
x = x^y #1101 #두 개의 입력이 다를 경우 = 1
y = x^y #0100
x = x^y #1001조금 더 쉽게
x, y = 4, 9
x, y = (x^y)^x, (x^y)^y
print(x, y) #9, 4