2.3-Integer_Arithmetic

2개의 양수를 더했는데 결과값이 음수이거나,
x < y 와 x - y < 0 의 결과가 다른 등 종종 컴퓨터는 연산 결과가 상식적이지 않다.
이는 컴퓨터가 표현할 수 있는 수의 범위가 한정적인데서 오는 특징이다.
이러한 특징을 아는 것은 신뢰할 수 있는 코드를 짜는 기반이 된다.

2.3.1 Unsigned Addition

인 두 는 bit 로 표현 가능하다.
하지만, 이므로 그 합은 bit 로는 부족하며, bit 가 필요하다.
은 산수 연산의 결과값을 온전히 나타낼 수 없다는 의미이다.

Lisp 같은 일부 언어는 임의 size 의 산수 연산을 지원하지만,
보통의 언어는 고정된 size 에 대해 지원한다.

새로운 더하기 연산자로 를 정의한다.
이 연산자는 bit 에서 + 를 수행하며, 그 결과를 Unsigned 로 표현해준다.
이는 사실 더하기 연산 이후, 를 취하는 것과 같은 결과이다.
일 때, 로 같은 결과이다.

unsigned 와 int 간의 암시적 형변환을 이유로 허락되지 않은 kernel 데이터에 접근할 수도 있었다.

산수연산이 해당하는 범위 내로 결과가 나오지 않을 때, 라고 한다.

는 보다 작기 때문에, , 는 모두 0보다 작다.
따라서, 가 발생하면 다음이 성립한다.

은 을 이룬다.

Group 에서 교환조건(Commutative) 가 추가된 Group 이다.
Group은 어떤 집합이 특정 연산에 대해,

연산 결과가 해당 집합에 있음이 보장(Operation is Closed)
결합법칙이 성립 (Associativity)
항등원이 존재 (Identity element exist)
역원이 존재 (Inverse element exist)

가 성립하는 경우, 해당 연산에 대해 Group 이라고 칭한다.

이기 때문에 연산의 결과가 예상 범위 내임이 보장되고, 연산에 자유롭게 변형을 가할 수 있다.

Group이기 때문에 역원이 존재함이 보장되고 이를 로 정의한다.
이 때,

로 계산할 수 있다.

2.3.2 Two's Complement Addition

2의 보수에서는 이므로, 가 성립한다.
즉, bit가 필요할 수 있다.
2의 보수에서는 양극단, 즉 너무 작거나, 클 때의 연산을 잘 정의해야한다.

해당 연산에서 를 더하고 빼는것은 modulo 연산을 생각하면 유추해낼 수 있다.
너무 큰수에 대해서는 modulo 값이 동일한 채로 줄여야하므로 를 더하고 빼면 된다.

2의 보수 표현과 부호없는 정수의 표현 방법이 동일하기 때문에,
피연산자를 부호없는 정수 표현으로 바꿔서 더하기 연산을 실행하고, 다시 2의 보수 표현으로 바꿔도 동일한 값을 얻을 수 있다. 수식으로 정리하면 다음과 같다.

라는 점과 가 단순히 라는 점을 감안하면,

2의 보수법에서는 OverFlow 는

일때, Positive OverFlow
일때, Negative OverFlow

	int tadd_ok(int x, int y) {
		int sum = x + y;
		return (sum - x == y) && (sum - y == x);
	}

위의 예제는 항상 1 을 반환한다.
2의 보수 덧셈은 아벨군이기 때문에, 더하기 연산에 대해 닫혀있다.
따라서, 덧셈의 결과로는 OverFlow 를 감지할 수 없다. 위의 x, y, sum 의 상태를 판단해야한다.

	int tsub_ok(int x, int y) {
		return tadd_ok(x, -y);	
	}

이 함수는 일 때, 발생한다. 의 값은 가능한 양수 범위를 벗어난다.
()
따라서 에는 그래도 가 저장된다.

2.3.3 Two's Complement Negation

에 대하여,

에 대하여, 이므로, 가 발생하므로,
이다. 그 외 에 대하여, 이다.

find rightmost 1.
일 때, 을 찾을 수 있다.
이 때, 이다.

