정수를 비트로 표현하는 방법

- 본 글은 [한 권으로 읽는 컴퓨터 구조와 프로그래밍] 책을 읽고 정리한 내용이다.

양의 정수 표현

- 10진수 체계

• 10진수(decimal number) 체계에서 10가지 기호인 숫자(digit)를 상자에 담을 수 있다.
• 각각 이름이 붙어있는 상자들이 오른쪽에서 왼쪽 방향으로 쌓인다.
  • 맨 오른쪽 상자 : 일의 자리
  • 오른쪽에서 두 번째 상자 : 십의 자리
  • 오른쪽에서 세 번째 상자 : 백의 자리

백의 자리	십의 자리	일의 자리
100	10	1
10^2	10^1	10^1

 

• ex) 5028 = 5 * 10^3 + 0 * 10^2 + 2 * 10^1 + 8 * 10^0

5	0	2	8
10^3	10^2	10^1	10^0

 

- 비트 체계

• 비트의 경우 10진 숫자 대신 비트를 사용하여 각 상자에 사용 가능한 기호는 1과 0 두가지이다.

거듭제곱	10진수
2^0	1
2^1	2
2^2	4
2^3	8
2^4	16
2^5	32
2^6	64
2^7	128
2^8	256

 

• ex) 5028 = 4096 + 512 + 256 + 128 + 32 + 4 = 1 * 2^12 + 0 * 2^11 + 0 * 2^10 + 1 * 2^9 + 1 * 2^8 + 1 * 2^7 + 0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 (13비트 수)

2^12	2^11	2^10	2^9	2^8	2^7	2^6	2^5	2^4	2^3
1	0	0	1	1	1	0	1	0	0
2^2	2^1	2^0
1	0	0

 

• 2진수로 표현할 수 있는 값의 범위

비트 개수	값의 개수	값의 범위
4	16	0 - 15
8	256	0 - 255
12	4096	0 - 4095
16	65536	0 - 65535
20	1048576	0 - 1048575
24	16777216	0 - 16777215
32	4294967296	0 - 4294967295
64	18446744073709551616	0 - 18446744073709551615

 

• 가장 오른쪽의 비트 = 가장 작은 유효 비트 (least significant bit) = LSB
• 가장 왼쪽의 비트 = 가장 큰 유효 비트 (most significant bit) = MSB

 

• 5028을 16비트 2진수로 저장

MSB -> 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0  <- LSB

• 리딩 제로 (leading zero) : 가장 왼쪽에 위치한 상자보다 더 왼쪽에 추가한 0

 

2진수 덧셈

• 10진 덧셈의 경우 오른쪽에서 왼쪽 방향으로 각 자리의 숫자를 더한 후 결과가 9보다 크면 1을 올려준다.
• 2진 덧셈의 경우 각 비트를 LSB에서 MSB 방향으로 더한 후 결과가 1보다 크면 1을 올려준다.
  • ex ) 1 + 5 = 6 

  •   0 0 1  -> 1
    + 1 0 1  -> 5
    --------
      1 1 0  -> 6

 

• 논리 연산을 사용하여 2진 덧셈 수행

A	B	A AND B	A + B	A XOR B	A	B
0	0	0	00	0	0	0
0	1	0	01	1	0	1
1	0	0	01	1	1	0
1	1	1	10	0	1	1

• 두 비트를 서로 더한 결과 = 두 비트를 XOR 한 값
• 올림 = 두 비트를 AND 한 값
  • ex ) 1 과 1을 더한 결과 = 10 -> (1 AND 1), (1 XOR 1)

 

• 오버플로(overflow) : 덧셈의 결과가 우리가 사용하는 비트의 개수로 표현 가능한 범위를 벗어나게 될 경우에 발생한다.
  • ex) 4비트 덧셈 상황에서 1001 + 1000 = 10001 이지만 MSB 왼쪽에 남은 비트가 없기 때문에 0001이 된다.

 

음수 표현

• 4비트를 이용하여 0 부터 15까지 16가지 수를 표현할 수 있다.
• 4비트로 16가지 수를 표현할 수 있다는 말이 0부터 15까지만 표현가능하다는 말은 아니다.

 

- 부호와 크기

• 음수와 양수를 구별하기 위해 흔히 부호(sign)를 사용한다.
• 부호에는 양부호(+)와 음부호(-) 2가지가 있기 때문에 비트 하나를 이용하여 표현할 수 있다.
• 가장 왼쪽 비트(MSB) 를 부호를 표현하는 비트로 사용한다.
  • 4비트의 경우 부호 비트를 제외하고 3비트가 남고 이를 이용하여 0~7의 수를 표현할 수 있다.
  • 부호 비트가 0이면 양수, 1이면 음수로 취급한다.

