SHPC 02 - Binary Representations

Signed or Unsigned Binary Numbers

Unsigned Binary Numbers

• Binary number로 0이나 positive value를 나타낸다.
• 나타낼 수 있는 x의 값 범위는 다음과 같음 $0\le x\le 2^n-1$

Signed Binary Numbers

• 0을 포함하여 negative value, positive value를 나타낸다.
• 나타낼 수 있는 x값 범위는 표현법에 따라 다름
• Signed magnitude representation
  • MSB를 sign bit로 쓰고, 나머지 bit들은 magnitude를 나타내게끔 하는 것
  • 나타낼 수 있는 x의 값 범위는 다음과 같음 (+0, -0 포함)$-(2^{n-1}-1)\le x\le 2^{n-1}-1$
• 1’s complement representation
  • Radix complements 표현법
  • r=2 일때 (r-1)‘s complement를 쓰는 것
  • 나타낼 수 있는 x의 값 범위는 다음과 같음 (+0, -0 포함)$-(2^{n-1}-1)\le x\le 2^{n-1}-1$
• 2’s complement representation
  • Radix complements 표현법
  • r=2 일때 r’s complement를 쓰는 것
  • 대부분의 컴퓨터 시스템에서 사용
  • 나타낼 수 있는 x의 값 범위는 다음과 같음 (0이 하나)$-2^{n-1}\le x\le 2^{n-1}-1$

Radix Complements

두가지 종류가 있다.

r’s Complements

