산술 연산과 상태 플래그

요약

계산기는 답만 보여 주지만 CPU는 계산할 때마다 답에 대한 쪽지 몇 장을 함께 남긴다. 답이 0인가, 맨 윗자리 비트가 1인가, 칸이 모자라 넘쳤는가. 넘쳤는지는 같은 비트를 음수가 없는 수로 볼 때와 음수가 있는 수로 볼 때 답이 달라서 쪽지가 두 장이다. CPU는 프로그래머가 어느 쪽으로 쓰는지 모르므로 늘 두 장을 다 쓰고, 어느 쪽지를 읽을지는 프로그래머가 고른다. 쪽지는 다음 계산이 덮어쓰므로 필요한 것은 바로 읽어야 한다.

예시로 보기

AL에 FFh를 넣고 1을 더하면 AL은 00h가 된다. 이 계산은 맞았을까?

FFh를 255로 쓰고 있었다면 255 + 1 = 256인데 0이 나왔다. 틀렸다.
FFh를 −1로 쓰고 있었다면 −1 + 1 = 0이다. 맞았다.

CPU는 덧셈 회로 하나로 두 경우를 똑같이 계산한다. 부호 있는 수인지 없는 수인지 구별하지 못한다. 알맞은 종류로 쓰는 것은 온전히 프로그래머의 몫이다. 그래서 CPU는 답과 함께 1비트짜리 표시 여러 개를 남긴다. 이 표시를 상태 플래그라 부른다. 방금 계산에서는 “부호 없는 수로는 넘쳤다”는 표시가 1이 되고 “부호 있는 수로는 넘쳤다”는 표시는 0이 된다.

검증: 본문의 모든 예와 추적 표, 8비트 ADD·SUB 65,536쌍 전수에서 네 플래그가 정의와 맞는 것, 넘침 플래그의 세 정의가 같은 것, “OF = CF XOR MSB”가 틀리는 개수, INC·DEC·NEG의 플래그, 카드 C2·C5. 파이썬 흉내로 확인 — 19_x86-status-flags_verify.py

정의

CPU에서 계산을 맡은 부분(ALU)에는 산술 연산과 비트 연산의 결과를 알려 주는 상태 플래그가 있다. 플래그의 값은 목적지 피연산자에 들어간 결과로 정해진다. 플래그가 1이면 켜졌다(set), 0이면 꺼졌다(clear)고 말한다.

플래그	켜지는 때	근거
제로 플래그 ZF	결과가 0이다
부호 플래그 SF	결과가 음수다. 결과의 맨 윗자리 비트를 그대로 복사한 값이다
올림 플래그 CF	부호 없는 수로 볼 때 결과가 칸의 범위를 벗어났다(너무 크거나 0보다 작다)
넘침 플래그 OF	부호 있는 수로 볼 때 결과가 칸의 범위를 벗어났다

MOV는 플래그를 바꾸지 않는다.

기호로 쓰면 다음과 같다. 피연산자의 크기를 \(n\)비트라 하자(8, 16, 32 가운데 하나). 두 피연산자의 비트를 부호 없는 수로 읽은 값을 \(a\), \(b\)라 하고, 같은 비트를 2의 보수로 읽은 값을 \(\hat a\), \(\hat b\)(에이 햇, 비 햇)라 한다. 결과 \(r\)은 참값을 \(2^n\)으로 나눈 나머지다¹.

\[\text{ADD: } r = (a + b) \bmod 2^n, \qquad \text{SUB: } r = (a - b) \bmod 2^n\] \[\mathrm{ZF} = [\,r = 0\,], \qquad \mathrm{SF} = r\text{의 } (n-1)\text{번 비트}\] \[\mathrm{CF} = \begin{cases}[\,a + b \ge 2^n\,] & \text{ADD}\\ [\,a < b\,] & \text{SUB}\end{cases} \qquad \mathrm{OF} = [\,\hat a \pm \hat b \notin [-2^{n-1},\ 2^{n-1} - 1]\,]\]