부호	2^2	2^1	2^0	10진수
0	1	1	1	+7
0	1	1	0	+6
0	1	0	1	+5
0	1	0	0	+4
0	0	1	1	+3
0	0	1	0	+2
0	0	0	1	+1
0	0	0	0	+0

부호	2^2	2^1	2^0	10진수
1	0	0	0	-0
1	0	0	1	-1
1	0	1	0	-2
1	0	1	1	-3
1	1	0	0	-4
1	1	0	1	-5
1	1	1	0	-6
1	1	1	1	-7

• +1 과 -1 의 더하기

•   0 0 0 1 -> +1
  + 1 0 0 1 -> -1
  ----------
    1 0 1 0 -> -2

  합계의 결과를 0으로 예상하지만 실제로는 부호와 크기 표현법으로 계산한 결과 -2가 된다.

 

- 1의 보수

• 음수를 표현하는 다른 방법 -> 양수의 모든 비트를 뒤집는 방법 => 1의 보수(one's complement) 표현법
• 비트들을 부호 비트와 나머지로 나누고 NOT 연산을 통해 보수를 얻는다.

부호	2^2	2^1	2^0	10진수
0	1	1	1	+7
0	1	1	0	+6
0	1	0	1	+5
0	1	0	0	+4
0	0	1	1	+3
0	0	1	0	+2
0	0	0	1	+1
0	0	0	0	+0

부호	2^2	2^1	2^0	10진수
1	1	1	1	-0
1	1	1	0	-1
1	1	0	1	-2
1	1	0	0	-3
1	0	1	1	-4
1	0	1	0	-5
1	0	0	1	-6
1	0	0	0	-7

• ex) 0111(+7) 의 비트를 NOT 연산하면 1000(-7)을 얻는다.
• 1의 보수 표현법에도 0이 +0, -0 두 가지로 표현된다.
• 덧셈의 경우 MSB 쪽에서 올림이 발생하면 LSB 로 올림을 전달하는 순환 올림(end-around carry)을 사용한다.

  •   0 0 1 0 -> +2
    + 1 1 1 0 -> -1
    ----------
      0 0 0 0 -> 0
    + 0 0 0 1 -> 1 순환 올림
    ----------
      0 0 0 1 -> +1​

    1의 보수를 사용하여 +2 와 -1 에 더하기 연산을 수행하면 일반 덧셈처럼 계산하고 순환올림을 사용한다.
• 잘 작동하지만 순환 올림의 처리를 위한 하드웨어가 추가적으로 필요하기 때문에 좋은 해법은 아니다
• 현대 컴퓨터에서는 부호와 크기 표현법, 1의 보수법 모두 사용하지 않고 다른 방법을 사용한다.

 

- 2의 보수

• 특별한 하드웨어의 추가없이 XOR 과 AND 연산만으로 일반 정수 사이의 덧셈을 가능하게 하는 방법
• +1에 더했을 때 0이 나오는 비트 패턴을 찾아서 -1을 표현하는 비트 패턴으로 사용한다.

  •   0 0 0 1 -> 1
    + 1 1 1 1 -> -1
    ----------
      0 0 0 0 -> 0

    0001(+1)을 뒤집으면 1110이 되고 거기에 1을 더하면 1111 -> -1
• 2의 보수 표현법은 부호가 있는 정수의 표현에 가장 많이 사용되는 방법이다.
• 어떠한 수의 각 비트에 NOT 을 취하고(비트 뒤집기) 1을 추가하여 음수를 얻는다.
• 이 때 MSB 에서 올림이 발생하면 그 값은 버린다.

부호	2^2	2^1	2^0	10진수
0	1	1	1	+7
0	1	1	0	+6
0	1	0	1	+5
0	1	0	0	+4
0	0	1	1	+3
0	0	1	0	+2
0	0	0	1	+1
0	0	0	0	+0

부호	2^2	2^1	2^0	10진수
1	1	1	1	-1
1	1	1	0	-2
1	1	0	1	-3
1	1	0	0	-4
1	0	1	1	-5
1	0	1	0	-6
1	0	0	1	-7
1	0	0	0	-8

• 0000(+0)의 모든 비트를 뒤집으면 1111이고 여기에 1을 더하면 [1]0000이 되는데 [1]은 올림 비트가 되어 버려 다시 0000(+0)이 된다. -> 0을 표현하는 것이 1개

 

• 2의 보수로 표현하는 값의 범위

비트 개수	값의 개수	값의 범위
4	16	-8 ~ 7
8	256	-128 ~ 127
12	4096	-2048 ~ 2047
16	65536	-32768 ~ 32767
20	1048576	-524288 ~ 524287
24	16777216	-8388608 ~ 8388607
32	4294967296	-2147483648 ~ 2147483647
64	18446744073709551616	-9223372036854775808  ~ 9223372036854775807