$$\bar{x}=\{\begin{array}{ll}{r}^n-x,& x\ne 0\\ 0,& x=0\end{array}$$

• $\bar{x}$는 $x$의 보수표현
• $x=0$ 케이스는 오버플로우가 나서 붙여주는 것, 실제론 carry를 무시하고 $x\ne 0$ 케이스와 같다고 생각하면 된다.

활용

• 2’s Complements는 이 표현법을 이용해 이진수를 2’s complement 형태로 나타낸 것을 의미 (r=2)

(r-1)‘s Complements

$$x^{\prime }=(r^n-1)-x$$

활용

• 1’s Complement는 이 표현법을 이용해 이진수를 (2-1)‘s complement 형태로 나타내는 것을 의미 (r=2)

1’s Complements vs 2’s Complements

	1’s Complements	2’s Complements
표현법	$x^{\prime }=(2^n-1)-x$	$\bar{x}=\{\begin{array}{ll}{2}^n-x,& x\ne 0\\ 0,& x=0\end{array}$
표현 범위	$2^{n-1}-1$ ~ $-2^{n-1}+1$ (n=3, 011~110)	$2^{n-1}-1$ ~ $-2^{n-1}$ (n=3, 011 ~ 100)
장점	MSB를 sign bit로 쓸 수 있다 음수표현을 찾기 쉽다 (bit 역전하면 됨)	MSB를 sign bit로 쓸 수 있다 0이 두개 생기지 않아 간단하다 Unsigned integer와 arithmetic hardware를 공유할 수 있다
단점	0이 두개 생긴다 - 0000 (+0) - 1111 (-0)

예시: n=3

1’s Complements

-3	100
-2	101
-1	110
0	111
0	000
1	001
2	010
3	011

2’s Complements

-4	100
-3	101
-2	110
-1	111
0	000
1	001
2	010
3	011

Operations on Binary Integers

Note

Modular arithmetic == Euclidean division을 이용했을 때 나머지를 구하는 연산

• Euclidean division은 나머지가 양수라는 특징이 있다. (e.g. -7 % 3 → Q: -3, R: 1)
• Modular arithmetic은 congruence relation (합동관계)를 만족시킨다.

Logical operations

• Bit-wise NOT, AND, OR, NOR, NAND, XOR, XNOR

Shift operations

• $x>>m$ shifts the 𝑛-bit binary number 𝑥 to the right by 𝑚 bits
• $x<<m$ shifts the 𝑛-bit binary number 𝑥 to the left by 𝑚 bits

Logical shift

Representation : $>{>}_L,<{<}_L$

Arithmetic shift

Representations : $>{>}_A,<{<}_A$

Shift operations of C

• Supports right shift and left shift
• C99 standard does not define the right shift for negative numbers
  • 정의되어 있지 않기 때문에 컴파일러가 정의하는 방식(구현)에 따라 결과가 달라진다.
  • Logical, arithmetic 모두에 해당한다.

Addition of Binary Integers

Unsigned

$$\begin{array}{rl}x+y& =(x+y)\mathrm{mod}{2}^n\\ & =\{\begin{array}{ll}x+y,& 0\le x+y\le 2^n\\ x+y-2^n,& 2^n\le x+y\le 2^{n+1}-2(overflow)\end{array}\end{array}$$

Signed

$$x+y=\{\begin{array}{ll}x+y-2^n,& 2^{n-1}\le x+y(overflow)\\ x+y,& -2^{n-1}\le x+y<2^{n-1}\\ x+y+2^n,& x+y<-2^{n-1}(underflow)\end{array}$$

Addition Hardware

Half Adder

• 두 개의 비트 $x,y$를 받아 덧셈 결과 $s$와 carry $c$를 리턴하는 회로

Full Adder

• 두 개의 비트 $x,y$와 $c_{in}$을 받아 덧셈 결과 $s$와 carry $c$를 리턴하는 회로
• 2개의 Half Adder와 1개의 OR 게이트를 이용해 만들 수 있다

Adder for Unsigned Numbers

Adder for 2’s Complement Representation

• Unsigned 버전에서 만들기 쉽다

• Overflow detection이 다르다

  • 부호 비트로 들어오는 캐리와 나가는 캐리가 다른 경우 overflow/underflow 발생
  • 예를 들어 4비트 덧셈으로 다음 두 케이스를 생각할 수 있음
    1. 양수 두 개를 더하는 경우 : 6 + 5

         0110  (6)
       + 0101  (5)
         ----
         1011  (-5) → overflow 발생!
       

    • 들어오는 캐리가 1인데, 나가는 캐리가 0이다
    2. 음수 두 개를 더하는 경우 : -4 + (-5)

         1100  (-4)
       + 1011  (-5)
         ----
         0111  (7) → overflow 발생!
       

    • 들어오는 캐리가 0인데, 나가는 캐리가 1이다
  • 간단히 생각하면 overflow의 조건을 다음과 같이 생각할 수 있는데,
    1. 부호 비트가 같을 때 (0+0, 1+1)
       1. 부호 비트가 둘 다 0
       2. 부호 비트가 둘 다 1
    2. 부호 비트가 바뀌었을 때
    • 1-1)와 2)를 만족하는 케이스를 생각해 보면 들어오는 캐리는 1이어야 한다. 이 때 나가는 캐리는 0일 것이다.
    • 반대로 1-2)와 2)를 만족하는 케이스를 생각해 보면 들어오는 캐리는 0이어야 한다. 이 때 나가는 캐리는 1일 것이다.
    • 따라서 overflow가 되는 상황은 들어오는 캐리와 나가는 캐리가 다른 상황밖에 없다.

Subtraction Hardware

Half subtractor & Full subtractor

Half Adder, Full adder에서 borrow 계산하는 쪽만 바뀐 형태

• Borrow는 x가 0, y가 1인 상황에서 발생하므로 x쪽에 NOT을 붙여준다

Subtractor for Unsigned integer

Subtractor for 2’s Complement

• Adder를 재활용한다
  • y를 -(y)로 바꾸어 덧셈계산
• 2’s Complement의 특성상, bit를 반전(XOR 1)시킨 후 $c_{in}$에 1을 넣으면 된다

Multiplication & Division

Multiplication은 Adder를 활용해 구현 가능하며, Addition과 성능적으로 비슷하다. Division 성능이 느린 편이다. Division은 인간이 하는 것과 비슷하게 몫을 큰 수로 두고 빼려고 시도하고 안되면 좀 더 작은 수로 내려가는 등의 과정으로 계산한다.