wrap around는 엄청 쉽게 이해할 수 있는 내용인 거 같지만 Go를 공부하면서 처음 접한 이론?이라 단독 포스트를 하게 됐다.
이번에 공부하면서 처음 알게 된 것부터 wrap around까지 천천히 최대한 자세히 서술해보겠다.
원래 알고 있던 2진수를 조금 더 깊고 자세하게 알게 되는 계기가 됐는데 그중 msb와 lsb가 뭔지부터 설명하겠다.
- lsb [least significant bit]
bit의 맨 오른쪽에 있는 bit를 뜻하고 연산의 시작점이라 할 수 있다. - msb [most significant bit]
bit의 맨 왼쪽에 있는 bit를 뜻하고 signed int는 msb가 0 이면 +(plus), 1 이면 -(minus)를 표현하고 unsigned int는 2^n으로 사용된다.
wrap around는 Overflow와 밀접한 관계가 있는데 Overflow도 명확하게 이야기하면 두 종류로 나눌 수 있다.
- Overflow
정수형을 저장하는 변수의 타입이 표현할 수 있는 범위가 8bit라고 가정했을 때 변수의 값(literal)이 점차 증가하다 음수나 양수를 표현하는 msb에서 Carry가 발생할 때 생기는 현상 - Underflow
정수형을 저장하는 변수의 타입이 표현할 수 있는 범위가 8bit라고 가정했을 때 변수의 값(literal)이 점차 증감하다 음수나 양수를 표현하는 msb에서 Borrow가 발생할 때 생기는 현상
여기서 눈치가 빠른 사람들은 Overflow나 Underflow는 signed int(부호 있는 정수)와 관련 있는 것을 눈치챘을 것이다.
이제 Overflow와 Underflow를 설명하면서 말한 Carry와 Borrow를 이해해야 한다. lsb부터 시작하고 덧셈(addition) 연산을 하면 Carry라 하고 뺄셈(subtraction) 연산을 하면 Borrow라 하는데 Carry나 Borrow는 CPU의 ALU입장에서는 아주 자연스러운 현상이다. 8bit 기준으로 예를 들면 0000 1111 + 0101 0001과 같은 식이 있다면 1과 1이 만나는 bit에서 Carry가 발생하여 자리 올림수가 발생되고 식의 결과는 0110 0000이 된다. 앞의 설명이 어렵다면 8개의 규칙만 이해하면 끝이다. (2진수는 1bit가 2를 표현 못 함)
- Carry
1. 0 + 0 = 0
2. 0 + 1 = 1
3. 1 + 0 = 1
4. 1 + 1 = 0 (carry on!, 상위 자리로 올림 발생)
5. c(carry) + 0 + 0 = 1
6. c + 1 + 0 = 0 (carry on!)
7. c + 0 + 1 = 0 (carry on!)
8. c + 1 + 1 = 1 (carry on!)
위와 같이 8가지 규칙을 외웠다면 아래의 그림을 보자
위 그림에서 설명한 규칙을 그대로 Go로 코딩해 보았다.
package main
import (
"fmt"
"strconv"
"strings"
)
func main() {
leftOperand, leftBinaryCode := Int8ToBinaryCode(15)
rightOperand, rightBinaryCode := Int8ToBinaryCode(81)
fmt.Printf("leftOperand(%T): %d, leftBinaryCode: %s\n", leftOperand, leftOperand, leftBinaryCode)
fmt.Printf("rightOperand(%T): %d, rightBinaryCode: %s\n", rightOperand, rightOperand, rightBinaryCode)
TwoNumberAdditionCarryPrint(leftBinaryCode, rightBinaryCode)
}
func Int8ToBinaryCode(num int) (n int8, binaryCode string) {
binaryCode = strconv.FormatInt(int64(num), 2)
binaryCode = fmt.Sprintf("%08s", binaryCode)
n = int8(num)
return
}
func TwoNumberAdditionCarryPrint(left, right string) {
leftArr := strings.Split(left, "")
rightArr := strings.Split(right, "")
fmt.Printf(`
==============Start===============
left: %v
right: %v
==================================`, leftArr, rightArr)
rightBit := ""
leftBit := ""
carryStrArr := strings.Split(" ________", "");
carryFlag := false
carryRuleNumber := 0
index := len(leftArr) - 1
count := 0
for ;index > -1; index-- {
rightBit = rightArr[index]
leftBit = leftArr[index]
carryRuleNumber = GetCarryRule(carryFlag, leftBit, rightBit)
switch carryRuleNumber {
case 4:
carryFlag = true
rightArr[index] = "0"
leftArr[index] = "0"
case 8:
fallthrough
case 6:
carryFlag = true
leftArr[index] = "0"
case 7:
carryFlag = true
rightArr[index] = "0"
case 5:
leftArr[index] = "1"
fallthrough
case 1:
fallthrough
case 2:
fallthrough
case 3:
carryFlag = false
}
if carryFlag {
carryStrArr[index] = "C"
}
fmt.Printf(`
%d번 째 Bit
carryflag: %t
carry: %v
left: %v
right: %v %d번 규칙
==================================`, count, carryFlag, carryStrArr, leftArr, rightArr, carryRuleNumber)
count++
carryStrArr[index] = "_"
}
}
func GetCarryRule(flag bool, left, right string) (ruleNum int) {
switch {
case flag == false && left == "0" && right == "0":
ruleNum = 1
case flag == false && left == "0" && right == "1":
ruleNum = 2
case flag == false && left == "1" && right == "0":
ruleNum = 3
case flag == false && left == "1" && right == "1":
ruleNum = 4
case flag == true && left == "0" && right == "0":
ruleNum = 5
case flag == true && left == "1" && right == "0":
ruleNum = 6
case flag == true && left == "0" && right == "1":
ruleNum = 7
case flag == true && left == "1" && right == "1":
ruleNum = 8
}
return
}
좋은 코드가 아니지만 github에서 clone 할 수 있다. 이제 Borrow를 알아보자 01110111 - 00001001과 같은 식이 있다면 답은 01101110이 되고 Borrow는 한번 발생한다. (119 - 9 = 110) Borrow가 더 많이 발생하는 예제로 다시 보면 주로 양수 + 양수 = 음수 이런 식이 많아 9 - 92 = -83이 되는 예제로 하겠다. 일단 밑에 8가지 규칙을 암기 후 진행하자.
- Borrow
1. 0 - 0 = 0
2. 0 - 1 = 1 (borrow on!, 상위 자리에서 끌어오기 발생)
3. 1 - 0 = 1
4. 1 - 1 = 0
5. 0 - 0 - b(borrow) = 1 (borrow on!)
6. 0 - 1 - b = 0 (borrow on!)
7. 1 - 0 - b = 0
8. 1 - 1 - b = 1 (borrow on!)
9는 2진수로 0000 1001이고 92는 0101 1100이다. 이제 계산을 해보면
위와 같이 연산할 수 있는데 결과를 보면 110101101이다 10진수로 변경해보면 (signed int로 계산함) -82와 같은 잘 못된 결과가 나온다. 그 이유는 borrow가 발생하면서 8bit 자리보다 큰 9bit까지 borrow값을 표현해서 이런 결과가 나온 건데 msb와 lsb를 carry연산을 더 해줘야 우리가 원하는 값을 표현할 수 있다. (이걸 뭐라 하는지 알려주시면 감사...)
비로써 우리가 원한 -83를 얻게 된다.
본론으로 돌아와 wrap around를 이야기하자면 unsigned int인 경우 carry나 brorrow로 인해 wrap around가 발생하고 signed int인 경우 overflow와 underflow에 의해 발생하는데 단순히 비트의 순환이라고 생각하면 된다.
예를 들어 8bit를 갖는 정수 타입인 경우 127에서 + 1을 하게 되면 01111111 + 00000001이고 carry가 발생해서 음수와 양수를 표현하는 msb가 변경돼 Overflow가 발생하여 10000000이 돼 -128이 되는 것을 wrap around라 하는 것이다.
이번 포스트는 호기심 때문에 너무 깊게 들어갔고 시간이 너무 소비됐다.... 다음부턴 가볍게 포스트 해야겠다 ㅠㅠ
'Golang > Study' 카테고리의 다른 글
chapter3(6) primitive type - rune and string (0) | 2022.02.01 |
---|---|
chapter3(5) primitive type - float and complex (0) | 2022.02.01 |
chapter3(3) primitive type - uint and casting and overflow (0) | 2022.01.24 |
chapter3(2) primitive type - boolean and int (0) | 2022.01.23 |
chapter3(1) variable (0) | 2022.01.19 |