알고리즘 '비트 조작' 파트의 코딩 문제를 풀기 위해
꼭 이해해야할 개념인 '부울 연산자', '비트 연산자', '2의 보수'에 관해 알아보고자 한다.
<목차>
1. 부울 연산자(Boolean Operator)
2. 비트 연산자 (Bitwise Operator)
3. 보수(Complement)
4. 2의 보수 구하기
5. 2의 보수를 이용한 수학 연산
1. 부울 연산자(Boolean Operator)
1.1 개념
부울(Bool)은 참(True), 거짓(False)를 나타내는 자료형으로,
부울 연산자는 특정 수들의 논리 연산에 사용되는 기호이다.
NOT, AND, OR의 개념은 친숙하지만,
XOR은 생소할 수 있겠다.
'Exclusive OR'이라고 읽으며,
값이 서로 다를 때(T-F or F-T)만 참(True)이되는 연산자다.
1.2 예시코드
2. 비트 연산자(Bitwise Operator)
2.1 기호
부울 연산자를 비트 연산자로 표현할 수 있다.
2.2 예시 코드
위 사례에서 주목할 부분은 비트 연산자 NOT(~, 틸트)이다.
틸트를 부울 변수 False(=0)에 적용할 때 -1이 출력된다.
연산자 NOT은 2의 보수에서 1을 뺀 값과 같기 때문이다.
그러면 2의 보수는 무엇일까?
3. 보수(Complement)
3.1 개념
2의 보수에 앞서, 보수의 기본 개념에 대해서 살펴보자.
보수는 컴퓨터가 음수를 계산하기 위해 취하는 방법의 일종이다.
컴퓨터는 가산기를 이용하여 덧셈, 뺄셈, 곱셈, 나눗셈을 계산한다.
즉, 덧셈만 이용하여 뺄셈, 곱셈, 나눗셈을 계산해야하는 것이다.
곱셈은 덧셈을, 나눗셈은 뺄셈을 반복하면 된다.
그럼 덧셈을 이용하여 뺄셈은 어떻게 계산할까?
이때 등장하는 개념이 '보수'다.
3.2 예시
컴퓨터가 '6 - 2 = 4' 를 계산해야 한다고 하자.
하지만 컴퓨터는 '-2'를 직접 계산할 수 없기 때문에,
덧셈을 이용해서 뺄셈(-2)을 연산해야 한다.
'-2'의 (10의)보수는 '-2'에서 '+10'만큼 이동한 '+8'이다.
'6'과 '-4'의 보수인 '+8'을 더한 값(6 + 8)은 '14'다.
'14'에서 십의 자리수 '1'을 제외하고 '4'만 출력한다.
그럼 본래 (6-2 의)답 '4'와 동일한 결과를 얻을 수 있다.
4. 2의 보수 구하기
4.2.1 사례
십진수 -14의 보수를 구하려고 한다.
십진수를 이진수로 바꾸면 -1110이 된다.
-1000을 반전시키면 1의 보수(+0001)을 구할 수 있다.
(편의상 반전이라 칭했으나, 실제로는 마스크 값(1111)와 XOR 연산한 값이다.)
1의 보수에 1을 더하면 2의 보수를 구할 수 있다.
5. 2의 보수를 이용한 연산
5.2.1 사례
컴퓨터가 '14 - 10 = 4'을 계산한다고 하자.
거듭 말했듯이 컴퓨터는 음수(-10)을 직접 계산할 수 없기에, 보수를 활용한다.
우선 '14 - 10 = 4'을 이진수로 나타내면, '1110 - 1010 = 0100'이 된다.
'-1010'의 2의 보수를 나타내기 위해,
우선 반전을 통해 1의 보수(+0101)을 구한 다음,
1을 더해주면 2의 보수(+0110)를 구할 수 있다.
-10의 2의 보수를 구한 후, 본래 식을 계산하면 '10100'이 나온다.
맨 앞에 1(자릿수 올림을 통해 새로 생겨난 값으로 '캐리'라고 한다)을 버리면 '0100'으로,
2의 보수를 구하기 전의 결과 값과 동일하다.
* 본 포스팅은 도서 '파이썬 알고리즘 인터뷰' 및 유튜브 '대멀쌤의 자료를 참고했습니다.(https://www.youtube.com/c/%EB%8C%80%EB%A9%80%EC%8C%A4)
'자료구조 & 알고리즘' 카테고리의 다른 글
| 분할 정복 예제 - 과반수 엘리먼트(리트코드 169) (0) | 2022.07.03 |
|---|---|
| 다이나믹 프로그래밍(Feat. 피보나치 수열) (0) | 2022.07.01 |
| [파이썬] 초기화 함수 / __init__() 메서드는 왜 쓰는 걸까? (0) | 2022.05.16 |
| 트리 순회 - 전위(Pre-Order), 중위(In-order), 후위(post-Order) 순회 (0) | 2022.04.28 |
| 비전공자 코딩 테스트 공부법 - 파이썬 알고리즘 인터뷰 (0) | 2022.04.14 |