2.3.4 Unsigned Multiplication

원래는 인 두 에 대해, 곱하기는 0에서 까지 가능하다.
즉, 이론상 bit 가 필요하다.
C언어에서는 하위 bit 를 알려주는 곱하기 연산이 있다. 이를 로 정의한다.
이는 사실 곱한 값에 를 취한것과 같다.

2.3.5 Two's complement Multiplication

원래는 인 두 에 대해, 곱하기는 에서 까지 가능하다.
즉, 이론상 bit 가 필요하다.
C언어에서는 하위 bit 를 알려주는 곱하기 연산이 있다. 이를 로 정의한다.
이는 사실 곱한 값에 를 취하고, Unsigned 에서 2의 보수로 변환한 값과 같다.

사실, Unsigned 에서의 곱하기와 2의 보수에서의 곱하기는 동일하게 작동한다.
양쪽 모두, 방식을 이용한다.
간단하게, 곱셈 연산의 오른쪽 숫자의 비트패턴을 살펴보며, 0이면 패스, 1이면 왼쪽 숫자를 그래도 더하고, 오른쪽 숫자가 왼쪽으로 1 shift 한다.

그리고, Unsigned 와 2의 보수법 모두 같은 패턴을 다르게 해석하는 해석의 차이이기 때문에,
같은 비트를 같은 연산으로 처리하므로, 해석법만 맞추면 동일한 값이 나온다.
즉, Unsigned * Unsigned 의 결과값을 bit 로 표현한 것은 signed * signed 을 bit 로 표현한 것과 같다.

2.3.6 Multiplying by Constants

곱하기에 대한 컴파일러 최적화를 위해 상수에 대한 곱을 처리한 다음, 남은 부분을 더하는 것이다.
이를 위해 먼저 꼴의 상수를 먼저 살펴보고, 임의의 상수로 넘어간다.

부호 없는 정수 표현에서 에 대해,
, bit 부호없는 정수 표현으로 는 다음과 같다.

이 오른쪽에서 개 추가되었다.
성립하는 이유는 이 추가되면서, 가중치가 정확히 배가 되며, 0으로 채웠기 때문에 연산에서 무시되기 때문이다.

이 때, bit 로 고정된 경우, 일부 정보의 손실이 발생할 수 있지만,
shift 연산도 동일하므로 두 과정을 동일하게 볼 수 있다.
즉,

이다.

2의 보수법에서도 bit-level 연산은 동일하므로,

이다.
두 경우 모두, OverFlow 가 발생할 수 있다는 점을 조심해야한다.

컴파일러는 최적화를 위해, 곱셈을 shifting and adding 으로 처리한다.
예를 들어, 이다.
또는 반대로, 로 표현할 수 있다.

에 대해, 이라고 하고
중 하나가 의 구간을 가질 때, 다음의 2가지 방법으로 계산할 수 있다.

위의 2가지 방법과 를 그대로 수행하는 것, 총 3가지 방법 중 가장 빠른 방법은
instruction 의 상대적인 속도 즉, machine-dependant 이기 때문에 machine 마다 다르다.
보통은 적은 수의 연산으로 가능할 때 위의 최적화가 발생한다.

	(x << (n + 1)) - (x << m)
	해당 연산 방법에 대해, n 이 MSB 이면 어떻게 되는가?

의 결과는 이다. 모든 비트 정보가 사라지기 때문이다.
따라서, 이다.

2.3.7 Dividing by Power of 2

나누기는 곱셉보다도 훨씬 느리다. 이번에는 오른쪽 shift 를 통해 해결할 수 있다.
logical, arithmetic 은 부호 없는 표현, 부호 있는 표현 각각에 대해 처리해준다.

정수 나눗셈은 항상 한다.
이를 명확히 하기 위해 표기를 정리한다.

에 대해,
양수 결과에 대해서는 round down(),
음수 결과에 대해서는 round up() 이다.

부호 없는 표현에 대해

shifting 을 이용하는 것은 자연스럽다.

2.1.9 Shift Operations in C