\([\,\cdot\,]\)는 안의 조건이 참이면 1, 거짓이면 0이다. \(\pm\)는 ADD면 더하기, SUB면 빼기다. 8비트라면 CF는 “참값이 0~255 밖”, OF는 “참값이 −128~127 밖”이다.

회로가 정하는 법

덧셈 회로는 부호를 모르므로 올림만 보고 두 플래그를 정한다.

ADD. CF는 맨 윗자리 비트 밖으로 나간 올림이다. OF는 “맨 윗자리 비트로 들어온 올림”과 “맨 윗자리 비트에서 나간 올림”이 서로 다를 때 1이다. 8비트라면 6번 비트에서 올라온 올림과 7번 비트에서 나간 올림의 XOR이다.
SUB. 빼는 수의 2의 보수를 더한다. CF는 나간 올림을 뒤집은 값이다. OF는 덧셈과 같은 방법으로 정한다.

FFh + 01h                          7Fh + 01h
  올림   1 1 1 1 1 1 1 1             올림   0 1 1 1 1 1 1 1
           1 1 1 1 1 1 1 1                    0 1 1 1 1 1 1 1
         + 0 0 0 0 0 0 0 1                  + 0 0 0 0 0 0 0 1
         ─────────────────                  ─────────────────
           0 0 0 0 0 0 0 0                    1 0 0 0 0 0 0 0
들어온 올림 1, 나간 올림 1           들어온 올림 1, 나간 올림 0
CF = 1, OF = 1 XOR 1 = 0            CF = 0, OF = 1 XOR 0 = 1

“올림” 줄의 맨 왼쪽 수가 맨 윗자리 밖으로 나간 올림이고, 그 오른쪽 수가 맨 윗자리로 들어온 올림이다¹.

SUB의 “빼는 수의 2의 보수를 더한다”는 비트를 뒤집은 수와 1을 한꺼번에 더한다는 뜻이다. 빼는 수에 먼저 NEG를 해서 얻은 수를 더한다고 글자 그대로 읽으면, 빼는 수가 0일 때 나가는 올림이 없어 CF = 1이 나온다. 실제로는 \(a - 0\)에서 빌려 올 일이 없으니 CF = 0이다².

넘침 플래그의 세 가지 정의

ADD에서 다음 셋은 같은 말이다¹.

부호 있는 수로 본 참값 \(\hat a + \hat b\)가 범위 밖이다. (위의 정의)
두 피연산자의 부호가 같은데 결과의 부호가 다르다. 양수 둘을 더했는데 음수가 나왔거나, 음수 둘을 더했는데 양수가 나왔다. (어림 규칙)
맨 윗자리 비트로 들어온 올림과 나간 올림이 다르다. (회로의 규칙)

증명

맨 윗자리 한 칸의 덧셈만 보고, 두 피연산자의 부호 비트가 (0, 0), (1, 1), 서로 다름인 세 경우로 나눈다(경우 나누기).

증명 펼치기

맨 윗자리의 두 비트를 \(a_s\), \(b_s\), 아래에서 들어온 올림을 \(c_{in}\), 밖으로 나간 올림을 \(c_{out}\), 결과의 맨 윗자리 비트를 \(r_s\)라 한다.

