비트로 수 세기

9월 15일 화요일 밤, 도현이 아두이노 보드를 들고 실습실에 들어옵니다. 버튼을 누를 때마다 char count에 1을 더해 화면에 찍는 장난감인데, 127 다음에 −128이 찍혔습니다. "1을 더했는데 음수라니, 이건 버그죠."

은재가 고개를 갸웃합니다. "char는 글자 아니에요? 글자에 왜 부호가 있어요?" 윤 조교가 보드를 받아 내려놓습니다. "char는 그냥 1바이트짜리 정수야. 지난주에 f8이 −8이었던 거 기억하지? 오늘은 그 바이트 안을 비트 하나씩 펼쳐 보자."

2-1. 2진수와 16진수 (9분)

비트는 0 아니면 1인 칸 하나입니다. 비트를 여러 개 늘어놓으면 자리마다 무게가 붙습니다. 맨 오른쪽이 1, 그 왼쪽이 2, 4, 8, …로 두 배씩 커집니다. 10진수의 자리가 1, 10, 100인 것과 같은 생각입니다.

  0   0   1   0   1   0   1   0      ← 비트
128  64  32  16   8   4   2   1      ← 자리의 무게
          32  +   8  +   2  = 42

비트 8개가 바이트입니다. 2진수는 너무 길어서 사람은 보통 16진수로 씁니다. 비트 4개가 16진수 한 자리(0–9, a–f)가 되니, 바이트 하나는 정확히 16진수 두 자리입니다. 0010 1010 = 0x2a = 42. 지난주 objdump의 48 89 7d f8이 바이트 네 개로 딱 떨어져 보였던 이유입니다.

x86-64는 같은 수를 네 가지 폭으로 다룹니다. 이름은 16비트 CPU 시절의 '워드(word) = 16비트'에서 왔습니다. 4교시에 QWORD PTR, DWORD PTR로 다시 만납니다.

C로 치면 리눅스 x86-64에서 char가 8비트, short가 16비트, int가 32비트, long과 포인터가 64비트입니다. 지난주의 add는 long이라 64비트(REX.W = 1)로 더했습니다. 오른쪽 '부호 있는 범위'는 2-3절에서 설명합니다.

2-2. 부호 없는 수는 시계처럼 감긴다 (8분)

비트 8개로 만들 수 있는 무늬는 2⁸ = 256가지뿐입니다. 이 256가지를 시계처럼 한 바퀴에 늘어놓은 것이 아래 원판입니다. 일단 바깥 숫자(부호 없이 읽은 값)만 보세요.

부호 없이 읽으면 8비트는 0–255입니다. 255에 1을 더하면 256이 되어야 하지만, 256은 1 0000 0000으로 비트 9개가 필요합니다. 8비트 칸에는 아래 8개만 남고 맨 위 1은 떨어져 나가니 결과는 0입니다. 넘친 덧셈은 256으로 나눈 나머지가 됩니다. 시계에서 12시 다음이 1시인 것과 같습니다.

CPU는 떨어져 나간 그 비트를 버리지 않고 CF(carry flag, 올림 플래그)에 남깁니다. 64비트 덧셈도 똑같이 2⁶⁴로 나눈 나머지이고, 넘치면 CF가 켜집니다. C 표준도 부호 없는 정수(unsigned)의 계산은 이렇게 감긴다고 정해 둡니다.

2-3. 2의 보수: 같은 비트, 두 가지 읽기 (12분)

