요약

0과 1이 줄지어 앉은 칸에서 모두를 한쪽으로 한 칸씩 옮겨 앉히는 명령이다. 끝에서 밀려난 하나는 따로 마련된 보관 칸 하나에 잠깐 남고, 반대쪽에 생긴 빈자리는 정해진 값으로 채운다. 십진수 끝에 0을 붙이면 열 배가 되듯, 2진수를 왼쪽으로 한 칸 밀면 두 배, 오른쪽으로 한 칸 밀면 절반이 된다. 곱셈·나눗셈을 자리 옮기기 한 번으로 끝내지만, 밀려난 자리는 사라지므로 결과가 칸 수를 넘으면 틀린 값이 남는다.

예시로 보기

5에 4를 곱하고 싶다. 곱하는 수가 2, 4, 8처럼 2를 여러 번 곱한 수라면 곱셈을 하지 않고 자리만 옮겨도 된다. 이것을 빠른 곱셈이라고 부른다.

십진수 37의 끝에 0을 붙이면 370, 열 배다. 2진수도 같다. 5는 00000101이다. 전체를 왼쪽으로 한 칸 밀고 오른쪽 끝에 0을 채우면 00001010, 10이다.

mov dl,5        ; DL = 00000101b = 5
shl dl,1        ; DL = 00001010b = 10

        CF     7 6 5 4 3 2 1 0
밀기 전  ?     [0 0 0 0 0 1 0 1]   = 5
              ↙ ↙ ↙ ↙ ↙ ↙ ↙ ↙ ← 0
밀고 난 뒤 0   [0 0 0 0 1 0 1 0]   = 10

맨 왼쪽(7번) 칸에서 밀려난 비트는 버려지지 않고 올림 플래그 CF에 들어간다. 오른쪽 끝 빈칸에는 0이 들어온다.

두 칸 밀면 네 배다. mov dl,5 다음 shl dl,2를 하면 DL = 20이다.

검증: 본문의 모든 값과 추적 표의 답(35h, A8h, C6h, F8h), 8비트 256가지 값 × 0~8칸 전부에서 아래 세 식 — 37_shift-instructions_verify.py (실제 어셈블러가 아니라 파이썬 흉내로 확인)

정의

시프트 명령은 넷이다.

명령 이름 미는 쪽 빈칸에 채우는 값 CF에 들어가는 것
SHL 왼쪽 시프트 왼쪽 맨 아래 칸에 0 맨 위 칸에서 나간 비트
SAL 왼쪽 산술 시프트 왼쪽 SHL과 완전히 같다 같다
SHR 오른쪽 시프트 오른쪽 맨 위 칸에 0 맨 아래 칸에서 나간 비트
SAR 오른쪽 산술 시프트 오른쪽 맨 위 칸에 원래 부호 비트 맨 아래 칸에서 나간 비트

빈칸을 0으로 채우는 것을 논리 시프트, 부호 비트를 복사해 채우는 것을 산술 시프트라고 부른다. 둘의 차이는 논리 시프트와 산술 시프트 비교에서 따로 다룬다.

쓰는 꼴. 첫 피연산자는 밀 대상(레지스터나 메모리), 둘째는 몇 칸 밀지다. 칸 수는 8비트 즉시값이나 CL 레지스터로만 준다. 회전 명령도 모두 같은 꼴이다.

SHL reg,imm8
SHL mem,imm8
SHL reg,CL
SHL mem,CL

곱셈·나눗셈과의 관계. 8비트 값 \(x\)를 \(n\)칸 밀 때(\(0 \le n \le 8\)) 다음이 맞다.

  • 왼쪽으로 \(n\)칸 밀면 \(2^n\)을 곱한 것이다. 단 8비트를 넘는 윗자리는 잘린다.
  • 부호 없는 수를 SHR로 \(n\)칸 밀면 \(2^n\)으로 나눈 몫이다.
  • 부호 있는 수를 SAR로 \(n\)칸 밀면 \(2^n\)으로 나누고 내린 값이다.

기호로 쓰면, \(x\)를 부호 없는 수로 읽은 값을 \(u\), 부호 있는 수로 읽은 값을 \(s\)라 할 때

\[\mathrm{SHL}(x, n) = (u \cdot 2^n) \bmod 2^8, \qquad \mathrm{SHR}(x, n) = \left\lfloor \frac{u}{2^n} \right\rfloor, \qquad \mathrm{SAR}(x, n) = \left\lfloor \frac{s}{2^n} \right\rfloor\]

이다. \(\bmod 2^8\)은 256으로 나눈 나머지, 즉 아래 8비트만 남긴다는 뜻이다. \(\lfloor\ \rfloor\)는 소수점 아래를 버리고 작은 쪽 정수로 내린다는 뜻이다. 세 식은 256가지 값 전부에서 확인했다1.

예제