한 칸의 덧셈. \(r_s\)는 \(a_s + b_s + c_{in}\)의 아랫자리이고, \(c_{out}\)은 셋 가운데 둘 이상이 1일 때 1이다. — 한 자리 2진 덧셈
둘 다 0 이상(\(a_s = b_s = 0\)). 1이 될 수 있는 것이 \(c_{in}\) 하나뿐이라 \(c_{out} = 0\)이고 \(r_s = c_{in}\)이다. 올림이 나가지 않았으니 \(r = a + b = \hat a + \hat b\)다. 이 값이 범위를 넘는 것은 \(2^{n-1}\) 이상일 때, 곧 \(r_s = 1\)일 때다. 그래서 (넘침) ⟺ (\(r_s = 1\): 양수 둘의 합이 음수로 보임) ⟺ (\(c_{in} = 1\)) ⟺ (\(c_{in} \ne c_{out}\)). — 1단계, 2의 보수의 범위
둘 다 음수(\(a_s = b_s = 1\)). 1이 이미 둘이라 \(c_{out} = 1\)이고 \(r_s = c_{in}\)이다. \(\hat a = a - 2^n\), \(\hat b = b - 2^n\)이고 올림이 나갔으니 \(r = a + b - 2^n\)이다. 그래서 \(\hat a + \hat b = r - 2^n\)이다. 이 값이 \(-2^{n-1}\) 이상인 것은 \(r \ge 2^{n-1}\), 곧 \(r_s = 1\)일 때다. 그래서 (넘침) ⟺ (\(r_s = 0\): 음수 둘의 합이 양수로 보임) ⟺ (\(c_{in} = 0\)) ⟺ (\(c_{in} \ne c_{out}\)). — 1단계, 2의 보수로 읽는 법
부호가 다르다. 음수 쪽을 \(\hat a\), 0 이상인 쪽을 \(\hat b\)라 하면 \(\hat a \le \hat a + \hat b \le \hat b\)다. 두 끝이 범위 안이므로 합도 범위 안이다. 넘치지 않는다. 한편 맨 윗자리에 1이 하나뿐이라 \(c_{out} = c_{in}\)이다. 정의 1, 2, 3이 모두 “아니다”로 일치한다. — 부등식, 1단계
세 경우 모두에서 세 정의가 같은 답을 낸다. ∎

SUB는 \(a + (b\text{의 비트를 뒤집은 수}) + 1\)이라는 덧셈이므로 같은 논증이 통한다. 전수 검사로도 확인했다.

스스로 설명해 보기

1. 2단계에서 \(c_{out} = 0\)이라고 한 근거

1단계에서 \(c_{out}\)은 \(a_s\), \(b_s\), \(c_{in}\) 가운데 둘 이상이 1일 때만 1이다. \(a_s = b_s = 0\)이면 1이 많아야 하나라 \(c_{out} = 0\)이다.

2. 3단계에서 \(\hat a + \hat b = r - 2^n\)이 나오는 과정

맨 윗자리 비트가 1인 \(n\)비트 값은 2의 보수로 읽으면 부호 없는 값에서 \(2^n\)을 뺀 것이다. 그래서 \(\hat a + \hat b = a + b - 2^{n+1}\)이다. 올림이 나갔으므로 \(a + b = r + 2^n\)이고, 넣으면 \(r - 2^n\)이다.

3. 4단계에서 합이 두 수 사이에 있다고 한 근거

\(\hat a < 0 \le \hat b\)다. \(\hat a\)에 0 이상인 수를 더하면 \(\hat a\)보다 작아지지 않고, \(\hat b\)에 음수를 더하면 \(\hat b\)보다 커지지 않는다.

이 증명의 핵심 아이디어는?

넘쳤는지는 맨 윗자리 한 칸에서 일어난 일만 보면 안다. 아래 비트들이 한 일은 “들어온 올림” 하나에 다 담겨 있다. 부호 비트의 조합이 셋뿐이라 경우를 다 따질 수 있다.

이 방법을 쓸 수 있는 다른 상황은?

뺄셈(비트를 뒤집어 더하는 덧셈으로 본다)과 16비트, 32비트 계산. 맨 윗자리가 15번, 31번으로 바뀔 뿐 논증은 같다.

예제

제로 플래그와 부호 플래그.

mov cx,1
sub cx,1         ; CX = 0, ZF = 1
mov ax,0FFFFh
inc ax           ; AX = 0, ZF = 1
inc ax           ; AX = 1, ZF = 0

