[5-1] Overflow / Multiplication

주어진 범위를 넘어가는 것이 overflow

 

* addition의 경우

- 양수와 음수 덧셈 : no overflow (범위가 벗어나지 않음. 0으로 가까워짐)

- 양수와 양수 덧셈 : Overflow if result sign is 1 (부호가 -가 될 가능성 있음)

- 음수와 음수 덧셈 : Overflow if result sign is 0 (부호가 +가 될 가능성 있음)

 

subtraction의 경우

- 양수 양수, 음수 음수 뺄셈 : no overflow

- 양수-음수 뺄셈 : Overflow if result sign is 0 (부호가 +가 될 가능성 있음)

- 음수-양수 뺄셈 : Overflow if result sign is 1 (부호가 -가 될 가능성 있음)

 

* Dealing With Overflow

- C는 overflow 무시 -> 잘 알고 써야 함

- 다른 언어는 에러나 exception, interrupt 발생시키기도 함.

 

* Multiplication

- 첫 번째 숫자를 multiplicand, 두 번째 숫자를 multiplier로 둔다.

- multiplicand는 왼쪽으로 shifting하고, multiplier는 오른쪽으로 shifting 한다.

- 이때, multiplier의 맨 끝 글자가 1이면 multiplicand를 product에 더하고, 0이면 더하지 않는다.

=> 마지막에 모든 product를 더하는 방식으로 Multiplication 구현

** 32bit x 32bit 연산은 총 32번의 연산 필요

 

* Optimized Multiplier

- 처음 Multiplication에 비해 Multiplicand가 32bit로 줄고, 64-bit ALU가 32bit로 줄었으며 Multiplier Shift right가 없어짐.

- Product를 절반으로 나눈다. (왼쪽은 32bit는 Multiplicand를 적고, 뒤에는 Multiplier를 적는다)

- Multiplier의 맨 끝 값이 1이면 왼쪽 값에 Multiplicand를 더해서 갱신한다. (0000이었을 경우 1000으로 갱신)

- 0일 경우 Multiplicand, Multiplier 모두 오른쪽으로 한 칸 shifting 한다.

- 마지막 값은 Multiplier가 0이 되었을 때의 Product 값이 최종 결과가 된다.

 

** 주의 **

- Product 전체가 shifting 되는 것이다. 왼쪽 오른쪽을 개별적으로 보면 안 됨. 즉 1001 0001 (8bit로 가정)일 때 오른쪽으로 shifting하면 0100 1000이 된다.

 

=> Multiplication은 shifting에 비해 너무 느리다. shifting으로 대체되는 경우 Multiplication을 쓰지 말자.