<< 은 비트를 왼쪽으로 밀면서, 새로운 공간을 0으로 채운다.
ex) 이 된다.

그러나, >> 의 경우는 조금 다르게 작동한다. 크게, , 2가지가 있다.
: 새로운 공간을 으로 채운다.
: 새로운 공간을 MSB 와 동일한 값으로 채운다. 이는 signed int 에서 유용하다.

C언어 표준은 Logical, Arithmetic 을 특정하지 않는다.
단, 대부분의 컴파일러가 signed data 에 대해 Arithmetic 을 사용하고, 개발자도 그렇게 받아들인다.
하지만, unsigned data 에 대해서는 Logical 을 사용해야만 한다.
Java 에서는 >> 을 Arithmetic 으로, >>> 을 Logical 로 이용한다.

C언어에서는 다음이 성립한다.

이다.
이 때,

이다.
따라서, 이다.

또한, shift 의 결과는
이다.

2의 보수법 즉, 부호가 있는 정수에 대한 나눗셈은 조금 더 복잡하다.
우선, 음수에 대해 부호 때문에 MSB 가 보존되는 right shift 가 일어나야한다.

2의 보수법으로 표현된 값 와, 부호 없는 정수 에 대해,

양수에 대해서는 MSB 가 0이므로, 가 동일하게 작동한다.

2의 보수에서
이다.
이 때,

이다.
따라서, 이다.
하지만, 과 다르게, 연산을 사용하므로,
shift 의 결과는 이다.

2의 보수법의 음수에 대해서는 이 필요하다.
이는 C언어에서 다음으로 표현된다.

은 번째 bit는 0, 이하의 bit에 대해서는 모두 1인 bit 패턴이다.
이를 더하는 것은 이하에서 이 있을 때, 올림을 해준다는 의미이다. 이는 floor 와 의미가 일치한다.

또는 다음의 수식으로 이해할 수 있다.

이는 다음으로 증명가능하다.

를 대입하면, 정확히 우리가 원하는 연산을 해준다.

이러한 분석을 통해, 2의 보수 표현에 대해 을 사용하는 machine 의 경우,

(x < 0 ? x + (1 << k) - 1: x) >> k = x/2^k

이다.

	 function returns x/16 for integer x.
	"No" Division, modulus, multiplication, any conditional, any comparison, any loop.
	x is type int with 32bits, use two's complements. And right shift are performed "arithmetics."

	int div16(int x) {
		int bias = (x >> 31) & 0xF;
		return (x + bias) >> 4;
	}

중요한 포인트는 양수에 대해서는 bias = 0 이며, 음수에 대해서는 16bit의 111...1 이다.
이는 양수, 음수가 MSB 에 의해 판단되며, arithmetic right shift 가 MSB 를 복사한다는 점을 이용한다.

2의 보수에서 꼴의 곱셈을 위해, 혹은 을 사용한다는 점은,
대부분의 machine 에서 양쪽 연산을 모두 지원하는 이유 중 하나일 것이다.

하지만, 나눗셈에 대해서는 일반적인 방법이 없다.

	# define M
	#define N

	int arith(int x, int y) {
		int result = 0;
		result = x*M + y/N;
		return result;
	}
	
	// compile and deCompile...
	
	int optarith(int x, int y) {
		int t = x;
		x <<= 5;
		x -= t;
		if(y < 0) y += 7;
		y << 3; /* arithmetic shift */
		return x + y;
	}

Answer:
해당 과정을 정리하면, 이며 이는 곱하기에 대한 최적화로 와 같다.
는 이므로 2의 보수 나눗셈으로 8에 대해 나누고 있다.

2.3.8 Final Thoughts on Integer Arithmetic

"정수" 연산은 모듈러 연산의 일종이다.
한정된 의 사이즈는 가능한 값의 범위를 제한한다. 또한 이 때문에 가 발생할 수 있다.
2의 보수법은 부호 없는 정수와 똑같은 bit-level 연산을 지원해주는 방법이다.
bit-level 연산에서는 같거나 거의 비슷했다.

C언어의 미묘한 행동은 예상치 못한 결과를 낳는다.