mov al,0
sub al,1         ; AL = 11111111b, SF = 1
add al,2         ; AL = 00000001b, SF = 0

올림 플래그. 너무 커도, 0 아래로 내려가도 켜진다.

mov al,0FFh
add al,1         ; CF = 1, AL = 00
mov al,0
sub al,1         ; CF = 1, AL = FF

넘침 플래그.

mov al,+127
add al,1         ; OF = 1, AL = 80h (127 + 1이 −128로 보인다)

mov al,80h
add al,92h       ; OF = 1  (음수 둘을 더했는데 12h, 양수가 나왔다)
mov al,-2
add al,+127      ; OF = 0  (부호가 다르면 넘치지 않는다)

추적 표. 다음 명령을 차례로 실행할 때 결과와 플래그는 이렇다³.

명령	결과	SF	ZF	CF	OF
`mov ax,00FFh`	AX = 00FFh	—	—	—	—
`add ax,1`	AX = 0100h	0	0	0	0
`sub ax,1`	AX = 00FFh	0	0	0	0
`add al,1`	AL = 00h	0	1	1	0
`mov bh,6Ch`	BH = 6Ch	그대로	그대로	그대로	그대로
`add bh,95h`	BH = 01h	0	0	1	0
`mov al,2`	AL = 02h	그대로	그대로	그대로	그대로
`sub al,3`	AL = FFh	1	0	1	0

add ax,1과 add al,1은 같은 FFh에 1을 더하지만 칸의 크기가 달라 CF가 다르다. 16비트 칸에서는 0100h가 들어가고, 8비트 칸에서는 넘친다.

넘침 플래그가 켜지는 예와 꺼지는 예(8비트)³.

계산	부호 있는 수로 읽으면	OF
7Fh + 01h = 80h	127 + 1 = 128 → 범위 밖	1
80h + 80h = 00h	−128 + (−128) = −256 → 범위 밖	1
80h − 01h = 7Fh	−128 − 1 = −129 → 범위 밖	1
FFh + 01h = 00h	−1 + 1 = 0	0
02h − 03h = FFh	2 − 3 = −1	0

INC, DEC, NEG. INC와 DEC는 ZF, SF, OF를 ADD 1, SUB 1처럼 바꾸지만 CF는 건드리지 않는다. NEG는 값이 0이 아니면 CF를 켜고, 값이 범위에서 가장 작은 음수(8비트에서 −128)일 때 OF를 켠다⁴.

설계 이유

플래그가 “넘쳤다” 하나가 아니라 CF와 OF 둘인 것은 CPU가 수의 종류를 모르기 때문이다. 같은 덧셈 회로의 답 FFh + 01h = 00h가 한쪽 해석에서는 틀리고 다른 쪽에서는 맞다. 종류마다 덧셈 명령을 따로 두는 대신 명령은 하나만 두고, 두 해석 각각에 대한 표시를 다 남긴다. 프로그래머는 자기가 쓰는 해석에 맞는 플래그만 본다.

플래그는 그 자체로 쓰기보다 다음 명령의 갈림길이 된다. 그 관계를 그림으로 그리면 이렇다.

flowchart TD
    ALU["ALU"] -->|"~의 일부"| CPU["CPU"]
    ALU -->|"실행한다"| OPS["산술·비트 연산"]
    CPU -->|"실행한다"| JMP["조건 점프"]
    OPS -->|"값을 바꾼다"| FLAGS["상태 플래그"]
    FLAGS -->|"붙어 있다"| ALU
    FLAGS -->|"읽어서 쓴다"| JMP
    JMP -->|"만들어 준다"| LOGIC["갈림길 논리"]

활용

