비트 조작
Question 70: 싱글 넘버
딱 하나를 제외하고 모든 엘리먼트는 2개씩 있다. 1개인 앨리먼트를 찾아라.
입력: [2,2,1]
출력: 1
내 풀이
class Solution:
def singleNumber(self, nums: List[int]) -> int:
number_dict = collections.Counter(nums)
for i in number_dict:
if number_dict[i] == 1:
return i
결과
Runtime: 309 ms, faster than 14.67% of Python3 online submissions for Single Number. Memory Usage: 17.3 MB, less than 5.65% of Python3 online submissions for Single Number.
풀이 1: XOR 풀이
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
print(f'result: {result}, num:{num}')
result ^= num
print(result)
return result
중요 내용
- ^은 이진수를 기준으로 XOR 연산을 수행한다.
- 배열의 모든 값을 XOR 하면, 두번 등장한 엘리먼트는 0으로 초기화되고 한번만 등장한 엘리먼트는 그 값을 온전히 보존한다.
Question 71: 해밍 거리
두 정수를 입력받아 몇 비트가 다른지 계산하라.
입력: x = 1, y = 4
출력: 2
내 풀이
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
one_count = bin(x^y)
print(one_count)
result = 0
for i in one_count:
if i == '1':
result += 1
return result
결과
Runtime: 65 ms, faster than 6.71% of Python3 online submissions for Hamming Distance. Memory Usage: 13.8 MB, less than 97.40% of Python3 online submissions for Hamming Distance.
풀이 1: XOR 풀이
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x^y).count('1')
중요 내용
- count() 함수를 사용하여 내가 풀이한 방법보다 훨씬 더 간단하게 풀이하였다.
- bin은 십진수로 된 정수를 입력받아 이진수로 된 문자열을 리턴한다.
Question 72: 두 정수의 합
두 정수 a와 b의 합을 구하라. + 또는 - 연산자는 사용할 수 없다.
입력: a = 1, b= 3
출력: 4
풀이 1: 전가산기 구현
class Solution:
def getSum(self, 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
중요 내용
- 전가산기는 하위의 자리올림수 출력을 상위의 자리올림수 입력에 연결함으로써 임의의 자리수의 이진수 덧셈이 가능하다.
- 반복문이 끝난 후에 아직 carry 값이 남아있으면 자리수가 하나 더 올라간 것이므로 1을 추가한다. 마지막 마스킹 작업을 통해 최대로 정한 비트값을 초과할 경우 초과한 값을 날려버린다.
풀이 2: 좀 더 간소한 구현
class Solution:
def getSum(self, 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
중요 내용
- ^은 다르면 1, 같으면 0인 결과값을 낸다. 따라서 이진수끼리 더하는 것과 비슷한 결과를 나타내나 자리수 올림에 대한 것은 반영하지 못한다. 따라서 ((a & b) « 1)를 통하여 자리수 올림에 대한 것을 반영한다.
Question 73: UTF-8 검증(재풀이)
입력값이 UTF-8 문자열이 맞는지 검증하라.
입력: data = [235,140,4]
출력: False
설명: data의 정수는 다음과 같이 나타낼 수 있다: [11101011 10001100 00000100] 첫번째와 두번째 이진수는 1110, 10으로 시작하므로 유효한 UTF-8 문자열이다. 그러나 세번째 이진수는 10으로 시작하지 않으므로 유효하지 않은 UTF-8 문자열이다.
풀이 1: 첫 바이트를 기준으로 한 판별
class Solution:
def validUtf8(self, data: List[int]) -> bool:
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
중요 내용
- while 문으로 처음 나오는 바이트가 유효한지 판별한다.
- check 함수는 처음 나오는 바이트를 제외한 나머지 바이트가 유효한지 판별한다.
Question 74: 1비트의 개수
부호없는 정수형을 입력받아 1비트의 개수를 출력하라.
입력: n = 00000000000000000000000000001011
출력: 3
내 풀이
class Solution:
def hammingWeight(self, n: int) -> int:
return bin(n).count('1')
- bin()으로 이진수로 바꿔준 후에 나타나는 1의 갯수를 count() 함수를 사용하여 구했다.
결과
Runtime: 32 ms, faster than 89.24% of Python3 online submissions for Number of 1 Bits. Memory Usage: 13.9 MB, less than 53.59% of Python3 online submissions for Number of 1 Bits.
풀이 1: 1의 개수 계산
내 풀이 방법과 동일하므로 생략한다.
풀이 2: 비트 연산
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
n &= n-1
count += 1
return count
중요 내용
- 이진수에서 1을 뺀 값과 AND 연산을 하면 작은 비트 순서대로 1 비트씩 빠지게 된다.
- 위 방법을 이용하여 전체 비트에서 1의 개수가 몇 개인지 알 수 있다.
Comments