Search
Duplicate
🌊

오버플로우와 언더플로우

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
C
Scrap
태그
9 more properties
1.
정수를 비트로 표현하는 방법
정수를 비트로 표현하기
비트를 사용해 값을 만들 때 숫자를 상자에 값을 넣는다고 생각해보자. 10진 숫자 대신 비트를 사용하기 때문에 각 상자에 사용할 수 있는 기호는 1과 0 두 가지밖에 없다. 10진수에서는 맨 오른쪽 상자가 일의 자리, 그다음 왼쪽으로 갈 수록 10의 자리, 10^2의 자리... 라는 이름을 갖고 있었다. 2진수에서도 마찬가지다. 맨 오른쪽 상자는 일의 자리라는 이름이 붙어있지만, 그 다음 왼쪽 상자는 ‘2의자리’라는 이름이 붙어있을 것이다. 각 상자의 자릿수는 2의 거듭제곱이며, 따라서 2진수 체계는 10을 밑으로 하지 않고 2를 밑으로 하는 수 체계이다.
*양의 정수 표현
우리는 보통 10진수 체계를 사용하는데, 이는 우리의 손가락과 발가락이 10개씩 있어서 그렇다고 한다. ㅋㅋ 10진수 체계에서는 10가지 기호인 숫자, digit을 상자에 담을 수 있다. 이때 오른쪽에서 왼쪽으로 상자가 쌓여가며, 각 상자마다 각기 다른 이름이 붙어있다. 맨 오른쪽 상자자리에는 일의 자리, 오른쪽에서 두번째 상자에는 십의 자리, 세번쨰 상자는 백의 자리라는 이름이 붙는다. 각 이름은 10의 거듭제곱에 해당한다.
이 체계는 지수를 적용할 밑으로 10을 사용하기 때문에 밑이 10(영어로는 base)인 시스템이라고 부른다. 수의 값은 각 상자에 든 내용물의 값과 상자의 값을 곱한 것을 모두 더해서 결정한다.
비트를 사용해 값을 만들 때도 이와 비슷하게 접근할 수 있다. 10진 숫자 대신 비트를 사용하기 때문에 각 상자에 사용할 수 있는 기호는 1과 0 두 가지밖에 없다. 하지만 기호가 2개뿐이라고 문제가 되지는 않는다. 10진수에서 수를 표현할 수 없을 때는 더 큰 수를 표현하기 위해 상자를 추가할 수 있었다. 예를 들어 9라는 개념적인 수는 표현을 하기 위해 하나의 상자로 가능하지만, 10이라는 수를 표현하기 위해서는 2개의 상자가 필요하다. (두자리 10진수) 2진수에서도 마찬가지다. 맨 오른쪽 상자는 일의 자리라는 이름이 붙어있지만, 그 다음 왼쪽 상자는 ‘2의자리’라는 이름이 붙어있을 것이다. 각 상자의 자릿수는 2의 거듭제곱이며, 따라서 2진수 체계는 10을 밑으로 하지 않고 2를 밑으로 하는 수 체계이다.
2진수에서 가장 오른쪽의 비트를 가장 작은 유효비트, least significant bit라고 부르고, 가장 왼쪽의 비트를 가장 큰 유효비트라고 부른다. 가장 오른쪽의 비트를 변경하면 2진수의 값이 가장 작게 변경되고 가장 왼쪽의 비트의 값을 변경하면 2진수의 값이 가장 크게 변하기 때문에 이런 이름이 붙었다. 컴퓨터를 사용하는 사람들은 종종 세글자 줄임말(Three Letter Acronym)을 사용하기 때문에, 이들을 각각 주려 LSB, MSB라고 부른다.
가장 왼쪽에 있는 상자보다 더 왼쪽에 0을 추가하면 어떤 값을 표현하는 데 필요한 최소한의 상자개수보다 더 많은 상자를 추가할 수 있다. (이렇게 왼쪽에 추가하는 0을 leading zero라고 한다고 한다. )
*2진수의 덧셈
2진수의 덧셈도 10진수 덧셈과 마찬가지로 각 비트를 LSB쪽에서 MSB쪽으로 더하며 결과가 1보다 크면 다음 자리로 옮긴다.
//(2진덧셈의 규칙을 논리연산을 이용해 A AND B 와 A XOR B로 표현할 수 있기도 하다. )
덧셈 결과가 우리가 사용할 비트의 개수로 표현할 수 있는 범위를 벗어나면 어떻게 해야할까? 이런 겨우 오버플로우가 발생한다. overflow. 오버플로우라는 말은 MSB에서 올림이 발생했다는 뜻이다. 예를 들어 4비트 덧셈에서 1001과 1000을 더한 값은 10001 (9 + 8 = 17)이다. 하지만 MSB왼쪽에 사용할 수 있는 비트가 없기 때문에 결과가 0001이 된다.(1)
컴퓨터에는 조건 코드(혹은 상태코드) 레지스터 (condition code register)라는 것이 있어서 몇 가지 이상한 정보를 담아둔다. 이런 정보 중에는 오버플로우 비트가 있고, 이 비트에는 MSB에서 발생한 올림값이 들어간다. 이 비트값을 보면 오버플로가 발생했는지 알 수 있다.
MSB위쪽에서 1을 빌려오는 경우를 언더플로우라고 부른다. 이에 대한 조건 코드도 컴퓨터에 들어있다.
*음수 표현
한 비트를 부호에 사용하고 나머지 비트를 수의 크기, 즉 0부터의 거리(절댓값)를 표현하기 위해 사용하는 이런 방법을 부호와 크기 표현법이라고 말한다.
부호와 크기 표현법은 두가지 이유로 인해 널리 쓰이지 못하고 있다. 첫째, 비트들을 구성하려면 비용이 드는데 0을 표현하는 방법이 두 가지라서 비용이 낭비된다. 둘째, 부호와 크기 표현법을 사용하면 AN와 XOR를 통한 덧셈 계산을 사용할 수가 없다.
음수를 표현하는 또 다른 방법으로는 양수의 모든 비트를 뒤집는 방법이 있다. 이런 방법을 1의 보수 표현법이라고 부른다. 1의 보수 표현법에서도 부호와 크기 표현법과 비슷하게 비트들을 부호 비트와 나머지로 나눈다.
표를 보면 0011(3)을 뒤집으면 1100(-3)이 되는 것을 볼 수 있다.
하지만 이 방법 역시 0을 두가지 방식으로 표현한다는 문제가 여전히 존재한다. 그리고 1의 보수에서도 덧셈을 쉽게 할 수는 없다. 이 문제를 해결하려면 MSB쪽에서 올림이 발생한 경우 LSB로 올림을 전달해야 하는데 이를 순환 올림이라고 부른다.
0 0 1 0 (2)
1 1 1 0 (-1)
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
1 0 0 0
(10)
MSB를 더하면 10이 나오기 때문에 0을 부호비트로 쓰고 1을 순환올림으로 LSB에 더하면,
0001이 되고 +1이 되어 값이 맞다!
하지만 이런 방법 역시 좀 복잡하다.
현대 컴퓨터에서는 부호와 크기 표현법이나 1의 보수 표현법을 모두 사용하지는 않는다. 이 방법들은 하드웨어를 더 추가해야 하는 방식이기 때문에 비용을 절감하는 방법을 찾아냈다.
*2의 보수
+1에 더했을 때 0이 나오는 비트 패턴을 찾고 이 패턴을 -1이라고 불러보자.
4비트 수의 경우 +1은 0001이다. 1111을 0001에 더하면 0000이 된다. 따라서 1111을 (4비트에서) -1을 표현하는 비트 패턴으로 사용하자.
이 방법은 부호가 있는 정수를 표현할 때 가장 널리 쓰이는 방법이다. 어떤 수의 비트를 뒤집고 1을 추가하면 음수를 얻을 수 있다. 이런 표현법을 2의 보수 표현법(two’s complement)이라고 하며, 이때 MSB에서 올림이 발생하면 이 값은 버린다. 여기에서도 최상위 비트는 음수를 표현할 수 있게 된다. (0은 양수, 1은 음수)
예시를 보면 다음과 같다.
+2는 0010이고 비트를 뒤집으면 1101이며, 1을 더하면 1110이고 이 값이 -2를 표현한다. 다음 표는 3부터 1씩 감소시키며 표현해본 것이다.
여기에서 0을 음수 처리 해보면, 1111 → 10000 → 0000으로 되어 여전히 0000이다.
0을 표현할 방법이 하나 밖에 없기 때문에 이전 방법들에서 중복되던 문제를 피할 수 있게 된 것이다!
보통 사용하는 int 정수형 변수는 8바이트, 32비트 정수이다.
ft_atoi에서 -2147483648의 절댓값을 꺼내기 위해
m = m * 10 + n %10; 꼴을 계속 수행할 때,
m = 214748364 이고 n = 8이 남아있을때 마지막 저 윗줄을 수행하면
m = 2147483640 + 8이 되어 2147483648 , 즉 int값을 초과하게 된다.
2147483647은 비트로 표현하면 01111 1111.... (총 숫자 32개)로 표현될 것이고, 여기서 +1을 하면
1000 0000 ... 000(총 숫자 32개)가 될 것이다.
마지막에 부호 -1을 곱해주기 위해 2의 보수 체계의 방식을 따르면
01111 1111 1111 ... 1111 으로 뒤집고 +1을 해서 1000 0000 .... 0000(총 32개)가 된다.
이 비트가 의미하는 값이 바로 -2147483648이다!! 이런 논리로 -2147483648이 그대로 나올 수 있게 되는 것이다...!
단, atoi 함수의 실제 사용 매뉴얼을 보면 (int)strtol 함수와 같다고 나와있다. string 을 long으로 변환후 int형 변환한 것과 같다는 의미인 것이다. 실제 사용시 정수값을 초과하는 숫자를 넣으면 이 함수의 결과값은 -1이 나온다. 그래서 보통은 long으로 값을 처리 한 후, 정수의 범위를 명시하는 조건문을 사용해서 범위를 벗어날 경우 따로 -1을 출력하게끔 하는 등의 코드로 예외처리를 하는 경우를 많이 보았다.