플래그를 읽어 갈라지는 명령: 조건 점프. 값은 바꾸지 않고 플래그만 얻는 명령: TEST와 CMP.
상태 플래그는 모두 여섯 개다. 위의 넷에 더해 패리티 플래그(결과의 아랫바이트에 1이 짝수 개면 켜진다)와 보조 올림 플래그(3번 비트에서 4번 비트로 올림이 생기면 켜진다)가 있다.
결과 값을 구할 때는 16진수로 계산하는 편이 쉽다. 7Fh + 1 = 80h처럼 바로 나온다.
흔한 실수: 부호 있는 계산의 넘침을 CF로 확인한다. 어느 플래그를 볼지는 올림 플래그와 넘침 플래그 비교에 있다.
흔한 실수: 계산과 플래그 확인 사이에 다른 산술 명령을 끼워 넣어 플래그를 덮어쓴다. MOV는 끼워도 된다.
연습: 플래그 추적 예제 사다리

연결

선수: 덧셈·뺄셈 명령, 정수의 2진 표현과 2의 보수
플래그가 모여 있는 레지스터: x86 레지스터
한 자리 덧셈의 올림과 XOR: 불 대수와 논리 회로
자바는 정수가 넘쳐도 아무 표시를 주지 않는다. CPU가 남긴 이 플래그를 언어가 프로그램에 보여 주지 않는 것이다: 연산자와 오버플로

자주 하는 오해

“올림 플래그가 켜졌으니 계산 결과가 틀렸다”

틀렸다. 올림 플래그는 “부호 없는 수로 읽으면 범위를 벗어났다”만 말한다. 그럴듯해 보이는 까닭은 손으로 덧셈할 때 맨 앞에서 올림이 나오면 자리가 모자란 것이기 때문이다. 하지만 FFh + 01h를 −1 + 1로 쓰고 있었다면 답 00h는 정확하고, 그때도 CF는 1이다. 부호 있는 계산이 틀렸는지는 OF가 말해 주고, 이 예에서 OF는 0이다. 반대로 7Fh + 01h = 80h는 CF가 0인데도 127 + 1이 −128이 되어 부호 있는 계산으로는 틀렸다. 확인하는 법: 두 피연산자를 자기가 쓰는 해석(부호 있음, 없음)의 10진수로 바꿔 참값을 구하고, 그 해석의 범위 안인지 본다.

“넘침 플래그는 올림 플래그와 결과의 맨 윗자리 비트를 XOR한 값이다”

틀렸다. 그럴듯해 보이는 까닭은 맞는 규칙도 XOR이고, 흔히 드는 예인 7Fh + 01h에서는 두 규칙이 같은 답(OF = 1)을 내기 때문이다. 하지만 FFh + 01h에서는 CF = 1이고 결과 00h의 맨 윗자리 비트가 0이라, 이 규칙은 OF = 1을 낸다. 실제로는 −1 + 1 = 0이라 넘치지 않았고 OF = 0이다. 맞는 규칙은 “맨 윗자리 비트로 들어온 올림 XOR 맨 윗자리 비트에서 나간 올림”이다. 위 세로셈에서 FFh + 01h는 들어온 올림도 1, 나간 올림도 1이라 OF = 0이 나온다. 확인하는 법: 8비트 덧셈 65,536쌍을 모두 따져 보면 틀린 규칙은 절반인 32,768쌍에서 어긋나고, 맞는 규칙은 한 쌍도 어긋나지 않는다³.

확인 문제

C1 제로, 부호, 올림, 넘침 플래그가 각각 언제 켜지는지 쓰라. 넷 가운데 “부호 없는 수”와 “부호 있는 수”라는 말이 꼭 들어가야 하는 둘은 무엇인가?

답: ZF: 결과가 0. SF: 결과의 맨 윗자리 비트가 1(음수). CF: 부호 없는 수로 볼 때 결과가 범위 밖. OF: 부호 있는 수로 볼 때 결과가 범위 밖. 해석을 밝혀야 하는 둘은 CF와 OF다.
이유: “넘쳤다”는 말은 어느 범위를 기준으로 하느냐에 따라 달라진다. 8비트에서 CF의 범위는 0~255, OF의 범위는 −128~127이다.

