Lecture 03: Bits, Bytes, and Integers (cont.)

Unsigned Addition in C

• Operands : w bits
• True Sum : w + 1 bits
• Discard Carry : w bits

따라서 Unsigned int 두 수의 합은 (실제 두 수의 합 mod 2^w) 의 값과 같다

 

 

 

Two's Complement Addition

• 두 수의 합에서 discard를 하더라도 실제 값과 동일한 경우가 존재한다

• 두 음수의 합에서 negative overflow가 발생하기도 한다
• 두 양수의 합에서 positive overflow가 발생하기도 한다

 

정리

 

 

 

Unsigned Multiplication in C

• Operands : w bits
• True product : 2 * w bits
• Discard w bits : w bits

따라서 Unsigned int 두 수의 곱은 (실제 두 수의 곱 mod 2^w) 의 값과 같다

 

 

Signed Multiplication in C

• 넘어가버리는 bit는 모두 무시하므로 존재하는 bit 중에서 가장 좌측에 0이 오느냐 1이 오느냐에 따라 값의 부호가 달라지게 된다
• 따라서 양수인 두 수를 곱했을 때 양수가 나올 수도 있고, 음수가 나올 수도 있다

• 위의 사진과 같이 두 수를 unsigned로 변환한 뒤 곱셈을 한 값을 hex로 나타내고, 우측의 bit들만 남는다고 생각하면 계산이 쉬워진다

 

 

Power-of-2 Multiply with Shift

• u << k gives u * 2^k

 

 

Unsigned Power-of-2 Divide with Shift

• 오른쪽으로 shift하고 소수점은 버린다

Quiz. 음수를 divide with shift하게 되면?

Answer : 아래 그림과 같이 Arithmetic shift를 사용하는 머신에서는 실제 값도 반으로 나눠지는 것을 볼 수 있다

Quiz. 위의 그림에서 -3을 divide with shift 했는데 -1이 아닌 -2가 나온 이유는?

Answer : 내림을 하는 것이 원칙이기 때문이다. -1이라는 결과를 얻기 위해서는 아래 그림과 같이 bias를 통해 보정해줘야 한다

 

 

x -> -x로 만드는 방법

• 비트를 flip하고 1을 더해준다

 

 

Java에서는 logical shift와 arithmetic shift 연산자를 구분한다
- logical shift : >>>
- arithmetic shift : >>

 

 

 

Counting Down with Unsigned

• 오히려 unsigned의 underflow를 활용해서 만든 로직...

 

Q. What if cnt is signed and < 0?

A. i가 엄청 큰 수가 되어 for 문을 돌 것이다

 

 

 

Why Should I Use Unsigned?

Do Use When Performing Modular Arithmetic
- Multiprecision arithmetic

Do Use When Using Bits to Represent Sets
- Logical right shift, no sign extension

 

 

Word-Oriented Memory Organization

hex가 아닌 decimal number임에 주의

 

 

Byte Ordering

요즘은 대부분 Little Endian

byte are flipped betw big and little

 

 

 

예제 생각해보기

 

 

 

 

Integer C Puzzles

• 항상 참이라면 왜 항상 참인지, 거짓이라면 반례 제시하는 문제