[백준] 24389. 2의 보수 - Python3

문제 설명

10진수 정수 N이 주어질 때, N의 2의 보수와 N의 서로 다른 비트 수를 출력하는 문제

https://www.acmicpc.net/problem/24389

24389번: 2의 보수

• 알고리즘 분류 - 수학, 비트마스킹
• 난이도 - 브론즈1

---

관련 개념

비트마스킹

데이터를 순수 비트로 저장하는 것.

주로 배열의 아이템 존재 여부를 나타낼 때 쓰이지만, 여기서는 본래의 의미로 단순히 비트 연산을 할 때 비트가 쓰이는 것을 말하는 듯 하다.

---

접근 방법

1. 문자열

1) N 이진수 변환

bin 함수를 이용해 N의 이진수를 문자열 형태로 저장했다.

 

2) N의 보수 구하기

우선 1의 보수를 취해주기 위해 0은 1로, 1은 0으로 서로 바꾼 후, 그 문자열을 10진수 정수로 변환하여 1을 더해 2의 보수를 취하고, 그걸 bin 함수로 다시 문자열 형태의 이진수로 변환하여 저장했다.

 

3) 1)에서 구한 이진수 문자열과 2)에서 구한 문자열을 글자 하나하나 비교했다.

 

2. 비트마스킹

1) 2의 보수 구하기

32개의 1과 N을 XOR 연산(^)하여 1의 보수를 취해준 후, 1을 더해 2의 보수를 구했다.

2) 비교하기

N과 1)에서 구한 2의 보수를 XOR 연산하고, 연산 결과의 1(=두 비트가 다름)의 개수를 세어 출력했다.

---

답안 코드

1. 문자열

메모리: 31388 KB , 시간: 40 ms, 코드 길이: 241 B

n = int(input())
bin_n = bin(n)[2:].zfill(32)

com_1 = ''
for i in range(32):
  com_1 += '1' if bin_n[i] == '0' else '0'
com_2 = bin(int(com_1,2)+1)[2:]

answer = 0
for i in range(32):
  if com_2[i] != bin_n[i]:
    answer += 1
print(answer)

 

2. 비트마스킹

메모리: 31256 KB , 시간: 44 ms, 코드 길이: 67 B

 

n = int(input())
com = (n^((1<<32)-1))+1
print((n^com).bit_count())

? 비트연산이 미세하게 더 오래 걸리네...ㅋㅋ