두 int값의 +연산후 오버플로우 여부 검출하기 퀴즈 채점결과!!!

gcc + gprof로도 실험해봤는데

의미있는 결과는 안나오네요

워낙 함수 크기가 작아서 -_-;

signed integer type에 대해서 sign bit은 필요하지만
padding bit은 필요없다고 하는군요.
그것은 implementation에 달려있다고 하지만,
요즘 padding bit을 사용하는 곳이 있는지 모르겠군요..
적어도 x86 machine과.. 음.. 그밖에 잘 알려진 CPU에서는 사용하지 않을것으로 생각합니다.

엄밀하게 생각한다면, 속도문제를 해결하기 위해 경우에 따라 특별하게 사용되는, 값을 2배씩 증감시키기 위해 사용되는 <<, >> 연산 자체가 성립되지 않습니다. two’s complement를 지원하는 머신에서는 적용될 수 없기 때문에요.. 다만 one’s complement를 지원하는 머신에서만 지원될 수 있기 때문이죠...

이후의 얘기는 모두 유부호 정수형을 전제로 하겠습니다.

ps. 점점 게시판 성격에 맞지 않는 글이... -_-;

ps. 저기... top-posting은 하지 않으셨으면 좋겠네요.

이런 식으로 쓰는 것입니다.

htna 님의 저번글과 이번글에서 제가 혼동되었던 것이 2의 보수라는 표현과 1의 보수라는 것을 바꿔서 기술하신 것이었습니다.

보통의 어셈블리에서는 쉬프트 연산의 오퍼랜드를 부호가 있는 것이냐 아니냐 (혹은 산술이냐 논리냐)에 따른 2가지 명령을 부여하고 있습니다.

대부분의 CPU가 음수를 2의 보수로 표현하고 이것의 쉬프트 연산을 산술 쉬프트로 수행해서 부호를 유지하면서 비트를 이동시킬 수 있습니다. 논리 쉬프트는 부호에 영향을 받지 않습니다.

1의 보수보다 2의 보수가 하드웨어적으로 산술 연산을 구현이 쉽고 쉬프트같은 경우 표현하기 쉽기 때문에 사용한 것인지는 몰라도 (사람의 눈에는 1의 보수가 편할지 몰라도요) 대부분 2의 보수를 채택하고 있는 걸로 알고 있습니다.

2의 보수와 1의 보수를 바꿔썼네요..
음. 학부 졸업한지 5~10년이 되어가고 있다보니 용어를 정확히 기억하지 못하다보니..
이미, bugiii님께서 언급해 주셨기에 doldori님이 용어혼동에 대해서 언급하시는 문제는 넘어가겠습니다.

확인해보니 이렇게 되네요.
저도 이론적으로만 알고 있었지 실제 확인해 본 것은 아니었습니다만.
unsigned int, signed int의 <<, >> 모두 하나의 비트연산으로 이뤄지고 있네요.
물론 변수에서 레지스터로 값을 이동시키는 과정이 추가로 있기는 하지만.. 이는 <<, >> 자체의 연산과는 연관이 없는것이기에...

27:       {
28:           int t=-8;
00404333   mov         dword ptr [t],0FFFFFFF6h
29:           int t1 = t << 2;	// -32
0040433A   mov         eax,dword ptr [t]
0040433D   shl         eax,2
00404340   mov         dword ptr [t1],eax
30:           int t2 = t << 1;	// -16
00404343   mov         ecx,dword ptr [t]
00404346   shl         ecx,1
00404348   mov         dword ptr [t2],ecx
31:           int t3 = t >> 1;	// -4
0040434B   mov         edx,dword ptr [t]
0040434E   sar         edx,1
00404350   mov         dword ptr [t3],edx
32:           int t4 = t >> 2;	// -2
00404353   mov         eax,dword ptr [t]
00404356   sar         eax,2
00404359   mov         dword ptr [t4],eax
33:           unsigned int tt = 8;
0040435C   mov         dword ptr [tt],0FFh
34:           int tt1 = tt << 2;
00404363   mov         ecx,dword ptr [tt]
00404366   shl         ecx,2
00404369   mov         dword ptr [tt1],ecx
35:           int tt2 = tt << 1;
0040436C   mov         edx,dword ptr [tt]
0040436F   shl         edx,1
00404371   mov         dword ptr [tt2],edx
36:           int tt3 = tt >> 1;
00404374   mov         eax,dword ptr [tt]
00404377   shr         eax,1
00404379   mov         dword ptr [tt3],eax
37:           int tt4 = tt >> 2;
0040437C   mov         ecx,dword ptr [tt]
0040437F   shr         ecx,2
00404382   mov         dword ptr [tt4],ecx
38:       }