이번에는 원판의 안쪽 숫자를 보세요. 0–127은 바깥과 같고, 128–255 자리에는 −128–−1이 적혀 있습니다. 이것이 2의 보수(two's complement) 읽기입니다. 규칙은 한 줄입니다. 맨 위 비트의 무게를 +128 대신 −128로 친다.

1000 0000  = −128
1111 1111  = −128 + 127 = −1
1001 1100  = −128 + 16 + 8 + 4 = −100
0111 1111  = 127

그래서 맨 위 비트가 1이면 음수, 0이면 0 이상입니다. 맨 위 비트를 부호 비트라고도 부릅니다. 범위는 −128–127로 음수가 하나 더 많습니다.

왜 하필 이렇게 읽을까요? 덧셈 회로를 하나도 바꾸지 않아도 되기 때문입니다. 원판에서 −1(0xff)에 1을 더하면 맨 위 경계를 넘어 0(0x00)이 됩니다. 부호 없이 읽은 '255 + 1 = 0(감김)'과 부호 있게 읽은 '−1 + 1 = 0'이 같은 비트, 같은 계산입니다. CPU의 add는 수에 부호가 있는지 모릅니다. 비트를 더할 뿐이고, 어떻게 읽을지는 프로그램이 정합니다.

진짜 gcc 출력이 그것을 보여 줍니다. int(부호 있는 32비트) 두 개를 더하는 add32는 지난주의 add와 같은 옵코드 01을 쓰고, REX가 없어 32비트로 더할 뿐입니다(first.O0.bytes, 줄임).

0000000000000019 <add32>:
  19:	55                   	push   rbp
  1a:	48 89 e5             	mov    rbp,rsp
  1d:	89 7d fc             	mov    DWORD PTR [rbp-0x4],edi
  20:	89 75 f8             	mov    DWORD PTR [rbp-0x8],esi
  23:	8b 55 fc             	mov    edx,DWORD PTR [rbp-0x4]
  26:	8b 45 f8             	mov    eax,DWORD PTR [rbp-0x8]
  29:	01 d0                	add    eax,edx
(줄임)

같은 함수를 unsigned로 바꿔 컴파일해도(unsigned addu(unsigned a, unsigned b)) -O0에서는 똑같이 01 d0, -O2에서는 int 판과 똑같이 8d 04 37(lea eax,[rdi+rsi*1])이 나옵니다. 덧셈에는 부호 있는 판과 없는 판이 따로 없습니다. 차이는 비교, 나눗셈, 폭 넓히기처럼 결과를 '읽는' 쪽에서 생깁니다(2-4절, 5교시).

−x는 어떻게 만들까요? 비트를 모두 뒤집고 1을 더합니다. 이유는 간단합니다. x와 x를 뒤집은 것(~x)을 더하면 모든 자리가 1, 곧 1111 1111 = −1입니다. x + ~x = −1이니 ~x + 1 = −x입니다.

  5  = 0000 0101
 ~5  = 1111 1010     (뒤집기)
 −5  = 1111 1011     (1 더하기) = 0xfb

예외가 하나 있습니다. −128(1000 0000)을 뒤집고 1을 더하면 다시 1000 0000입니다. +128은 8비트 부호 있는 수에 없기 때문입니다. 실습대에서 값을 128에 두고 맨 아래 줄을 보세요.

폭을 넓힐 때는 맨 위 비트를 복사해 왼쪽을 채웁니다(부호 확장). 8비트 −1(0xff)을 64비트로 늘리면 0xffffffffffffffff, 여전히 −1입니다. 반대로 0으로 채우면(0 확장) 255가 됩니다. 어느 쪽으로 늘릴지도 명령어가 정합니다(3·4교시).

맨 위 비트가 곧 부호라는 것을 gcc도 압니다. int is_neg(int x) { return x < 0; }를 -O2로 컴파일하면 비교 명령어가 없습니다(first.O2.bytes).

0000000000000040 <is_neg>:
  40:	89 f8                	mov    eax,edi
  42:	c1 e8 1f             	shr    eax,0x1f
  45:	c3                   	ret

shr eax,0x1f는 eax를 오른쪽으로 31자리 밀어 맨 위 비트만 맨 아래에 남깁니다(3교시). 32비트 x가 음수인지는 비트 31 하나로 정해집니다.

2-4. 덧셈이 남기는 플래그 네 개 (12분)

CPU는 덧셈 결과를 부호 없이 읽을지 부호 있게 읽을지 모르니, 두 가지 읽기 모두에 필요한 정보를 한꺼번에 남깁니다. 그것이 플래그입니다. 비트를 눌러 가며 확인해 보세요.

네 플래그의 뜻입니다. add와 sub는 넷을 모두 새로 정합니다.

OF는 '맨 위 자리로 들어온 올림'과 '맨 위 자리에서 나간 올림'이 다를 때 1입니다. 실습대가 빨간 테두리로 보여 주는 두 칸입니다. 말로 바꾸면 '부호가 같은 두 수를 더했는데 결과의 부호가 다르다'입니다. 양수 + 양수가 음수로 나오거나 음수 + 음수가 양수로 나올 때입니다. 부호가 다른 두 수의 덧셈은 절대 넘치지 않습니다.

빼기에서 CF는 '부호 없이 a < b라서 빌려 와야 했다'는 뜻입니다. 5 − 7은 부호 없이 보면 넘침(CF = 1)이고 부호 있게 보면 −2로 정상(OF = 0)입니다. 같은 결과를 두고 CF와 OF가 서로 다른 말을 합니다. 프로그램은 자기가 수를 어떻게 읽는지에 맞는 플래그를 봐야 합니다.

5교시에 쓸 것을 미리 하나 봅니다. cmp a, b는 a − b를 계산해 플래그만 남기는 명령어이고, 조건 점프가 그 플래그를 읽습니다. 64비트 −1(0xffffffffffffffff)과 1을 cmp하면 SF = 1, OF = 0, CF = 0입니다. 부호 있는 비교 jl은 SF ≠ OF를 보고 '−1 < 1, 참'이라 하고, 부호 없는 비교 jb는 CF를 보고 '거짓'이라 합니다. 부호 없이 읽으면 0xff…ff는 가장 큰 수이기 때문입니다.

2-5. 64비트도 감긴다: 팩토리얼 미리보기 (4분)

8비트에서 본 일은 64비트에서도 그대로 일어납니다. 다만 경계가 2⁶³ − 1 = 9,223,372,036,854,775,807(약 9.22 × 10¹⁸)로 멀 뿐입니다. 윤 조교가 6교시에 쓸 재귀 팩토리얼 fact(n)을 미리 돌려 봅니다.

• fact(20) = 2,432,902,008,176,640,000. 경계 안이라 맞습니다.
• fact(21)의 참값은 51,090,942,171,709,440,000입니다. 비트 66개가 필요해서 64비트 칸에 넣으면 2⁶⁴로 나눈 나머지만 남고, 부호 있게 읽으면 −4,249,290,049,419,214,848입니다.

여기서 C의 약속을 정확히 알아 둡니다. C 표준에서 부호 있는 정수의 넘침은 '정의되지 않은 동작'입니다. 위의 음수는 gcc -O0이 만든 곱셈 명령어가 64비트로 감긴 결과일 뿐, C가 약속한 값이 아닙니다. 최적화를 켜면 컴파일러는 '넘치지 않는다'고 가정하고 코드를 바꿀 수 있습니다. 반면 도현의 char는 사정이 다릅니다. count + 1은 int로 계산되어 128이 되고, 그것을 다시 char에 넣을 때 바뀌는 값은 구현이 정하는데, gcc는 아래 8비트를 그대로 남깁니다.

파이썬의 int는 이렇게 넘치지 않습니다. math.factorial(21)은 66비트짜리 정확한 값을 돌려줍니다. 그 대가가 무엇인지가 10교시의 주제입니다.

자주 하는 실수 (2분)

• 0xff는 255라고 단정한다. 비트만 보고는 모릅니다. 부호 없이 255, 부호 있게 −1입니다. 읽는 쪽(타입, 명령어)이 정합니다.
• CF를 부호 있는 넘침으로 읽는다. CF는 부호 없는 넘침, OF가 부호 있는 넘침입니다. 0xff + 1은 CF = 1이지만 −1 + 1 = 0이라 OF = 0입니다.
• 음수를 '맨 위 비트만 1로 바꾼 수'로 생각한다. −1은 1000 0001이 아니라 1111 1111입니다.
• −x를 비트 뒤집기로 만든다. 뒤집기(~x)는 −x − 1입니다. 1을 더해야 −x입니다.
• C에서 부호 있는 넘침이 늘 감긴다고 믿는다. 기계는 감기지만 C 표준은 약속하지 않습니다. 감김에 기대려면 unsigned를 씁니다.

연습 문제 (3분)

1. 16비트 부호 있는 수로 0xffff와 0x8000은 각각 얼마인가요? 16비트 0xffff + 1의 CF와 OF는?
2. 8비트 add로 0x90 + 0x90을 계산하면 결과와 네 플래그는 무엇인가요? 부호 있게 읽으면 무슨 일이 일어났나요?
3. 32비트 int x = 2147483647;에 add eax, 1을 하면 eax는 16진수로 얼마이고, SF와 OF는?

풀이

1. 맨 위 비트의 무게가 −32,768이므로 0xffff = −32,768 + 32,767 = −1, 0x8000 = −32,768. 0xffff + 1 = 0x0000으로 CF = 1, OF = 0(−1 + 1 = 0은 정상).
2. 144 + 144 = 288 = 256 + 32이므로 결과 0x20, CF = 1, ZF = 0, SF = 0, OF = 1. 부호 있게는 −112 + (−112) = −224로 범위 밖이라, 음수 + 음수가 양수 32가 되었습니다. 두 가지 읽기 모두 넘쳤습니다.
3. 0x7fffffff + 1 = 0x80000000, 곧 −2,147,483,648. SF = 1, OF = 1(CF = 0). 8비트의 127 + 1과 같은 일이 32비트 경계에서 일어났습니다.

다음 주 화요일(9월 22일)에는 이 비트들이 들어 있는 CPU 안의 칸, 레지스터를 봅니다. rax, eax, ax, al이 한 레지스터의 다른 이름이라는 것과 mov, add, xor 같은 첫 명령어들을 하나씩 실행합니다.