정수란
수학에서 정수는 양의 정수, 음의 정수 및 0으로 이루어진 수의 체계이다. 또는 자연수, 자연수의 음수 및 영을 통칭하는 말이다.
컴퓨터에서 정수를 표현하는 방법
컴퓨터는 정수를 2진법으로 표현한다. n 개의 비트(bit)로 2^n 개의 정수를 표현할 수 있다.
컴퓨터에서 정수를 표현하는 방법은 부호없는 정수(Unsigned Integer), 부호있는 정수(Signed Integer) 2가지로 나뉜다.
부호없는 정수는 0 또는 양의 정수를 표현한다.
부호없는 정수는 0, 양의정수 또는 음의정수를 표현한다.
그런데 비트에는 +, - 와 같은 기호가 없고 0, 1만 있을 뿐이다. 비트로 어떻게 음수를 나타낼 수 있을까?
부호있는 정수
부호있는 정수가 음수를 표현하는 방법은 3가지로 부호 절대값, 1의 보수, 2의 보수가 있다.
부호 절대값
최상위 비트인 MSB (Most Significant Bit) 를 기준으로 양수와 음수를 구분한다. 최상위 비트는 비트에서 가장 왼쪽에 있는 숫자다. 예를 들어 8비트 2진수 10000000이 있다면 1이 최상위 비트다.
최상위 비트가 0이면 0 또는 양의 정수, 최상위 비트가 1이면 음의 정수를 나타낸다. 최상위 비트만 보고 양수인지 음수인지 바로 알 수 있다.
최상위 비트는 부호로 사용하고, 나머지 비트로 숫자를 나타낸다.
00000011(2) -> +3
10000011(2) -> -3
0이 2개
00000000(2) -> +0
10000000(2) -> -0부호 절대값 방식은 0이 양수, 음수 2개가 존재해서 비트로 표현할 수 있는 숫자가 하나 줄어든다.
연산이 복잡하다
부호 비트와 나머지 비트를 나눠서 계산
부호 비트의 계산 방법은 절대값의 계산 방법과 다를 수 있다. 두 수가 모두 음수인 경우 덧셈을 해도 음수이므로 덧셈한 결과의 부호 비트는 1이어야 한다. 예를 들어 -3인 1011(2) 와 -2 인 1010(2) 덧셈은 부호 비트가 0이 아니라 1이 되어야 한다.
1011(2) -> -3
1010(2) -> -2
1011
+ 1010
------
1101
뺄셈 + 두 피연산자간의 절대값 크기를 고려해서 계산
이진수의 뺄셈은 주로 덧셈을 활용하는데 부호 절대값에서는 이게 적용되지 않을 수 있다. 적용되지 않으면 가산기 외에 뺄셈기가 필요하다.
부호 절대값의 연산
1) 두 피연산자가 모두 양수
- 앞의 절대값 > 뒤의 절대값
(+3) - (+2) 를 (+3) + (-2) 로 계산하면
0011(2) -> 3
0010(2) -> 2
0011(2) -> 3
1010(2) -> -2
1이 나와야 하는데 -5가 됐다.
0011
+ 1010
------
1101
위처럼 부호가 다르면 부호비트는 덧셈으로 구할 수 없다. 뺄셈으로 계산하면 원하는 값을 얻을 수 있다. 단, 부호비트는 별도로 처리해야 한다. 부호비트는 1이 아닌 0으로 처리해야 한다.
부호비트 연산을 이해 하는데 이 글이 많은 도움이 됐다. 이 경우 부호비트는 -1이 된다. 1은 음수고 음수에 음수를 나타내는 -를 붙이면 양수가 되므로 양수를 나타내는 0을 대입하면 된다.
0011
- 1010
------
0001
- 앞의 절대값 < 뒤의 절대값
0010(2) -> 2
0011(2) -> 3
그대로 계산하면 안되고 두 숫자의 순서를 바꿔서 계산해야 한다.
그런데 (+2) - (+3) 을 순서를 바꿔서 (-3) + (+2) 계산해도 원하는 값이 나오지 않는다.
1011
+ 0010
------
1101
'앞의 절대값이 뒤의 절대값 보다 작은 경우'도 '앞의 절대값이 뒤의 절대값 보다 큰 경우'처럼 덧셈이 아닌 뺄셈으로 구해야 한다.
부호비트는 1 - 0 에서 -0이 된다. -0은 양수에 음수 기호를 붙인 것이라 음수가 되므로 1로 나타낼 수 있다.
1011
- 0010
------
1001
2) 앞의 피연산자가 음수면서 뒤의 피연산자가 양수
-3 과 2를 뺄셈할 경우 (-3) - (+2) 를 (-3) + (-2) 로 계산하고 부호 비트만 따로 연산하면 덧셈으로 구할 수 있다.
1011(2) -> -3
1010(2) -> -2
1011
+ 1010
------
1101
부호 비트를 따로 연산해야 해서 회로 구성이 복잡해진다.
1의 보수
커다란 2의 제곱수는 어떤 수 보다 1자리수가 많으면서 1로 시작하고 나머지가 0인 수다. 이 커다란 2의 제곱수에서 1을 빼면 어떤 수와 자리수가 같으면서 자리수의 모든 값이 1이다.
101의 커다란 2의 거듭제곱수 - 1은 111이다. 101의 1의 보수는 111에서 101을 빼서 구하는 숫자다. 111에서 101을 빼면 010이 되고 010은 101의 자리수를 모두 반전한 것과 같다.
0이 2개
| 2진수 | 10진수 |
|---|---|
| 0000 | 0 |
| 0001 | 1 |
| 0010 | 2 |
| 0011 | 3 |
| 0100 | 4 |
| 0101 | 5 |
| 0110 | 6 |
| 0111 | 7 |
| 1111 | -0 |
| 1110 | -1 |
| 1101 | -2 |
| 1100 | -3 |
| 1011 | -4 |
| 1010 | -5 |
| 1001 | -6 |
| 1000 | -7 |
1의 보수 표현으로 나타낼 수 있는 4비트 2진수는 위와 같다. 1의 보수도 부호 절대값과 마찬가지로 0이 2개다.
연산시 캐리 처리 필요
1의 보수로 표현한 이진수 연산시 캐리가 발생 여부에 따라 처리 방법이 달라진다. 캐리가 발생한 경우 발생한 캐리 1을 최하위 비트에서 더한다.
2와 -1을 더할 경우 최상위 비트에서 자리올림이 발생한다. 자리올림된 1을 자리올림을 제외한 값과 더하면 (2) + (-1)의 몫인 1을 구할 수 있다.
0010(2) -> 2
1110(2) -> -1
0010
+ 1110
------
1 0000
(최상위 비트에서 1 자리올림 발생)
0000
+ 0001
------
0001
(자리올림된 1을 0000과 더한다)
2의 보수
커다란 2의 제곱수는 어떤 수 보다 1자리수가 많으면서 1로 시작하고 나머지가 0인 수다. 예를 들어 011의 커다란 2의 제곱수는 1000이다.
2의 보수에서 2는 2^n 의 2다. 2의 보수는 2^n 을 만드는 수다.
예를 들어 2진수 011이 있다고 하면 011의 2의 보수는 101 이다. 2진수 011은 길이가 3이다. 길이를 2^n 의 n 에 대입하면 2^3 이고 이는 10진수로 표현하면 8이고 2진수로 표현하면 1000이다. 즉 011의 2의 보수는 1000을 만드는 수다. 011에서 101을 더하면 1000이 된다.
| 2진수 | 10진수 |
|---|---|
| 0000 | 0 |
| 0001 | 1 |
| 0010 | 2 |
| 0011 | 3 |
| 0100 | 4 |
| 0101 | 5 |
| 0110 | 6 |
| 0111 | 7 |
| 1111 | -1 |
| 1110 | -2 |
| 1101 | -3 |
| 1100 | -4 |
| 1011 | -5 |
| 1010 | -6 |
| 1001 | -7 |
| 1000 | -8 |
2의 보수는 1의 보수에서 1을 더한다. 자리수를 모두 반전하고 1을 더하면 2의 보수를 구할 수 있다. 5의 2의 보수는 아래와 같이 구할 수 있다.
0101(2) -> 5
1010(2) -> 비트를 모두 반전
1011(2) -> 1을 더한다 (2의 보수)
0이 1개
부호 절대값, 1의 보수와 달리 2의 보수는 0이 1개다.
캐리는 무시
2의 보수에서 캐리는 무시하면 되는데 오버플로우는 막을 수 없다.
오버플로우는 비트로 표현할 수 있는 수의 범위를 벗어난 경우다. 캐리는 오류가 아니지만 오버플로우는 오류다.
- 캐리 O, 오버플로우 X
0001
+ 1111
------
1 0000
(캐리 발생)1 + (-1)은 0이다.
이진수 연산을 하면 캐리가 발생하는데 캐리를 제외하고 나머지 비트를 보면 0000으로 0이 나왔다. 캐리는 무시한다.
- 캐리 X, 오버플로우 O
0001
+ 0111
------
10001 + 7은 8이다.
4비트에서 2의 보수로 표현할 수 있는 수의 범위는 -8 ~ 7이다. 8은 4비트에서 표현할 수 있는 수의 범위를 벗어났다.
1000은 2의 보수에서 -8이다. 오버플로우가 발생해서 올바른 연산 결과가 나오지 않았다.
- 캐리 X, 오버플로우 X
0001
+ 0011
------
01001 + 3은 4다.
이 경우 캐리와 오버플로우 모두 발생하지 않았다. 정상적인 연산 결과가 나왔다.
- 캐리 O, 오버플로우 O
1110
+ 1001
------
1 0111
(캐리 발생)-2 + (-7) 은 -9다.
이진수 연산시 7이 나온다. 오버플로우가 발생해서 올바른 연산 결과가 나오지 않았다. 캐리도 발생했으나 캐리는 무시한다.
-0b1010
접두어 0b
print(0b1001)
# 9
print(~0b1001)
# -10
# (~ 과 - 의 구분에 주의)파이썬에서는 이진수임을 나타내기 위해 이진수 앞에 0b 접두어를 붙인다.
-0b1010은 접두어 0b 앞에 -가 붙었는데 이는 어떤 의미일까?
1010이 8비트 단위의 이진수였다면 1010은 00001010과 같다.
파이썬에서 정수 크기는 8비트 보다 훨씬 크기(파이썬의 정수 크기는 기본적으로 28바이트고 이보다 더 큰 수도 표현이 가능해서 사실상 무한대라고 볼 수 있다고 한다) 때문에 0b1010는 0b와 1010사이에 아주 많은 0이 생략되어 있다고 할 수 있다.
~(tilde)
파이썬에서 ~(tilde) 는 비트를 반전한다.
10진수 9는 2진수로 0b1001이고 0b와 1001사이에는 아주 많은 0이 생략됐다.
0b1001을 비트 반전하면 0b와 1001사이에 있던 아주 많은 0이 모두 1이 된다. 그대로 나타내려면 화면에 아주 많은 공간이 필요하다.
비트 반전은 2의 보수에서 1을 뺀 값과 같다.
비트 반전은 1의 보수를 구하는 것과 같고, 1의 보수는 2의 보수에서 1을 뺀 값이다. 반대로 2의 보수는 1의 보수에서 1을 더한 값이다. 파이썬은 음수를 나타내기 위해 2의 보수법을 사용한다.
2의 보수법에서 비트 반전
0010(2) -> 2
1101(2) -> -3
따라서 9를 비트 반전하면 -10이 된다.
-10을 2의 보수법으로 나타내려면 1을 아주 많이 표시해야 해서 화면에 많은 공간이 필요하다.
이를 간략하게 나타내기 위해 -를 사용할 수 있다.
-(minus)
이진수 0b1001(0b와 10001사이에 아주 많은 0이 생략된 상태)의 비트 반전은 0b111....0110 과 같다.
비트 반전한 수는 2의 보수법에서 -10이다. -10을 이진수로 간략하게 나타내기 위해 먼저 -와 10을 나눠서 다룬다.
10을 이진수로 표현하면 0b1010(0b 와 1010 사이에 아주 많은 0이 생략된 상태)고 이진수 앞에 -를 붙여서 표현하면 -0b1010이다.
bin(~0b1001)
# -0b1010
# 1001에서 앞에 -기호가 붙고 1001이 1010으로 바뀌었다참고로 파이썬에서 9를 비트 반전한 이진수를 출력하려고 하면 자체적으로 -를 붙인다.
-0b1010을 10진수로 표현하면 -10이다.
0b뒤의 1은 부호비트가 아니다. 2진수 1010을 10진수로 변환하면 10이고 음수기호 -를 붙여서 -10이 된다.
즉, -는 2진수가 음수임을 (간략하게) 나타내기 위해 사용한다.
비트 반전
import sys
sys.getsizeof(0b1001)
# 28
sys.getsizeof(~0b1001 + 1)
# 2810진수 9와 같은 2진수 0b1001의 크기는 28바이트다. 0b1001의 2의 보수는 ~0b1001 + 1 과 같다. 2의 보수 크기도 28바이트다. 28바이트를 비트로 표현하면 아주 많은 자리수가 필요하다.
파이썬에서 ~(tilde) 연산자는 비트를 반전한다. 비트 반전은 2의 보수에서 1을 뺀 값과 같다.
2진수 0010
1의 보수 1101
2의 보수 11104비트 이진수 2인 0010 의 1의 보수는 1101 이고 2의 보수는 1110 이다. 1의 보수에서 1을 더하면 된다.
여기서 2의 보수 기준으로 1101 은 -3이다. 즉, 2의 보수에서 1을 뺀 값과 같다.
2의 보수법을 사용하는 파이썬에서 비트 반전은 2의 보수에서 1을 뺀 값이다. 그래서 9의 비트 반전은 -10이 된다.
2의 보수와 비트 반전
- 10진수에서 2의 보수는 -만 붙여주면 된다
5 -> -5
- 10진수에서 비트 반전은 -붙이고 1을 뺀다
5 -> -6
- 2진수에서 2의 보수는 비트 반전하고 1을 더한다
0001(2) -> 1001(2)
- 2진수에서 비트 반전은 비트만 바꾼다
0001(2) -> 1000(2)
<참고>
파이썬 알고리즘 인터뷰
https://ko.wikipedia.org/wiki/%EC%A0%95%EC%88%98
https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%83%81%EC%9C%84_%EB%B9%84%ED%8A%B8
https://ko.wikipedia.org/wiki/%EC%B5%9C%ED%95%98%EC%9C%84_%EB%B9%84%ED%8A%B8\
https://ko.wikipedia.org/wiki/1%EC%9D%98_%EB%B3%B4%EC%88%98
https://namu.wiki/w/%EC%A0%95%EC%88%98
https://kangdy25.tistory.com/50
https://hs-archive.tistory.com/26
https://cosmosproject.tistory.com/569
https://hemahero.tistory.com/29
https://hemahero.tistory.com/31
https://hemahero.tistory.com/32
https://blog.naver.com/piyoro/221774762703
https://en.wikipedia.org/wiki/Two%27s_complement
https://ko.wikipedia.org/wiki/2%EC%9D%98_%EB%B3%B4%EC%88%98
https://seollal.tistory.com/700
https://blog.naver.com/hjyang0/183698525
https://tyoon9781.tistory.com/entry/python-int-size-28bytes
https://docs.python.org/3/library/stdtypes.html#numeric-types-int-float-complex