PS:
아무래도 회사 다니면서, 틈틈히 KLDP에 글을 보면서 글을 올리다보니.. 아무래도 응답이 늦어지게 되네요.. 몇몇 눈에 보이는 것들만 리플 답니다..

후... 참 멀리까지도 왔군요. 어쩌다가 이런 얘기가 나왔는지 기억도 나지 않네요.
지금까지 얘기를 나눈 느낌으로는 htna님은 낙관파이시고 저는 비관파라고 할 수
있겠군요. "흔히 통용되는 사항이라면 표준에서 보장해주지 않아도 쓸 수 있다."와
"표준에서 보장하지 않는 것은 최소한으로만 쓰겠다." 맞죠? 어느 쪽이 더 바람직한
것인지는 저도 단언하지 못하겠습니다만, 특별한 계기가 생기지 않는 이상 저는
저의 스타일을 지킬 것입니다. (갑자기 웬 비장감이...)
아무튼 이번 기회에 많이 배웠고 재미도 있었습니다.

ps. 그래도 놀이터는 놀이터다워야...

kkb110님, 제가 중얼거린 말에 대해서는 너무 괘념치 마세요. 토요일이니 놀아봅시다.

// assume range check for addition is implemented somehow
bool OutOfRangeForAddtion(int a, int b);

bool OutOfRangeForSubtraction(int a, int b)
{
    return OutOfRangeForAddtion(a, -b);
}

// assume b != 0
bool OutOfRangeForDivision(int a, int b)
{
    return false;
}

// assume range check for addition is implemented somehow
bool OutOfRangeForAddtion(int a, int b);

// assume b != INT_MIN
bool OutOfRangeForSubtraction(int a, int b)
{
    return OutOfRangeForAddtion(a, -b);
}

// assume b != 0, a>0, b>0
bool OutOfRangeForDivision(int a, int b)
{
    return false;
}

음수의 나눗셈은 어떻게 되는건지 모르겠군요. ㅠㅜ

어제 올려놓고 틀린거 발견해서 지웠네요 -_-;;

그나저나 이제 사칙연산 모두에 대한거니 새 쓰레드를 열어야하지 않나요?

ㅎㅎㅎ

bool is_sum_overflow(int a,int b)
{
    unsigned int c, result;

    c = (unsigned)a + (unsigned)b;
    result = (a ^ c) & (b ^ c);
    if (result & (0x80 << (sizeof(int)-1)*8))
        return 1;
    else
        return 0;
}

bool is_mult_overflow(int a, int b)
{
    int sign, result;
    int multiplicand = 0;

    sign = ((a ^ b) & (0x80 << (sizeof(int)-1)*8)) && 1;
    a &= 0x7fffffff; // removing sign bit
    b &= 0x7fffffff; 
    while (a != 0 && b != 0)
    {
        result = a * (b & 0x1);
        result = sign ? -result : result;
        b >>= 1;
        if (is_sum_overflow(result, multiplicand) == true)
            return true;
        multiplicand += result;
    }
    return false;
}

2의 보수체계에서는 항상 음수가 1이 더 많으므로 혹시나 모를 상황이 있으니

체크해봤습니다. 다시 is_sum_overflow를 호출하니 느리겠지만

귀찮아서 -_-;

bool is_mult_overflow(int a, int b)
{
    int sign, result;
    int multiplicand = 0;

    sign = ((a ^ b) & (0x80 << (sizeof(int)-1)*8)) && 1;
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;
    while (b != 0)
    {
        result = a * (b & 0x1);
        result = sign ? -result : result;
        b >>= 1;
        if (is_sum_overflow(result, multiplicand) == true)
            return true;
        multiplicand += result;
    }
    return false;
}

참 제거하면 안되겠네요. -_-;;

이런 실수를...

