2.3 정수의 산술연산

2.3은 비부호형 (부호가 없다는뜻)

2의 보수(그 보수 아님)형의 덧셈과 곱셈

그리고 오버플로우에 대해서다

2.3.1 비부호형 덧셈

비트로 수를 표현하는데엔 한계가 있다

예시로, 4비트의 경우 0~15로 그 이상은 표현이 불가하다

( [0110] = 6 ) + ( [1100] = 12 )
에서
( [10010] = 18 )

이러면 5비트가 되버리기에 4비트까지 쳐낸다

( [0010] = 2 ) 이따구로 말이다

느낌이 오지 않는가?

오버플로우시 초과한만큼 맨 처음부터 다시 올라오는 거다

|----|--------------------------------| ----- |
0    2                              16(0)     18

16을 넘친 2는 다시 처음으로 돌아가는 느낌으로

여기서 법칙도 하나 나온다

x + y 가 x나 y 보다 작다면 오버플로우가 발생!
이라는 상식 말이다

추가로 역원도 알아보자

더하면 0이 되는 역원이다 ㅇㅇ

싯팔 양수 2개 더했는데 왜 역원이냐?
그야 오버플로우니까…

w비트를 사용할 경우 $x$의 역원은

$2^w - x$ 이다

둘을 딱 더하면 $2^w$가 되어버려서 오버플로우나
0이 된다

w비트는 $2^w -1$ 까지만 표현가능하니…

이제 다음으로 넘어가자 이해못했으면 다시 읽거나 책 참고하고 ㅇㅇ

2.3.2 2의 보수의 덧셈

2의 보수가 뭔지모르면 앞에 다시 보고 오자

csapp 2.1 ~ 2.2

이번엔 부호가 있는 수의 덧셈이다

의외로 음양 상관없이 더하고 절삭하면 된다

예시) x=[10100] , y=[10001] = 00101

예시2) x=[10111] , y=[01000] = 11111

그리고 이곳에서 역원은 졸라 쉽다

음양이 있으니 걍 (-) 부호 붙이면 된다
3의 역원 -3, 18 역원 -18 이런식 ㅇㅇ;;

※주의※
단, [1000. . . ] 과 같은
2의 보수에서 가장작은 수(TMin이라고 함)의 경우는
스스로가 역원이다

[1000. . .] + [1000. . .] = [0000. . .]
절삭 당하니 말이다

2.3.3 2의 보수에서의 비트반전

비트반전 법칙 인데
별 거 없다

마이너스 부호 붙이기,
TMin 역원 = TMin
이딴거니 넘어가자

2.3.4 비부호형 곱셈

덧셈도 오버플로우 되는데
곱셈은 오버플로우 3바퀴 돌고도 남는다

2진수에서의 곱셈은 10진수랑 같다

         0110 <- 6(10)
         0101 <- 5(10)
-----------------------
         0110
        0000  <-1번째 비트가 0이니까
       0110
      0000 <- 3번째 비트가 0이니까
------------------------
        11110 <- 30(10)

걍 10진수 변환하고 곱하고 2진수로 바꿔도 좋다

곱하고 난 뒤에는 똑같이 절삭하면 끝이다

전문가처럼 말하면 $mod 2^w 모듈러$ 연산 했다고 한다

2.3.5 2의 보수 곱셈

비부호형이랑 똑같다

그치만…

MSB(부호 정하는 비트) 때문에 결과값이 조금 다르다

방법은 똑같이 w비트 남기고 절삭이지만

해석 방법이 다르니 이것만 유의하자

2.3.6 상수를 이용한 곱셈

상수 곱셈을 시프트 연산으로 하는 방법이다

시프트 연산이 뭔데? ㅅㅂ

그건 앞에 있으니 다시 보도록 ㅇㅇ

csapp 2.1 ~ 2.2

그래서 시프트 연산이랑 무슨상관이냐?

그건…

$x * 2^k$ 일때 $0 <= k < w$ 인 $k$에 대해서
$(x « k)$로 표현 가능하다
반대로 $k<0$ 일때엔$(x»|k|)$로 가능하다

설명으로 보면 뭔 개소리지 싶으니

예시를 알려주겠다

$x*14$를 시프트 연산으로 표현하면

$14=2^3+2^2+2^1$ 이다 따라서

$x*(2^3+2^2+2^1)$

$=x2^3+x2^2+x*2^1$

$=(x«3)+(x«2)+(x«1)$

이렇게다.
쉬프트 연산 3번 + 덧셈 2번으로 총 5번의 연산이 시행된다

이게 마음에 안들면 다른 것도 있다

$14=16-2=2^4-2^1$

$x*(2^4-2^1)$

$=x2^4-x2^1$

$=(x«4)-(x«1)$

이렇게 하면
쉬프트 연산 2번 + 뺄셈 1번으로 연산횟수를 3번으로 줄일 수 있다

2.3.7 2의 제곱으로 나눗셈

나눗셈, like jot

상당히 complicate하고

likely jot이다

우리는 정수를 다루니 소숫점은 걍 버리면 되는게 위안이다

그치만…

버리는 법도 배워야 한다…

like 분리수거

$int(3.9) = 3$
양수는 이런식으로 하면 문제없다

양수가 문제 없다는 건 음수가 문제라는 거다
$int(-3.2) = -3$

어라?
이새끼는 양수랑 다르게 숫자가 커져버렸다…

컴퓨터에서 중요한건 일관성이다

이를 챙겨주기 위해 우린 음수에겐 내림이 아닌 올림을 해줘야 한다

$int(-3.2) = -4$

그리고 이를 컴퓨터에서 표현하기 위해선
bias(보정값이라는 뜻)를 사용해야 한다

어떻게 bias를 넣는지는 예시로 알아보자
미리 말해보자면 걍 1 더하는 느낌이다

ex) -12340 = [1110/1111/1100/1100]
              ↑ 이자식을 2^8로 나눠보자

나누는 시프트 연산이니 우측으로 8칸 이동하면 된다
그리하면...

오른쪽 8비트([1100/1100])은 나머지가 되고
남은 왼쪽 부분([1100/1111])은 몫이 된다


🐸👍
(개구리가 따봉하는 그림)


절삭 이후엔 MSB값을 넣어주는 거 하면 된다

[ 1111 / 1111 / 1100 / 1111 ]
  1로 채운 곳 /   몫 부분

# 이렇게 되면 나머지 부분이 사라진다

그리고 나머지 부분에 1이 하나라도 존재했다면

bias(보정값이라는 뜻)을 더해줘야 한다

없어지는 비트의 길이가 k라 치면 bias는
2^k -1이 된다

요약하면
음수를 2^8로 나누고 싶으면 bias를 2^8-1로 정한뒤
더하고 시프팅으로 넘기면 된다

간단히 식으로 요약하자면
x<0이면 (x+(1«k)-1)»k, x>=0이면 (x»k)

2.3.8 산술연산에 대한 마지막 고찰

컴퓨터의 워드길이는 유한해서 넘으면 오버플로우 난다
컴퓨터는 모듈러 연산이라는 형태로 오버플로우의 값을 표시
덧셈, 뺄셈, 곱셈 ,나눗셈은 unsigned 이건 signed이건 큰 차이 없으니 걍 값구하고 절삭
unsigned(비부호형)과 signed(부호형) 같이 연산안하게 조심
같이 연산? like jot이니 be careful 바란다. 독자 여러분.

2.4는 따로 다루겠다