C2 다음을 차례로 실행한다. 표시한 줄마다 AL과 ZF, SF, CF, OF를 쓰라. mov al,0F0h / add al,20h (가) / sub al,11h (나) / add al,1 (다) / mov al,90h (라) / sub al,20h (마)

답: (가) AL = 10h, ZF 0, SF 0, CF 1, OF 0. (나) AL = FFh, ZF 0, SF 1, CF 1, OF 0. (다) AL = 00h, ZF 1, SF 0, CF 1, OF 0. (라) AL = 90h, 플래그는 (다) 그대로(ZF 1, SF 0, CF 1, OF 0). (마) AL = 70h, ZF 0, SF 0, CF 0, OF 1.
이유: (가) F0h + 20h = 110h. 부호 없이 240 + 32 = 272로 범위 밖, 부호 있게 −16 + 32 = 16으로 범위 안. (나) 10h − 11h는 16 − 17이라 빌림이 생긴다. (다) FFh + 1 = 100h. (라) MOV는 플래그를 바꾸지 않는다. 여기서 ZF를 0으로 답하기 쉽다. (마) 90h − 20h = 70h. 부호 없이 144 − 32 = 112로 범위 안, 부호 있게 −112 − 32 = −144로 범위 밖.

C3 CPU가 덧셈 한 번마다 CF와 OF를 둘 다 계산해 두는 이유를 쓰라.

답: CPU는 피연산자가 부호 있는 수인지 없는 수인지 구별하지 못한다. 같은 비트 계산이 한 해석에서는 넘치고 다른 해석에서는 안 넘칠 수 있으므로 두 해석의 판정을 모두 남기고, 프로그래머가 자기 해석에 맞는 쪽을 읽게 한다.

C4 “부호가 다른 두 수를 더하면 넘침 플래그는 절대 켜지지 않는다”의 근거를 대라.

답: 음수 \(\hat a\)와 0 이상인 \(\hat b\)를 더한 값은 \(\hat a\) 이상 \(\hat b\) 이하다. 두 수가 범위 안이므로 그 사이에 있는 합도 범위 안이다.
이유: 넘침은 참값이 범위 밖으로 나가는 것인데, 반대 방향의 두 수는 서로를 범위 안쪽으로 끌어당긴다. 회로로 보면 맨 윗자리에 1이 하나뿐이라 들어온 올림과 나간 올림이 같아진다.

C5 “넘침 플래그 = 올림 플래그 XOR 결과의 맨 윗자리 비트”가 틀렸음을 보이는 8비트 덧셈을 하나 들고, 맞는 규칙을 쓰라.

답: FFh + 01h. CF = 1, 결과 00h의 맨 윗자리 비트 0이라 규칙은 OF = 1을 내지만, −1 + 1 = 0이라 실제 OF는 0이다. 맞는 규칙은 “맨 윗자리 비트로 들어온 올림 XOR 맨 윗자리 비트에서 나간 올림”이다.
이유: 이 덧셈에서는 들어온 올림도 1, 나간 올림도 1이라 XOR이 0이다. 틀린 규칙은 65,536쌍 가운데 절반에서 어긋난다.

증명은 단계별로 점검했고, 8비트 ADD·SUB 65,536쌍 전수와 16비트 표본에서 세 정의가 일치하는 것을 파이썬 흉내로 확인했다. 실제 CPU나 어셈블러로 돌린 결과가 아니다. ↩ ↩² ↩³
비트를 뒤집은 수와 1을 함께 더하는 것으로 계산하면 65,536쌍 전부에서 맞는다(검증 코드). ↩
값은 파이썬 흉내로 확인했다. ↩ ↩² ↩³
Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 2의 INC, DEC, NEG 항목에 있다. 흉내기는 이 규칙대로 만들었고, INC·DEC의 나머지 플래그가 ADD 1·SUB 1과 같은지를 8비트 전수로 확인했다. ↩