bool OutOfRangeForModulus(int a, int b) 
{ 
    return false;
} 

정수 % 음수 의 결과가...
VC60, gcc(버전은 모릅니다. ㅡ.ㅜ) 로 테스트 해 봤는데..
여기서는 양수로 나오는군요..
하지만 Visual FoxPro manual에는 음수로 나와야 한다고 하네요..
음. 어느게 맞는지 모르겠네요..
예전에 배울때 "정수 % 음수" 의 결과가, 음수 였는지 양수 였는지...

만약 음수로 modulus를 취했을때 음수로 나와야 하는게 맞다면 리턴값은 false가 될 수 밖에 없구요..
양수가 나오는게 맞다고 한다면, 그래도 false 입니다.

우선 "a % b = c" 라고 할때, c의 절대값은 b의 절대값 보다 작아야 합니다.
이때 문제가 되는 경우가 b가 MIN_INT일때 인데..
공교롭게도 a역시 MIN_INT라고 한다면, c는 0이 될 수 밖에 없습니다.
그렇기에 어떠한 경우라도 overflow/underflow는 발생할 수 없는거죠.

하하하.... 이거 제가 크게 착각했군요.
뇌세척이라도 받아야겠습니다. ㅡ_ㅡ;;
'%'는 overflow가 없습니다.

#define MIN ((T)(((unsigned T)~0 >> 1) + 1))
#define DIV ((T)(-1))

T foo(T i, T j)
{
  return i % j;
}

int main()
{
  return (int) foo(MIN, DIV);
}

$ gcc --version | head -1;
gcc (GCC) 3.4.3 20050227 (Red Hat 3.4.3-22.fc3)
$ for i in char short int long "long long" ; do
>     echo -n "checking for $i... ";
>     gcc -DT="$i" test.c;
>     ./a.out && echo OK;
> done
checking for char... OK
checking for short... OK
checking for int... Floating point exception
checking for long... Floating point exception
checking for long long... OK
$ 

구현체라면 idiv 뿐이 없으니 CPU쪽에서 그렇게 처리하는듯 하군요.
assembler로..
idiv eax,dword ptr [ebp+0Ch]
뿐입니다..

것두 특이하게 "INT_MIN % variable_minus_one" 일 경우만이네요..

int a = INT_MIN;
int b1 = -1;
int b2 = -2;
int b3 = 1;
int c1 = a % b1;  // overflow
int c2 = a % b2;
int c3 = a % b3;
int c4 = a % -1;
int c5 = INT_MIN % b1;  // overflow
int c6 = INT_MIN % b2;
int c7 = INT_MIN % b3;
int c8 = INT_MIN % -1;

걍 예외로 생각하고 잊고 넘어가면 될 듯 합니다..
적당히 잊어버리면서 살아야...
머리가 포화되지 않죠.. ^^

아, 전웅님 반갑습니다. 설명 잘 들었습니다. 그건 생각 못했군요.

ps. 흠흠... 여쭤보고 싶은 것이 있지만 가뜩이나 바쁘신 것 같은데 부담을 드릴까봐 차마...

(실제로 Mathmetica 같은 수학 전문 프로그램은 정수 나눗셈(Integer Division)을 따로 구현하고 있는 모양이지만 (저도 직접 본 적은 없습니다.), C에서는 '나누기' 하나로 전부를 포함하고 있는게 이런 혼란의 원흉이지 싶습니다.
뭐 C가 수학을 하기 위한 언어는 아닐테니 이정도는 "그냥 그런가보다"하고 넘어가는게 좋을지도 모르겠습니다.
그런데.. fortran 같은 경우엔 어떤지 궁금하네요. 누구 포트란 하시는 분 안계신가요? ;))

참고: Integer Division in mathworld

PS:
그렇게 볼때...
1, 2, 3 번 모두 만족하는것 같습니다..
주어진 전제를 다시한번 잘 보시면...
테스트 해 봤습니다만, 1,2,3 모두 만족하는것 같군요.
특별히 overflow 와 같이 특수상황이 아니고서는요...

제가 확인하면서...
0 <= a % b
를 생각 못했군요..
3번의 "0 <= a % b"는 만족시켜주지 않는듯 합니다.

음. 근데 저 3가지 기준을..
어디서 찾아보면 되죠.. ??