오른쪽으로 밀어 나누기. 80을 한 칸 밀면 40, 거기서 두 칸 더 밀면 10이다.

mov dl,80
shr dl,1        ; DL = 40
shr dl,2        ; DL = 10

음수는 SAR로. −80(10110000)을 SAR로 밀면 부호가 그대로다.

mov dl,-80
sar dl,1        ; DL = -40
sar dl,2        ; DL = -10

한 줄씩 따라가기. AL에 값을 넣고 두 번씩 밀면서 AL과 CF가 어떻게 바뀌는지 따라간다.

명령 밀기 전 AL 밀고 난 AL 16진 CF
mov al,6Bh   01101011 6Bh  
shr al,1 01101011 00110101 35h 1
shl al,3 00110101 10101000 A8h 1
mov al,8Ch   10001100 8Ch  
sar al,1 10001100 11000110 C6h 0
sar al,3 11000110 11111000 F8h 1

여러 칸을 밀면 CF에는 마지막으로 밀려난 비트 하나만 남는다. shl al,3에서는 0, 0, 1이 차례로 나갔고 마지막 1이 CF다1.

넘치면 틀린다. 200(11001000)을 왼쪽으로 한 칸 밀면 400이 되어야 하는데 8비트에는 255까지만 들어간다. 맨 위의 1이 CF로 나가고 남는 값은 10010000 = 144다. 400 − 256 = 144와 맞는다1.

활용

  • 2를 여러 번 곱한 수로 곱하거나 나눌 때 곱셈·나눗셈 명령 대신 쓴다. 다른 수도 쪼개면 된다. 36 = 32 + 4이므로 x에 36을 곱한 값은 x를 5칸 민 것과 2칸 민 것을 더한 값이다1.
  • 비트 묶음 꺼내기: 원하는 비트를 맨 아래로 밀어 놓고 비트 논리 명령의 AND로 나머지를 지운다.
  • 흔한 실수 세 가지.
    • 음수에 SHR을 쓴다. −80에 shr dl,1을 하면 88이 나온다. 부호 있는 수는 SAR을 쓴다.
    • 왼쪽으로 밀어 넘친 것을 놓친다. 넘쳤는지는 CF(부호 없는 수)를 봐야 안다.
    • 칸 수를 EAX나 변수로 주려 한다. 칸 수는 즉시값이나 CL뿐이다.
  • Java의 <<, >>, >>>가 각각 SHL, SAR, SHR과 같은 일을 한다1. 비트 연산
  • 연습: 시프트와 회전 예제 사다리

연결

확인 문제

C1 SHL, SHR, SAR이 각각 빈칸을 무엇으로 채우고 CF에 무엇을 넣는지 쓰라. SAL은 무엇과 같은가?

답: SHL: 맨 아래 칸에 0, CF에는 맨 위에서 나간 비트. SHR: 맨 위 칸에 0, CF에는 맨 아래에서 나간 비트. SAR: 맨 위 칸에 원래 부호 비트, CF에는 맨 아래에서 나간 비트. SAL은 SHL과 같은 명령이다.

C2 mov al,3Ch 다음에 shl al,2, 이어서 shr al,3을 실행한다. 각 명령 뒤의 AL(16진)과 CF는?

답: shl al,2 뒤 AL = F0h, CF = 0. shr al,3 뒤 AL = 1Eh, CF = 0.
이유: 3Ch = 00111100. 왼쪽 두 칸: 11110000, 나간 비트는 0, 0. 오른쪽 세 칸: 00011110, 나간 비트는 0, 0, 0. 처음 값 3Ch(60)로 돌아오지 않는다. 60 × 4 = 240, 240 ÷ 8 = 30이다1.

C3 mov al,80h 다음 shl al,1을 하면 AL은 0이 된다. 128 × 2 = 256인데 왜 0인가? 이 일이 일어났다는 것을 프로그램은 어떻게 아는가?

답: 256은 2진수로 1 00000000, 9비트다. AL은 8칸뿐이라 맨 위의 1이 밀려나고 아래 8비트 00000000만 남는다. 밀려난 1은 CF에 들어가므로 CF = 1을 보고 안다.
이유: 왼쪽 시프트의 결과는 \((u \cdot 2^n) \bmod 2^8\)이다. 곱이 255 이하일 때만 곱셈과 같은 값이 남는다1.

C4 EAX에 든 부호 없는 수에 18을 곱한 값을 곱셈 명령 없이 EAX에 넣는 코드를 쓰라(EBX를 써도 된다).

답: 18 = 16 + 2다.

mov ebx,eax
shl eax,4       ; EAX × 16
shl ebx,1       ; EBX × 2
add eax,ebx     ; EAX × 18

이유: \(x \cdot 18 = x \cdot 2^4 + x \cdot 2^1\). \(x = 3\)이면 48 + 6 = 54다1.

  1. 모두 검증 줄의 파이썬 흉내로 확인했다. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 ↩8