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

kkb110의 이미지

http://bbs.kldp.org/viewtopic.php?t=56561

저번에 냈던 문제 채점합니다 ^^;
저까지 총 4명이 코드를 만들었는데요

먼저 htna

//htna
bool func(int a,int b) 
{ 
    return !( 
        ((a&0xF000) != (b&0xF000)) || 
        ((a&0xF000) == ((a+b)&0xF000)) 
    ); 
}

그다음 cppig1995

//cppig1995
bool func(int a,int b) 
{ 
   bool Bigger = true; 

   if((a < 0) || (b < 0)) Bigger = !Bigger; 


   int c = a + b; 

   if(Bigger && ((c < a) || (c < b))) return false; 
   else if(!Bigger && ((c > a) || (c > b))) return false; 
    
   return true; 
}

다음 morris

//morris
bool func(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; 
} 

마지막으로 저 kkb110

//kkb110
unsigned int func_kkb110(int a,int b)
{
	return (a>a+b) ^ ((bool) (  (1<<(CHAR_BIT*sizeof(int)-1)) & b  ));
}

근데 cppig1995님코드는 오버플로우가 제대로 검출이 안되더군요!
확인 안하셨다그러더니;; 그래서 탈락 -_-;;;

컴파일러는 vc7을 이용했구요.. 팬티엄4 노스우드코어에서 테스트했고 소스 대략은 다음과같습니다.

inline unsigned int getcycle()
{
	__asm 
	{
		cpuid
		rdtsc
	}
}
#define repeatN 100000000

int main()
{
	unsigned int cycle1,cycle2;
	int a,b,t;
	cin >> a;
	cin >> b;

	getcycle();getcycle();getcycle();
	cycle1 = getcycle();
	for (int i = repeatN; i; --i)
	{
		t +=i;
		t += func_NAME(a,b);
	}
	cycle2 = getcycle();
	
	cout << "speed : " << ((double)(cycle2-cycle1))/(repeatN/100) << "\n\n\n";
	
	cout << t;
	cin >> t;
	return 0;
}

vc7이 최대최적화하니까 코드를 자꾸 생략해서 생략안시키느라고 저렇게 됬습니다 -_-; 처음엔 옵션설정으로 해볼라그랬는데 잘 안되서 -_-;;
함수는 모두 inline입니다..

각 코드의 asm코드입니다.

htna

//htna
inline bool func_htna(int a,int b) 
{ 
    return !( 
        ((a&0xF000) != (b&0xF000)) || 
        ((a&0xF000) == ((a+b)&0xF000)) 
    ); 
00401000 8B 4C 24 04      mov         ecx,dword ptr [esp+4] 
00401004 8B 54 24 08      mov         edx,dword ptr [esp+8] 
00401008 56               push        esi  
00401009 8B C1            mov         eax,ecx 
0040100B 8B F2            mov         esi,edx 
0040100D 81 E6 00 F0 00 00 and         esi,0F000h 
00401013 25 00 F0 00 00   and         eax,0F000h 
00401018 3B C6            cmp         eax,esi 
0040101A 5E               pop         esi  
0040101B 75 12            jne         func_htna+2Fh (40102Fh) 
0040101D 03 CA            add         ecx,edx 
0040101F 81 E1 00 F0 00 00 and         ecx,0F000h 
00401025 3B C1            cmp         eax,ecx 
00401027 74 06            je          func_htna+2Fh (40102Fh) 
00401029 B8 01 00 00 00   mov         eax,1 
}
0040102E C3               ret       

inline
{
	t +=i;
00401FC0 03 FA            add         edi,edx 
	t += func_htna(a,b);
00401FC2 3B C6            cmp         eax,esi 
00401FC4 75 14            jne         main+7Ah (401FDAh) 
00401FC6 8D 0C 2B         lea         ecx,[ebx+ebp] 
00401FC9 81 E1 00 F0 00 00 and         ecx,0F000h 
00401FCF 3B C1            cmp         eax,ecx 
00401FD1 74 07            je          main+7Ah (401FDAh) 
00401FD3 B9 01 00 00 00   mov         ecx,1 
00401FD8 EB 02            jmp         main+7Ch (401FDCh) 
00401FDA 33 C9            xor         ecx,ecx 
00401FDC 0F B6 C9         movzx       ecx,cl 
00401FDF 03 F9            add         edi,ecx 
00401FE1 4A               dec         edx  
00401FE2 75 DC            jne         main+60h (401FC0h) 
}

morris

//morris
inline bool func_morris(int a, int b) 
{ 
    unsigned int c, result; 

    c = (unsigned)a + (unsigned)b; 
00401040 8B 4C 24 04      mov         ecx,dword ptr [esp+4] 
00401044 8B 54 24 08      mov         edx,dword ptr [esp+8] 
00401048 56               push        esi  
00401049 8D 04 11         lea         eax,[ecx+edx] 
    result = (a ^ c) & (b ^ c); 
    if (result & (0x80 << (sizeof(int)-1)*8)) 
0040104C 8B F0            mov         esi,eax 
0040104E 33 F1            xor         esi,ecx 
00401050 33 C2            xor         eax,edx 
00401052 23 F0            and         esi,eax 
00401054 F7 C6 00 00 00 80 test        esi,80000000h 
0040105A 0F 95 C0         setne       al   
0040105D 5E               pop         esi  
        return 1; 
    else 
        return 0; 
} 
0040105E C3               ret    

inline
{
	t +=i;
	t += func_morris(a,b);
00401FA2 8B C1            mov         eax,ecx 
00401FA4 33 C6            xor         eax,esi 
00401FA6 8B 74 24 14      mov         esi,dword ptr [esp+14h] 
00401FAA 33 CF            xor         ecx,edi 
00401FAC 23 C1            and         eax,ecx 
00401FAE BA 00 E1 F5 05   mov         edx,5F5E100h 
00401FB3 25 00 00 00 80   and         eax,80000000h 
00401FB8 03 F2            add         esi,edx 
00401FBA 85 C0            test        eax,eax 
00401FBC 0F 95 C1         setne       cl   
00401FBF 0F B6 C9         movzx       ecx,cl 
00401FC2 03 F1            add         esi,ecx 
00401FC4 4A               dec         edx  
00401FC5 75 F1            jne         main+58h (401FB8h) 
}

kkb110

//kkb110
inline unsigned int func_kkb110(int a,int b)
{
	return (a>a+b) ^ ((bool) (  (1<<(CHAR_BIT*sizeof(int)-1)) & b  ));
00401060 8B 44 24 04      mov         eax,dword ptr [esp+4] 
00401064 8B 4C 24 08      mov         ecx,dword ptr [esp+8] 
00401068 53               push        ebx  
00401069 8D 14 08         lea         edx,[eax+ecx] 
0040106C 33 DB            xor         ebx,ebx 
0040106E 3B C2            cmp         eax,edx 
00401070 0F 9F C3         setg        bl   
00401073 F7 C1 00 00 00 80 test        ecx,80000000h 
00401079 0F 95 C0         setne       al   
0040107C 0F B6 C8         movzx       ecx,al 
0040107F 33 D9            xor         ebx,ecx 
00401081 8B C3            mov         eax,ebx 
00401083 5B               pop         ebx  
}
00401084 C3               ret       

inline

{
	t +=i;
	t += func_kkb110(a,b);
00401F9F 33 DB            xor         ebx,ebx 
00401FA1 3B F2            cmp         esi,edx 
00401FA3 8B 74 24 10      mov         esi,dword ptr [esp+10h] 
00401FA7 0F 9F C3         setg        bl   
00401FAA F7 C1 00 00 00 80 test        ecx,80000000h 
00401FB0 0F 95 C1         setne       cl   
00401FB3 0F B6 D1         movzx       edx,cl 
00401FB6 8B F8            mov         edi,eax 
00401FB8 8B CB            mov         ecx,ebx 
00401FBA B8 00 E1 F5 05   mov         eax,5F5E100h 
00401FBF 33 CA            xor         ecx,edx 
00401FC1 8D 14 01         lea         edx,[ecx+eax] 
00401FC4 03 F2            add         esi,edx 
00401FC6 48               dec         eax  
00401FC7 75 F8            jne         main+61h (401FC1h) 
}

측정은 연속해서 3번씩돌린결과..
htna님의 코드는 a와 b가 부호가 같을때와 다를때 속도가 차이나서 두번 테스트했습니다

htna
부호 같을때 :
612.394
612.867
614.451
다를때 :
442.258
427.854
438.334

morris
457.936
459.082
456.745

kkb110
203.246
203.38
204.194

근데 이 테스트는 잘못되었습니다
inline어셈코드 마지막을 보시면 각각 되돌아가는 분기가 다릅니다. 심지어 제코드(kkb110)는 그냥 덧셈만하고 루프만 도는 꼴이네요. vc7이 싫어지는 순간입니다. -_-
인라인 안할수도 있는데 그렇게하면 함수호출오버헤드가 너무 커서
셋다 비슷한 클럭이 나오더군요..
asm코드상으로보면 morris님코드가 가장 빠를것으로 생각됩니다. 코드와 어셈을 비교해보면 놀랍기까지 하군요!

벤치마킹실패(...)
혹시 좋은생각있으시면 댓글부탁드리구요..
벤치마킹연구좀 더해봐야겠습니다 -_-;;
아니면 gcc는 옵션많아서 컴파일러설정으로 해결할수 있을법도한데..

Forums: 
doldori의 이미지

morris님을 제외한 다른 분들은 코드에 a + b가 나온 것만으로 탈락입니다.
이식성과 가독성이 좋은 방법을 소개합니다. (아마 성능상으로도 별로 문제는 없을 것 같네요.)

#include <limits>

template<typename SignedIntegralType>
bool OutOfRange(SignedIntegralType a, SignedIntegralType b)
{
    return (b > 0 && a > std::numeric_limits<SignedIntegralType>::max() - b) ||
           (b < 0 && a < std::numeric_limits<SignedIntegralType>::min() - b);
}
cppig1995의 이미지

doldori wrote:
morris님을 제외한 다른 분들은 코드에 a + b가 나온 것만으로 탈락입니다.
이식성과 가독성이 좋은 방법을 소개합니다. (아마 성능상으로도 별로 문제는 없을 것 같네요.)
#include <limits>

template<typename SignedIntegralType>
bool OutOfRange(SignedIntegralType a, SignedIntegralType b)
{
    return (b > 0 && a > std::numeric_limits<SignedIntegralType>::max() - b) ||
           (b < 0 && a < std::numeric_limits<SignedIntegralType>::min() - b);
}

kkb110 wrote:
두 int값의 +연산후 오버플로우 여부 검출하기

#include <limits>

bool OutOfRange(int a, int b)
{
    return (b > 0 && a > std::numeric_limits<int>::max() - b) ||
           (b < 0 && a < std::numeric_limits<int>::min() - b);
}

Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.

익명 사용자의 이미지

두수 a,b를 더한다음 결과가 max(a,b)보다 작으면 오버플로우아닌가요?? 왜케 복잡하게짜는지 좀 이해가...??

익명 사용자의 이미지

Anonymous wrote:
두수 a,b를 더한다음 결과가 max(a,b)보다 작으면 오버플로우아닌가요?? 왜케 복잡하게짜는지 좀 이해가...??

1 + (-1) 을 계산해 보아요~~~

kkb110의 이미지

doldori wrote:
morris님을 제외한 다른 분들은 코드에 a + b가 나온 것만으로 탈락입니다.
이식성과 가독성이 좋은 방법을 소개합니다. (아마 성능상으로도 별로 문제는 없을 것 같네요.)
#include <limits>

template<typename SignedIntegralType>
bool OutOfRange(SignedIntegralType a, SignedIntegralType b)
{
    return (b > 0 && a > std::numeric_limits<SignedIntegralType>::max() - b) ||
           (b < 0 && a < std::numeric_limits<SignedIntegralType>::min() - b);
}

아 그렇군요 찾아보니 오버플로우가 일어나는경우엔 예외가 발생된다고 나와있네요..
그런데 궁금한게 있는데 최상위비트를 부호비트로 가정하는것도 엄격하게따지면 해선 안되는 것인가요?

morris의 이미지

a+b 테스트를 한 100억번 정도 해보면

되지 않을려나요? -_-;;

익명 사용자의 이미지

이 문제는 다분히 간단한 수학적인 센스~를 발휘하는것이 포인트입니다. doldori님의 답은 복잡한것이 아니라 (수학적으로)명쾌한 해답입니다. 다른분들은 두 수를 더해서 그것이 오버플로우인가 아닌가를 check하려고 했지만..이 문제의 의도는 그것이 아닙니다. 잘생각해보세요.. 8)

doldori의 이미지

kkb110 wrote:
그런데 궁금한게 있는데 최상위비트를 부호비트로 가정하는것도 엄격하게따지면 해선 안되는 것인가요?

네, 안됩니다. unsigned char형을 제외한 정수형을 나타내는 비트는 value bit와
padding bit로 나누어지는데(unsigned char형은 모든 비트가 value bit입니다),
최상위 비트가 padding bit에 해당하는 환경에서는 그런 가정을 할 수 없죠.
자세한 내용은 han.comp.lang.c 뉴스 그룹에서 "trap representation"으로
검색해 보시면 많이 나옵니다. (전웅님의 글) 이런 얘기는 C++ 표준에 직접적으로
나오지는 않지만 C와의 호환성을 유지하겠다는 내용이 나오는 걸로 봐서 이 점에
대해서는 C 표준을 적용해도 무리가 없겠습니다.
morris의 이미지

gcc + gprof로도 실험해봤는데

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

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

htna의 이미지

저도 모르는 새에 이런 테스트가 있었군요...
이제야 봤습니다...

1000 0000 0000 0000 0000 0000 0000 0000
를 표현한다는게 그만, 0xF000 으로 표현했네요.. 쯔아비..
0x80000000 로 했어야 했는데 말이죠..

stress test 해 봤습니다.
INT_MAX + INT_MAX와
INT_MIN + INT_MIN을 테스트 해 봤는데...
cppig1995만 빼고는 정상으로 나왔네요...
(저의 0xF000를 0x80000000로 고쳐서 테스트 했습니다.)
아무래도 cppig1995님께서 리턴을 거꾸로 하신게 아닌가 생각이 드는군요.

PS:
물론 signed와 unsigned 를 고려해서 최상위 비트를 사용하지 않는다고 전제를 하는것이 좋겠습니다만..
그런 전제가 처음부터 들어갔다면, 다들 그 문제를 고려해서 작성했을 것이라 봅니다.
우선 제가 최상위비트를 이용하도록 초기 작성을 했기에, 다들 저의 기준으로 따라왔을 가능성도 농후하다고 봅니다.
물론 완벽한 코드가 좋은것은 사실입니다만. dodori님께서는 이미 numeric_limits<T>를 이용하셨기에, 음.. 이미, 충분히 MAX_INT, MIN_INT를 사용하셨다고 봐도 충분하다고 생각합니다만...

PS2:
먼저 글을 올렸다가. stress test를 엉뚱하게 하는바람에 지우고 다시 올립니다.
혹시 그사이에 보신분들 계시다면.. (아마 없을거라 생각이 듭니다만..)
죄송합니다.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

kkb110의 이미지

cppig1995님코드는 반대로된건 반대로 된거지만
a와 b가 하나는 음수고 하나는 양수일경우의 처리가 일정하지 않은것같습니다.

그리고 c99문서에는 다음과 같이 나와있던데

읽어보니 패딩비트가 sign비트와 value비트 가운데 있군요
sign비트는 1비트여야하구.. 값이 1이라면 1의보수나 2의보수일수있군요.
그렇다면 최상위비트가 부호비트라고 가정해도 되지만 1의보수일수도있고 2의보수일수도있다.. 이렇게 되는것같은데..
아닌가.. 그냥 padding,sign,value 비트가 있다는것만 언급한거고 순서는 상관없는건가.. 그렇다면 sign bit를 사용할 방법은 없나??
이거 점점 더 미묘해지는데요? -_-;;;

Quote:
1For unsigned integer types other thanunsigned char,the bits of the object
representation shall be divided into twogroups: value bits and padding bits (there need
not be anyofthe latter).If there areNvalue bits, each bit shall represent a different
N-1
power of 2 between 1 and 2,sothat objects of that type shall be capable of
N
representing values from 0 to 2-1using a pure binary representation; this shall be
44)
known as the value representation.The values of anypadding bits are unspecified.
2Forsigned integer types, the bits of the object representation shall be divided into three
groups: value bits, padding bits, and the sign bit.There need not be anypadding bits;
there shall be exactly one sign bit.Each bit that is a value bit shall have the same value as the same bit in the object representation of the corresponding unsigned type (if there are
Mvalue bits in the signed type andNin the unsigned type, thenM≤N). Ifthe sign bit
is zero, it shall not affect the resulting value. Ifthe sign bit is one, the value shall be
modified in one of the following ways:
--the corresponding value with sign bit 0 is negated (sign and magnitude);
N
--the sign bit has the value-(2)(two’scomplement);
N
--the sign bit has the value-(2-1) (one’scomplement).
Which of these applies is implementation-defined, as is whether the value with sign bit 1
and all value bits zero (for the first two), or with sign bit and all value bits 1 (for one’s
complement), is a trap representation or a normal value. Inthe case of sign and
magnitude and one’scomplement, if this representation is a normal value it is called a
negative zero.
3If the implementation supports negative zeros, theyshall be generated only by:
--the&,|,^,~,<<,and>>operators with arguments that produce such a value;
--the+,-,*,/,and%operators where one argument is a negative zero and the result is
zero;
--compound assignment operators based on the above cases.
It is unspecified whether these cases actually generate a negative zero or a normal zero,
and whether a negative zero becomes a normal zero when stored in an object.
4If the implementation does not support negative zeros, the behavior of the&,|,^,~,<<,
and>>operators with arguments that would produce such a value is undefined.
45)
5The values of anypadding bits are unspecified.Avalid (non-trap) object representation
of a signed integer type where the sign bit is zero is a valid object representation of the
corresponding unsigned type, and shall represent the same value.
6Theprecisionof an integer type is the number of bits it uses to represent values,
excluding anysign and padding bits.Thewidthof an integer type is the same but
including anysign bit; thus for unsigned integer types the twovalues are the same, while
for signed integer types the width is one greater than the precision.
익명 사용자의 이미지

어셈코드 내장으로~~

htna의 이미지

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

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

Quote:
For signed integer types, the bits of the object epresentation shall be divided into three groups: value bits, adding bits, and the sign bit.There need not be any padding bits; there shall be exactly one sign bit.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

doldori의 이미지

kkb110 wrote:
읽어보니 패딩비트가 sign비트와 value비트 가운데 있군요

그렇지 않습니다. 정수형을 표현하는 비트의 종류를 나열한 순서일 뿐 반드시 그런
순서로 비트열이 구성된다는 뜻은 아닙니다. 인용하신 표준의 문구를 잘 읽어보면
아시겠지만 undefined, unspecified, implementation-defined 투성이입니다.
그냥 아무것도 가정하지 않는 것이 속 편합니다.

놀이터에서 하는 얘기 치고는 너무 심각해서 농담 비슷한 얘기를 해보겠습니다.
다음 중에서 프로그램이 도는 데 별로 지장을 주지 않는 가정은 어떤 것일까요?
1. 1바이트는 8비트이다.
2. 최상위 비트는 sign bit이다.
3. padding bit는 없다.
4. trap representation은 없다. (가능한 모든 비트 패턴의 조합은 모두 유효한 값을 나타낸다.)
5. int 변수의 모든 비트가 0이면 그 변수의 값은 0이다.
6. int 값은 wrap-around 된다. (INT_MAX + 1 == INT_MIN, INT_MIN - 1 == INT_MAX이다.)

doldori의 이미지

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

자꾸 딴지를 거는 것 같아서 죄송하지만 그렇지 않습니다. E1 << E2의 연산 자체가
E1 * 2^E2로 정의되기 때문입니다. E1 >> E2는 E1 / 2^E2 이고요. 유부호
정수형의 경우에는 무부호에 비해 추가적인 제약이 있습니다만. 정수형의 내부 표현
방법과는 무관합니다.
뭐, 2를 곱하려고 <<를 쓰는 것은 별로 탐탁치 않게 생각하긴 합니다.
htna의 이미지

shift operation 그리고 이때의 one's complement에서의 특징으로 인해서...
<< 시에는 signed int의 경우에 음수이건 양수이건 E1 << E2 == E1 * 2^E2 의 특징을 보이게 됩니다.
하지만, >> 는 최상위 비트를 복사하여 빈곳에 자리를 채우는 형식을 취하고 있기에, E1 >> E2 == E1 / 2^E2의 결과를 보이게 됩니다.

Quote:
0000 0110 >> 1 => 0000 0011 : 6 >> 1 => 3 (최상위 비트를 복사하여 shift 함)
1111 1010 >> 1 => 1111 1101 : -3 >> 1 => -3 *** (최상위 비트를 복사하여 shift 함)
0000 0110 << 1 => 0000 1100 : 6 << 1 => 12
1111 1010 << 1 => 1111 0100 : -6 >> 1 => -12

만약 two's complement에서라면
<<, >> 의 경우 최상위 비트(sign bit)는 남겨두고 나머지 value bits만을 shift 연산을 취해야만,
E1 << E2 == E1 * 2^E2
E1 >> E2 == E1 / 2^E2
와 같은 결과를 얻을 수 있습니다.

Quote:
0000 0110 >> 1 => 0000 0011 : 6 >> 1 => 3
1000 0110 >> 1 => 1000 0011 : -3 >> 1 => -3 (최상위 비트를 적용시키지 말아야 함)
0000 0110 << 1 => 0000 1100 : 6 << 1 => 12
1000 0110 << 1 => 1000 1100 : -6 >> 1 => -12 (최상위 비트를 적용시키지 말아야 함)

더구나 이러한 경우에라도 "1000 0001 >> 1", "1100 0001 << 1"과 같은 결과의 저장은 "1000 000" 으로가 아니라 "0000 0000"로 저장해 주어야 하기 때문에
복잡도가 더욱 커지게 됩니다.

물론 C/C++ compiler가 이러한 연산을 알아서 여러 단계에 처리하도록 할 수 있는것도 사실입니다.
하지만, one's complement의 경우 한번의 shift연산으로 처리가 가능합니다만.
two's complement의 경우에는 assmbler로 한번에 처리할 수 없다는것이 당연하다고 봅니다.
물론 해당 CPU의 assmbler가 저러한 연산을 지원하도록 필요한 명령어가 모두 예약되어 있다면 가능하겠지만요...

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

자꾸 딴지를 거는 것 같아서 죄송하지만 그렇지 않습니다. E1 << E2의 연산 자체가
E1 * 2^E2로 정의되기 때문입니다. E1 >> E2는 E1 / 2^E2 이고요. 유부호
정수형의 경우에는 무부호에 비해 추가적인 제약이 있습니다만. 정수형의 내부 표현
방법과는 무관합니다.
뭐, 2를 곱하려고 <<를 쓰는 것은 별로 탐탁치 않게 생각하긴 합니다.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

doldori의 이미지

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

htna wrote:
<< 시에는 signed int의 경우에 음수이건 양수이건 E1 << E2 == E1 * 2^E2 의 특징을 보이게 됩니다.

만약 E1이 0이거나 양수이고 << 연산의 결과가 E1의 형으로 표현 가능하면
연산 결과는 E1 * 2^E2입니다. 그 이외의 경우 연산 결과는 정의되지 않습니다.

htna wrote:
하지만, >> 는 최상위 비트를 복사하여 빈곳에 자리를 채우는 형식을 취하고 있기에, E1 >> E2 == E1 / 2^E2의 결과를 보이게 됩니다.

E1이 0이거나 양수일 때만 그렇습니다. E1이 음수이면 >> 연산의 결과는 구현체
정의(implementation-defined)입니다. 따라서

htna wrote:
1111 1010 >> 1 => 1111 1101 : -3 >> 1 => -3 *** (최상위 비트를 복사하여 shift 함)

이 결과는 구현체 정의입니다.

htna wrote:
1111 1010 << 1 => 1111 0100 : -6 >> 1 => -12

이 결과는 정의되지 않습니다.

htna wrote:
더구나 이러한 경우에라도 "1000 0001 >> 1", "1100 0001 << 1"과 같은 결과의 저장은 "1000 000" 으로가 아니라 "0000 0000"로 저장해 주어야 하기 때문에
복잡도가 더욱 커지게 됩니다.

그래서 비트 연산에 유부호 정수형을 쓰면 골치가 아파집니다. 무부호에 비해서
제약이 많지요. 저는 이런 제약을 비트 연산에는 유부호 정수형을 쓰지 말라는
의도로 이해하고 있습니다.

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

htna의 이미지

한 예로, x가 int일때 x+1 이 int가 허용하는 범위내에서는 x+1을 보장하는것은 당연합니다.
굳이 이와같은 극한의 경우로 한정지을 필요는 없을것으로 생각합니다.

doldori wrote:
이후의 얘기는 모두 유부호 정수형을 전제로 하겠습니다.
htna wrote:
<< 시에는 signed int의 경우에 음수이건 양수이건 E1 << E2 == E1 * 2^E2 의 특징을 보이게 됩니다.

만약 E1이 0이거나 양수이고 << 연산의 결과가 E1의 형으로 표현 가능하면
연산 결과는 E1 * 2^E2입니다. 그 이외의 경우 연산 결과는 정의되지 않습니다.

모든 operation은 구현체 정의에 달려있습니다.. 만...
1's complement에서 signed int type의 <<, >> 시에, 기본적으로 삽입되어야 할 자리에 0이 들어가지만,
최상위 비트에 대해서는 이전의 최상위 비트를 복사하는것을 기본으로 알고 있습니다.
그에대한 실 예를 보이고 이때
E1 << E2 == E1 * 2^E2
E1 >> E2 == E1 / 2^E2
가 잘 동작한다는 것을 예로 보인것입니다.
충분히 아시는 내용일것이라 생각이 들어 예를 들 필요가 없을 것이라 생각했지만, 논란의 여지가 생기지 않을까 하여 좀 구체적으로 설명했습니다만...
역시나, "구현체 정의"라고 언급하시는군요...
혹시 이와 다르게 동작하는 컴파일러나 CPU 아시는 분 있나요 ???

doldori wrote:
htna wrote:
하지만, >> 는 최상위 비트를 복사하여 빈곳에 자리를 채우는 형식을 취하고 있기에, E1 >> E2 == E1 / 2^E2의 결과를 보이게 됩니다.

E1이 0이거나 양수일 때만 그렇습니다. E1이 음수이면 >> 연산의 결과는 구현체
정의(implementation-defined)입니다. 따라서
htna wrote:
1111 1010 >> 1 => 1111 1101 : -3 >> 1 => -3 *** (최상위 비트를 복사하여 shift 함)

이 결과는 구현체 정의입니다.
htna wrote:
1111 1010 << 1 => 1111 0100 : -6 >> 1 => -12

이 결과는 정의되지 않습니다.

sign bit를 사용하는 2's complement의 CPU에서 "-1 >> 1" 와 같은 쪽에서 처리가 어려울 수 있다는 것을 예로 들기 위해서 다음과 같은 예제를 사용한것입니다.
물론 1's complement인지 2's complement인지 신경쓰지 않고 shift연산을 하기 위해서는 unsigned 변수를 사용하는것이 좋다는 것에는 다들 충분히 공감하시겠지만.
"이런 제약을 비트 연산에는 유부호 정수형을 쓰지 말라는 의도"로 얘기한 것은 아닙니다. 충분히 환경이 정해진 경우라면, 충분히 필요하다면 사용해야 되니깐요.

doldori wrote:
htna wrote:
더구나 이러한 경우에라도 "1000 0001 >> 1", "1100 0001 << 1"과 같은 결과의 저장은 "1000 000" 으로가 아니라 "0000 0000"로 저장해 주어야 하기 때문에
복잡도가 더욱 커지게 됩니다.

그래서 비트 연산에 유부호 정수형을 쓰면 골치가 아파집니다. 무부호에 비해서
제약이 많지요. 저는 이런 제약을 비트 연산에는 유부호 정수형을 쓰지 말라는
의도로 이해하고 있습니다.

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

요즘 2's complement를 사용하는 CPU가 얼마나 있을지 궁금합니다.
머 본적이 없다고 하는게 맞을듯 하네요.. (^^; 너무 x86 machine에 길들여져서 인가.. 혹시 이와같은 CPU 아시는 분 있나요 ?)
물론 2's complement환경일 수 있다고 생각해서 작업하는것이 당연한 일입니다만...
물론 이러한 연산을 거의 사용하지 않고, 또한 가능하면 사용하지 않는것이 좋습니다만.
이러한 기본적인 내용은 알아두는것도 나쁘지는 않다고 생각합니다.
정의된다, 정의되지 않는다 라고 엄밀하게 말할 수도 있겠지만, 이런경우에는 배경지식을 알아두는것도 좋지 않나요 ?
이러한 전제가 필요한 경우가 없다고.. 단정지을 수는 없으니깐요...

저 역시 게시판의 성격에 맞지 않을수 있다고 생각합니다만...
이것 역시 재밌지 않습니까.. 그렇다고 새로이 게시판을 여는것도 그렇구요. ^^

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

doldori의 이미지

htna wrote:
doldori wrote:
이후의 얘기는 모두 유부호 정수형을 전제로 하겠습니다.
htna wrote:
<< 시에는 signed int의 경우에 음수이건 양수이건 E1 << E2 == E1 * 2^E2 의 특징을 보이게 됩니다.

만약 E1이 0이거나 양수이고 << 연산의 결과가 E1의 형으로 표현 가능하면
연산 결과는 E1 * 2^E2입니다. 그 이외의 경우 연산 결과는 정의되지 않습니다.

한 예로, x가 int일때 x+1 이 int가 허용하는 범위내에서는 x+1을 보장하는것은 당연합니다.
굳이 이와같은 극한의 경우로 한정지을 필요는 없을것으로 생각합니다.

이 말씀이 위의 문맥과 어떻게 연결이 되는지 잘 모르겠습니다. 부연 설명 부탁합니다.

htna wrote:
모든 operation은 구현체 정의에 달려있습니다.. 만...

혹시나 해서 확인을 하겠습니다. 구현체 정의(implementation-defined)는 꽤
구체적으로 정의된 용어입니다. 표준에 정의된 모든 연산은 어떤 방식으로든 구현을
하겠지만, 그것을 모두 구현체 정의라고 부르지는 않습니다. 구현체 정의는 표준에서
각 구현체에게 선택을 하도록 일임한 사항이고 그에 대해서는 각 구현체에서 문서화
하도록 규정하고 있습니다. 예를 들어 INT_MAX가 얼마가 될 것인가는 구현체 정의
사항입니다. -1 >> 1의 결과 역시 각 구현체의 선택이며 표준은 그 이상의 보장을
하지 않습니다. 1 >> 1과는 성격이 다르지요. 따라서 "모든 operation은 구현체
정의에 달려있다"는 말씀은 오해의 소지가 있습니다.

htna wrote:
1's complement에서 signed int type의 <<, >> 시에, 기본적으로 삽입되어야 할 자리에 0이 들어가지만,
최상위 비트에 대해서는 이전의 최상위 비트를 복사하는것을 기본으로 알고 있습니다.
그에대한 실 예를 보이고 이때
E1 << E2 == E1 * 2^E2
E1 >> E2 == E1 / 2^E2
가 잘 동작한다는 것을 예로 보인것입니다.

>>의 예는 시험하신 환경에서 구현체는 그러한 선택을 했다는 것 이상의 사실을
말해 주지는 못합니다. 다른 환경에서는 다른 선택을 할 가능성도 충분히 있습니다.
게다가 -1 << 1, INT_MAX << 1의 결과는 정의되지 않습니다. 실행할 때마다
다른 결과를 보여도 하소연할 곳조차 없다는 뜻입니다.

htna wrote:
"이런 제약을 비트 연산에는 유부호 정수형을 쓰지 말라는 의도"로 얘기한 것은 아닙니다. 충분히 환경이 정해진 경우라면, 충분히 필요하다면 사용해야 되니깐요.

아, 그건 누가 그런 얘기를 했다는 뜻이 아니라, 표준이 유부호형에 대해 보장하는 범위가
무부호형에 비해 상대적으로 적다는 사실을 제가 그런 의도로 받아들였다는 뜻입니다.
구현체 정의 사항에 의존하는 코드가 합리적인 선택이 되는 경우도 분명 있습니다.
예를 들어 Windows에서만 쓰일 것이 확실한 코드라면 VC++이나 MinGW의
구현체 정의 사항에 의존하거나 특정 hack을 사용하는 것이 성능상으로 더 좋을
수도 있습니다. 다른 대안이 없을 수도 있고요. 제가 지금까지 표준을 들먹이면서
좀 답답하게(?) 군 것은 이식성에 중점을 두었기 때문입니다.

htna wrote:
요즘 2's complement를 사용하는 CPU가 얼마나 있을지 궁금합니다.
머 본적이 없다고 하는게 맞을듯 하네요.. (^^; 너무 x86 machine에 길들여져서 인가.. 혹시 이와같은 CPU 아시는 분 있나요 ?)

어? x86은 2의 보수를 쓰지 않나요? 저는 1의 보수를 쓰는 환경을 접해보지 못했는데...

htna wrote:
물론 2's complement환경일 수 있다고 생각해서 작업하는것이 당연한 일입니다만...
물론 이러한 연산을 거의 사용하지 않고, 또한 가능하면 사용하지 않는것이 좋습니다만.
이러한 기본적인 내용은 알아두는것도 나쁘지는 않다고 생각합니다.
정의된다, 정의되지 않는다 라고 엄밀하게 말할 수도 있겠지만, 이런경우에는 배경지식을 알아두는것도 좋지 않나요 ?
이러한 전제가 필요한 경우가 없다고.. 단정지을 수는 없으니깐요...

물론입니다. 아는 것이 좋으면 좋았지 나쁠 리는 없지요. 그런데 거기에 함정이
있더라고요. 어떤 경우에는 그 배경 지식에 치중한 나머지 그것이 쉽게 일반화될
성질의 것이 아니라는 점을 잊게 되더군요. 그래서 제가 항상 주장하는 것이
"먼저 언어의 정의를 숙지한 후에 그것이 어떻게 구현되는지 관찰하자"입니다.

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

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

Quote:
top-posting이 뭡니까?

읽기 불편하니까요.
Quote:
그게 왜 안좋죠?
kkb110의 이미지

퀴즈올리길 정말 잘했습니다 너무 재밌어서 미치겠군요 ! :twisted:

그리고 코드 놀이터에서 코드에 대한 하드코어한 토론이 이루어지는것이
왜 적당하지 않으며 심각한 토론이 왜 나쁜지 모르겠군요! 8)

저는 재밌어서 미치겠습니다. 다른분들은 그렇지 않나요? :D

doldori
htna

두분 토론 잘 보고 있습니다.

한분은 엄격한 표준에 대해 주로 이야기하시고 한분은 실용적인 면을 이야기하고 계시군요!
물론 표준을 지키는것은 좋습니다. 하지만 두분이 말씀하셨듯이 비표준의 코드도 나름대로 미학이 있고 존재해야할 엄연한 이유가 있습니다.
둘다 가치있고 저에게는 엄격한 표준에 근거한 코드나 덜엄격해도 나름대로의 미학을 연출해내는 코드 둘다 너무 흥미롭습니다.

이예기는 이쯤하고..

htna님이 2의보수와 1의보수를 잠시 햇갈리셨나봅니다 ㅋㅋ

VC7에서는 각종 연산을 이렇게 만듭니다. 흥미롭네요. 2의 보수에서도 int는 >>연산이 명령어 한개가 아니군요.


//signed int t

t << 1;
shl         eax,1 

t * 2;
shl         eax,1 


t >> 1;
sar         eax,1

t / 2;
cdq              
sub         eax,edx 
sar         eax,1 

t / 4;
cdq              
and         edx,3 
add         eax,edx 
sar         eax,2 

t / 8;
cdq              
and         edx,7 
add         eax,edx 
sar         eax,3 



//unsigned int t

t / 2;
shr         eax,1 

t는 eax에 들어있다고 가정하는것이구요.
cdq는 edx레지스터의 모든 비트들을 eax의 레지스터의 부호비트로 가득 채우는겁니다.
음수라면 11111111... 양수라면 00000000...

signed int t 일때 /2의 연산이 cdq까지 들먹이며 저렇게 되는 이유는 아마 -1일경우에 0으로 되야하기때문인것같습니다.
/4일경우에는 t값이 -3일경우에도 0이되어야하고.. 흠.. 흥미롭네요 이거

그리고 질문이 있는데
제가 알기로 역시 엄격한 표준문서에 의하면 int값의 숫자에 의한 value비트의 작동방식은 전혀 정의되지 않았는데 맞는지요?
그렇다면 01011011 이라는 비트값도 문서에 의하면 0을 나타낼수도 있는거겠군요?

그리고 padding bit, sign bit, value bit 의 순서도 정의되지 않았다면
sign bit가 최하위에 올수도 있겠네요?? -_-;;;

제질문은 여기까지구요

벤치마킹은 꼭 제대로 해봐야겠습니다 ㅋㅋ 함수들이 워낙 작아서... 그것도 함수호출 오버헤드에 의해 차이가 오차범위에 묻힐만큼 작지만.
안해보고는 못지나가겠습니다 ㅋㅋ

bugiii의 이미지

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

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

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

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

doldori의 이미지

kkb110 wrote:
그리고 질문이 있는데
제가 알기로 역시 엄격한 표준문서에 의하면 int값의 숫자에 의한 value비트의 작동방식은 전혀 정의되지 않았는데 맞는지요?
그렇다면 01011011 이라는 비트값도 문서에 의하면 0을 나타낼수도 있는거겠군요?

흐... 저를 제대로 공부시키시네요. ^^;
결론을 먼저 얘기하면 (signed char)01011011은 0을 나타내는 비트 패턴이 될
수 없습니다. 이유는 위에서 인용하신 정수형의 표현에 나와 있습니다. 관련되는
부분만 다시 인용하죠.
Quote:
6.2.6.2/1
For unsigned integer types, [...] If there are N value bits, each bit shall
represent a different power of 2 between 1 and 2^N-1, [...]

6.2.6.2/2
For signed integer types, [...] Each bit that is a value bit shall have
the same value as the same bit in the object representation of the
corresponding unsigned type[...].


(signed char)01011011에서 1에 해당하는 비트 중 적어도 4개는 value bit에
해당할 것이고 그것들이 2의 멱승(power)을 나타내므로 0이 될 수 없습니다.

kkb110 wrote:
그리고 padding bit, sign bit, value bit 의 순서도 정의되지 않았다면
sign bit가 최하위에 올수도 있겠네요?? -_-;;;

네, 그렇습니다. 사실은 저도 그런 환경은 접해보지 못했습니다. 다만 그 가능성은
항상 열려 있다고 봐야겠죠.
htna의 이미지

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:       }

doldori wrote:
이 말씀이 위의 문맥과 어떻게 연결이 되는지 잘 모르겠습니다. 부연 설명 부탁합니다.

"0111 1111 1111 1111 << 1" 과같이 극한의 경우가 아니고는 "양수 << 1" 과 같은 결과가 보장되는것은 당연하죠.
같은 의미로 ""0111 1111 1111 1111 + 1" 과 같이 극한의 경우가 아니고는 "양수 + 1"과 같은 결과가 보장되는 것은 당연하죠.
다른의미로 그 한계를 넘어서는 범위에 대해서는 정의되지 않았겠죠..
("0111 1111 1111 1111"는 signed type을 얘기한 것입니다..)
이걸 설명해달라고 하신것인지...

doldori wrote:
혹시나 해서 확인을 하겠습니다. 구현체 정의(implementation-defined)는 꽤
구체적으로 정의된 용어입니다. 표준에 정의된 모든 연산은 어떤 방식으로든 구현을
하겠지만, 그것을 모두 구현체 정의라고 부르지는 않습니다. 구현체 정의는 표준에서
각 구현체에게 선택을 하도록 일임한 사항이고 그에 대해서는 각 구현체에서 문서화
하도록 규정하고 있습니다. 예를 들어 INT_MAX가 얼마가 될 것인가는 구현체 정의
사항입니다. -1 >> 1의 결과 역시 각 구현체의 선택이며 표준은 그 이상의 보장을
하지 않습니다. 1 >> 1과는 성격이 다르지요. 따라서 "모든 operation은 구현체
정의에 달려있다"는 말씀은 오해의 소지가 있습니다.

물론 INT_MAX가 얼마가 될 것인가는 구현체 정의 입니다만, 32bit machine에서 UINT_MAX는 4294967295임을 의심하는 사람이 없을것입니다.
혹시 32bit machine에서 UINT_MAX가 4294967295가 아니라고 생각하시는건 아니죠 ?
intel 계열이든 amd 계열이든...

doldori wrote:

Quote:
6.2.6.2/1
For unsigned integer types, [...] If there are N value bits, each bit shall
represent a different power of 2 between 1 and 2^N-1, [...]

6.2.6.2/2
For signed integer types, [...] Each bit that is a value bit shall have
the same value as the same bit in the object representation of the
corresponding unsigned type[...].


(signed char)01011011에서 1에 해당하는 비트 중 적어도 4개는 value bit에
해당할 것이고 그것들이 2의 멱승(power)을 나타내므로 0이 될 수 없습니다.

질문 있습니다. 제가 영어를 좀 잘 못해서 그런데요..
위에 인용문에 4라는 숫자는 어디서 나왔는지 모르겠군요..
저 표준에 의한 signed integer에서는 0000 0011을 3으로 정의하고 있지만, 이는 어디까지나 하드웨어적인 공통사항에 근거한 결정일 뿐입니다.
이후에 (머 이런일은 없을것이라 보이지만..) 1100 0000을 3으로 정의하도록 하는 CPU가 일반화 된다면 저 표준 또한 바뀌어야 겠지요...
signed integer또한 구현체 정의다 라고...
kkb110님의 말의 의도는 너무 엄격한 표준으로는 어떠한 것도 명확하게 정의되지 않는다라는 말씀하시기 위해 그런 얘를 들은것이 아닌가 생각합니다만..

doldori wrote:
kkb110 wrote:
그리고 padding bit, sign bit, value bit 의 순서도 정의되지 않았다면
sign bit가 최하위에 올수도 있겠네요?? -_-;;;

네, 그렇습니다. 사실은 저도 그런 환경은 접해보지 못했습니다. 다만 그 가능성은
항상 열려 있다고 봐야겠죠.


네 가능성은 열려있습니다. 가능성은요.. 하지만 그렇게 될 일은 없어보이는군요... 적어도 몇년간은요...

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

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

htna의 이미지

//signed int t 

t << 1; 
shl         eax,1 

t * 2; 
shl         eax,1 


t >> 1; 
sar         eax,1 

t / 2; 
cdq              
sub         eax,edx 
sar         eax,1 

t / 4; 
cdq              
and         edx,3 
add         eax,edx 
sar         eax,2 

t / 8; 
cdq              
and         edx,7 
add         eax,edx 
sar         eax,3 



//unsigned int t 

t / 2; 
shr         eax,1 

이것에 대해서는 compiler가 알아서 코드 최적화를 해 주었다고 바라보는게 맞을것 같군요..
일반적인 나누기 연산이라면 idiv assembler 명령어를 사용해야 할 것으로 보입니다. 하지만 이에비해 sar이 연산속도가 빠르기에 idiv 대신에 sar로 연산을 하도록 만들어졌다고 보여지네요..

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

doldori의 이미지

htna wrote:
doldori wrote:
(signed char)01011011에서 1에 해당하는 비트 중 적어도 4개는 value bit에
해당할 것이고 그것들이 2의 멱승(power)을 나타내므로 0이 될 수 없습니다.

질문 있습니다. 제가 영어를 좀 잘 못해서 그런데요..
위에 인용문에 4라는 숫자는 어디서 나왔는지 모르겠군요..

별 게 아니고 01011011에서 1이 5개인데 그 중에서 하나는 부호 비트일 수
있으므로 적어도 4개라고 한 것입니다. 이 부분은 저도 자신이 없는데, 어쨌든
이 비트 패턴이 0을 표현할 수 없다는 점은 확실합니다.

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

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

htna의 이미지

doldori wrote:
htna wrote:
doldori wrote:
(signed char)01011011에서 1에 해당하는 비트 중 적어도 4개는 value bit에
해당할 것이고 그것들이 2의 멱승(power)을 나타내므로 0이 될 수 없습니다.

질문 있습니다. 제가 영어를 좀 잘 못해서 그런데요..
위에 인용문에 4라는 숫자는 어디서 나왔는지 모르겠군요..

별 게 아니고 01011011에서 1이 5개인데 그 중에서 하나는 부호 비트일 수
있으므로 적어도 4개라고 한 것입니다. 이 부분은 저도 자신이 없는데, 어쨌든
이 비트 패턴이 0을 표현할 수 없다는 점은 확실합니다.

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

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


저또한 재밌었습니다.
간만에 예전에 배웠던 지식의 기억을 더듬느라.. ^^;;
각자 이게 맞느니 저게 맞느니 얘기는 해도 실제로 사용하는건 비슷할겁니다.. ^^

음. 그러고보니 여기가 코드놀이터군요...
^^;;;

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

kkb110의 이미지

doldori님 자세한답변감사합니다 ^^
사실 제가 지금짜고있는게 그런거에 좀 민감한 주제라 제가 관심히 좀 많아요 ^^;

코드들을 정밀하게 측정해보았습니다. 클럭이며 약간의 상수 오버헤드가 포함되있습니다.
kkb110 : 16
morris : 16
htna : 18
doldori : 18

정말 근소한 차이군요 하하 ㅋㅋ

htna님 제가 /2와 >>1를 언급한것은 일반적인 2의 보수 환경에서도 int타입에대하여 /2와 >>1가 정확하게 같게 동작하지 않는단걸 말하고자한겁니다.

t >> 1; 
sar         eax,1 

t / 2; 
cdq              
sub         eax,edx 
sar         eax,1 

-1을 /2하면 0이되겠지만 >>1을 하면 -1이될테니깐요! 흠..

그리고 '코드 놀이터'라는곳 원래 이런토론 하라고 만들어놓은곳 아니였나요? -_-;; 포럼에서 해야하나...
http://bbs.kldp.org/viewtopic.php?t=52828
이글읽고서 코드놀이터에 이런글도 적합하다고 생각했었는데;;

beta의 이미지

a+b의 사용이 탈락이라는데 동의할수 없습니다. ^^;
그리고 토론 재미있네요. 이래야 배우는것이 있지 않겠습니까? 감사할 따름입니다.

     12 int _test_overflow_when_integer_addition( int a, int b )
     13 {
     14     return (( (a & b & ~(a+b)) | (~a & ~b & (a+b)) ) < 0) ;
     15 }

사칙연산에 대해 전부하면 하면 잼있을꺼 같네요. ^^;

발 담갔다. 이제 익숙해 지는길만이..

doldori의 이미지

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

beta wrote:
a+b의 사용이 탈락이라는데 동의할수 없습니다. ^^;

그 이유도 밝혀주시면 좋겠습니다.

beta wrote:
사칙연산에 대해 전부하면 하면 잼있을꺼 같네요. ^^;

그렇겠군요. 쉬운 것부터 해볼까요?
// 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;
}

뺄셈과 나눗셈에 대해 이렇게 처리하는 것이 옳은 방법일까요?
(서로 관련이 있는 문제임.)
kkb110의 이미지

beta님 코드도 측정해보니 18클럭으로 나오네요 ^^
그리고 doldori님이 올려주신 뺄셈과 나눗셈은 둘다 옮아보이는군요.
곱셈의경우는 되게 재밌을것같습니다.. 한번 연구를..

kane의 이미지

// 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;
}

일까요?

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

익명 사용자의 이미지

kkb110 wrote:
beta님 코드도 측정해보니 18클럭으로 나오네요 ^^
그리고 doldori님이 올려주신 뺄셈과 나눗셈은 둘다 옮아보이는군요.
곱셈의경우는 되게 재밌을것같습니다.. 한번 연구를..

클럭 계산 어떻게 하는 건가요?
kkb110의 이미지

inline unsigned int getcycle() 
{ 
   __asm 
   { 
      cpuid 
      rdtsc 
   } 
} 

클럭재는 함수는 이건데요.. 그냥 정확히 클럭값을 반환해줍니다
측정하려는것을 루프에 담고 돌리기전에측정하고 돌린후에 측정해서 빼면 됩니다. 근데 저것자체가 보통 몇백클럭을 먹어서 -_-; 십만 백만번이상은 돌려야되구요. 제가 금방 측정한것은 루프에다가 그냥 함수호출하게 만들어서 측정했습니다. 루프돌릴때마다 조금씩 다른값이 나오던데.. 계속 돌려보니 코드마다 일정한 하한이 있는것같더라구요.. 18.0333 , 18.1585, 18.1749 이런식으로요.. 스레드전환이나 기타 오버헤드가 있어서 시간이 늘어났으면 늘어났지 줄어들진 않을거란 판단하에 정확한 값이라고 생각하게되었습니다 흠;;

그리고 뺄셈의 오버플로우 검출코드에서 보니까 kane님이 작성하신대로 빼려는수가 int값으로 표현할수있는 가장 작은 음수라면 미묘해질것같네요

부호전환을위해 2의보수를 사용한다고하고..
1byte의 예로 들면
1000 0000 의 2의 보수는 1000 0000 자기 자신의 수가 되니까요 -_-;;

htna의 이미지

이거 점점 재밌어지는군요...

그럼 곱셈의 것은 어떻게 되나 함 볼까요.. ?
곱셈에 대해서는 좀 어렵군요..
차근차근 시작해보죠. 일단 a, b를 양수로 만들고 시작합니다.
음수와 양수의 허용범위의 오차는 1 이죠 ???
그정도면 INT_MIN을 절대값 2이상의수로 곱하면 무조건 overflow/underflow이기에 이를 걸러내기 위한 코드가 있어야 겠지만.. 머 알고리즘(이라고 하기에는 좀 그렇죠??)만 본다고 할때.. 간단히 건너띄겠습니다.
또한, int의 최상위 bit가 0x8000 이라고 가정 합니다.
참고로, 컴파일러로 아직 돌려보지는 않은 코드 입니다. 그냥 머릿속으로만.. ^^;
귀차니즘의 압박이.. 집에서는 VC를 안띄우는 편이라서..

bool OutOfRangeForMultiplication(int a, int b)
{
    a = (a < 0) ? (-a) : (a);
    b = (b < 0) ? (-b) : (b);
    int s = 0; // sum
    while(b != 0) {
        if((b & 1) != 0) {
            a = a << 1; if(a & 0x8000) return true;
            s = s + a; if(s & 0x8000) return true;
        }
        b = b >> 1;
    }
    return false;
}

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

morris의 이미지

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

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

ㅎㅎㅎ

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를 호출하니 느리겠지만

귀찮아서 -_-;

htna의 이미지

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

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

ㅎㅎㅎ

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를 호출하니 느리겠지만

귀찮아서 -_-;


머 이대로 걍 나가는것도...
쓰레드를 새로 달면, 그만큼 인지대고 떨어지는 것도 있을테고.
참여율도 초기화되지 않을까 합니다만..

a와 b의 sign bit를 제거하는것이 큰 의미를 지니지 않을듯 합니다.
0xFFFF(-1)의 sign bit를 제거하게 되면 0x7FFF(MAX_INT)가 되기 때문이죠...
b가 0xFFFF(-1)일때 sign bit를 제거한 0x7FFF(MAX_INT)의 값으로 a를 배수하게 되면.....
음.. a의 절대값이 2이상일때에는 무조건 overflow/underflow가 나오도록 결과가 나오게 될테구..
음.. 이는 정상이 아니겠죠 ?

이쯤의 논의가 된다면...
STL을 이용해서 이식성과 가독성이 좋읕 코드를 만든다는게 좀 어려울 수도 있겠군요.. 효율성이란 것을 같이 고려한다면...
어쩌면요.. ^^
제 생각이 틀렸을 수도 있겠지만... ^^;

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

morris의 이미지

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;
}

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

이런 실수를...

doldori의 이미지

kane wrote:
// 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;
}

일까요?

제가 처음에 제시한 코드에 문제가 있음을 알고 계시는군요. 뺄셈의 경우 2의 보수를
사용하는 환경에서는 b == INT_MIN일 때 문제가 됩니다. -INT_MIN > INT_MAX가
되어 int의 표현 범위를 벗어나죠. 나눗셈의 경우 INT_MIN / (-1)일 때도 같은
문제가 발생하고요.

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

음수의 나눗셈이라고 해서 근본적으로 달라질 것은 없습니다. 우리가 상식적으로
알고 있는 대수 관계가 그대로 성립하죠. (나머지 연산 %에서는 또다시 골치 아픈
문제가 생깁니다만.)

그래서 제가 생각하는 코드는 이렇습니다.

bool OutOfRangeForSubtraction(int a, int b) 
{ 
    return (b < 0 && a > INT_MAX + b) || (b > 0 && a < INT_MIN + b); 
} 

bool OutOfRangeForDivision(int a, int b) 
{ 
    assert(b != 0);
    return INT_MIN != -INT_MAX && a == INT_MIN && b == -1;
} 

int만을 고려한 코드이지만 모든 유부호 정수형에 대해 적용할 수 있는 템플릿으로도
쉽게 변경할 수 있습니다.

ps. 논리적인 오류가 있어 정정했습니다.

htna의 이미지

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

혹시 아닌가요 ?

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

kane의 이미지

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

음수의 나눗셈이라고 해서 근본적으로 달라질 것은 없습니다. 우리가 상식적으로
알고 있는 대수 관계가 그대로 성립하죠. (나머지 연산 %에서는 또다시 골치 아픈
문제가 생깁니다만.)

'/' 연산과 'mod' 연산 사이에서 헤매고 있었습니다. ㅠㅠ

// assume b!=0 and not (a>0, b<0)
bool OutOfRangeForModulus(int a, int b) 
{ 
    return false; 
}

일까요?
htna의 이미지

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

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

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

Quote:
Microsoft Visual FoxPro Language Reference

MOD( ) FunctionSee Also
% Operator
Divides one numeric expression by another numeric expression and returns the remainder.

MOD(nDividend, nDivisor)
Return Values
Numeric

Parameters
nDividend
Specifies the dividend. The number of decimal places in nDividend determines the number of decimal places in the return value.
nDivisor
Specifies the divisor. A positive number is returned if nDivisor is positive, and a negative number is returned if nDivisor is negative.
Remarks
The modulus function MOD( ) and the % operator return identical results.

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

doldori의 이미지

전에 올린 글에 잘못된 내용이 있어서 정정합니다.

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

음수의 나눗셈이라고 해서 근본적으로 달라질 것은 없습니다. 우리가 상식적으로
알고 있는 대수 관계가 그대로 성립하죠. (나머지 연산 %에서는 또다시 골치 아픈
문제가 생깁니다만.)

이 말은 틀렸습니다. 다음은 C Traps and Pitfalls, Andrew Koenig에 나오는
내용을 요약한 것입니다.

/와 % 연산의 성질
1. (a/b) * b + a % b == a이다.
2. a의 부호가 바뀌면 a / b의 부호만 바뀌고 절대값은 같다.
3. b가 양수일 때 0 <= a % b && a % b < b 이다.

표준에서 보장하는 것은 1뿐입니다. 그리고 불행히도 세 개의 성질을 모두 만족하는
것은 불가능합니다. 3 / 2 == 1이고 3 % 2 == 1이죠. (-3) / 2는 어떻게 될까요?
2.에 따르면 (-3) / 2 == -1이 되어야 합니다. 그리고 1.과 2.를 만족하려면
(-3) % 2 == -1이어야 하는데 그러면 3.을 만족할 수 없습니다. 다른 방법으로
3.을 만족하려면 (-3) % 2 == 1이어야 하고 1.과 3.을 만족하려면 (-3) / 2 == -2가
되어야 하므로 2.를 만족할 수 없습니다. 즉 (-3) / 2의 값은 -1일 수도 있고 -2일
수도 있습니다.
1.은 표준에서 강제하는 것이므로 반드시 만족해야 하고 추가로 2.를 만족할지
3.을 만족할지는 각 구현체마다 다릅니다. 네, 골치 아픕니다. -_-;
그러나 어떤 경우에도 나머지 연산 %에서 오버플로우가 날 수는 없겠죠.

곱셈의 오버플로우 검사하는 코드를 처음에 이렇게 생각했는데

bool OutOfRangeForMultiplication(int a, int b) 
{ 
    return (b > 0 && (a < INT_MIN / b || a > INT_MAX / b)) ||
           (b < 0 && (a > INT_MIN / b || a < INT_MAX / b));
}

이게 쓸모없게 되는군요. T.T
kane의 이미지

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

kane의 이미지

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

일반적으로 mod 연산을 얘기할 때, 반드시 그 결과 값이 양수이거나 음수여야 하는 건 아니라고 알고 있습니다. 단지 결과 값이 양수인게 쓰기 편하기 때문에 많이 사용하는 걸로 알고 있습니다.
singlet의 이미지

#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
$ 
doldori의 이미지

singlet wrote:
#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
$ 

희한한 결과로군요. VC++에서도 마찬가지 현상을 보입니다.
그러니까 INT_MIN % -1에서 0으로 나누는 연산이 발생한다는 얘긴데
구현체의 버그가 아닐까 싶습니다.
htna의 이미지

구현체라면 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;

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

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

전웅의 이미지

doldori wrote:
singlet wrote:
#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
$ 

희한한 결과로군요. VC++에서도 마찬가지 현상을 보입니다.
그러니까 INT_MIN % -1에서 0으로 나누는 연산이 발생한다는 얘긴데
구현체의 버그가 아닐까 싶습니다.

구현제 버그는 아닙니다.

% 연산자의 결과는 / 연산자로 정의됩니다. 따라서 동일한 두 피연산자에
대해 / 연산자의 결과가 정의되지 않으면, % 연산자 역시 정의되지
않습니다.

signed zero 나 trap 을 쓰지 않는 two's complement representation
환경에서 |INT_MIN| == |INT_MAX|+1 입니다. 결국 INT_MIN / -1 이
정의되지 않기 때문에 INT_MIN % -1 도 정의되지 않습니다. 따라서 이
경우를 나머지 연산자에서 overflow 가 발생한 경우로 볼 수도 있습니다.

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

doldori의 이미지

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

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

htna의 이미지

하하 그렇군요..
컴파일러가 똑똑하다고 봐야 겠네요.
다음과 같은 코드가 overflow 없이 돌아간다고 하는건...
컴파일러가 똑똑하다기 보다..
컴파일러 만든는 VC개발자들의 노가다였을 듯 하네요..
^^

58:       int k = (INT_MIN) % -1;
004019FB   mov         dword ptr [ebp-18h],0

왜 변수로 mod 연산을 취할때만 overflow가 나는지..
이제야 감이 오네요..
좀 assembler를 들여다 봤으면 말끔히 해결될 것을..

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

kane의 이미지

doldori wrote:

/와 % 연산의 성질
1. (a/b) * b + a % b == a이다.
2. a의 부호가 바뀌면 a / b의 부호만 바뀌고 절대값은 같다.
3. b가 양수일 때 0 <= a % b && a % b < b 이다.

개인적으로 1, 3번을 선택하는게 바람직하다고 생각합니다. 그 쪽이 /, % 연산을 휠씬 자연스럽게 정의할 수 있기 때문입니다.
a/b의 결과를 내림하도록 하면, 자연스럽게 1, 3번을 만족시킬 수 있습니다.
하지만 2번은 내림, 올림, 반올림으로 정의되지 않습니다. 2번을 만족시키기 위해서는 a>0, b>0에서 정의된 a/b의 결과를 회전 이동시켜야 합니다.
2번을 선택하는 이유는 A + (-A) = 0 (즉, (a/b) + (-a/b) = 0)을 만족시키기 위해서 일겁니다. 저는 이게 실수 나눗셈의 성질을 정수 나눗셈에 그대로 적용시키려해서 생긴 문제라고 생각합니다. 실수 나눗셈과 정수 나눗셈을 나누어서 생각하는 쪽이 더 나은 것 같습니다.

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

참고: Integer Division in mathworld

doldori의 이미지

kane wrote:
doldori wrote:

/와 % 연산의 성질
1. (a/b) * b + a % b == a이다.
2. a의 부호가 바뀌면 a / b의 부호만 바뀌고 절대값은 같다.
3. b가 양수일 때 0 <= a % b && a % b < b 이다.

개인적으로 1, 3번을 선택하는게 바람직하다고 생각합니다. 그 쪽이 /, % 연산을 휠씬 자연스럽게 정의할 수 있기 때문입니다.
a/b의 결과를 내림하도록 하면, 자연스럽게 1, 3번을 만족시킬 수 있습니다.
하지만 2번은 내림, 올림, 반올림으로 정의되지 않습니다. 2번을 만족시키기 위해서는 a>0, b>0에서 정의된 a/b의 결과를 회전 이동시켜야 합니다.
2번을 선택하는 이유는 A + (-A) = 0 (즉, (a/b) + (-a/b) = 0)을 만족시키기 위해서 일겁니다. 저는 이게 실수 나눗셈의 성질을 정수 나눗셈에 그대로 적용시키려해서 생긴 문제라고 생각합니다. 실수 나눗셈과 정수 나눗셈을 나누어서 생각하는 쪽이 더 나은 것 같습니다.

논리적인 해설이군요. ^^ 선택의 문제라서 정답은 없긴 하지만요. 위에서는 빼먹고
말하지 않았는데 Andrew Koenig의 말에 따르면 1과 2를 택하는 구현이 많다고
합니다. 제가 시험해본 구현도 모두 그랬고요.
원래 주제로 돌아와서 표준만으로 유부호 정수형 곱셈의 오버플로우를 검사하는
방법이 있을지 모르겠습니다. 생각하다가 어지러워져서 포기했습니다. orz
htna의 이미지

kane wrote:
doldori wrote:

/와 % 연산의 성질
1. (a/b) * b + a % b == a이다.
2. a의 부호가 바뀌면 a / b의 부호만 바뀌고 절대값은 같다.
3. b가 양수일 때 0 <= a % b && a % b < b 이다.

개인적으로 1, 3번을 선택하는게 바람직하다고 생각합니다. 그 쪽이 /, % 연산을 휠씬 자연스럽게 정의할 수 있기 때문입니다.
a/b의 결과를 내림하도록 하면, 자연스럽게 1, 3번을 만족시킬 수 있습니다.
하지만 2번은 내림, 올림, 반올림으로 정의되지 않습니다. 2번을 만족시키기 위해서는 a>0, b>0에서 정의된 a/b의 결과를 회전 이동시켜야 합니다.
2번을 선택하는 이유는 A + (-A) = 0 (즉, (a/b) + (-a/b) = 0)을 만족시키기 위해서 일겁니다. 저는 이게 실수 나눗셈의 성질을 정수 나눗셈에 그대로 적용시키려해서 생긴 문제라고 생각합니다. 실수 나눗셈과 정수 나눗셈을 나누어서 생각하는 쪽이 더 나은 것 같습니다.

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

참고: Integer Division in mathworld


여기에서 b가 음수일 때의 얘기는 명확히 있지는 않군요...
다들 양수일때와, 임의의 정수일때를 언급하고 있으니깐요..

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

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

doldori의 이미지

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

그럴 리가요? @.@
제가 시험한 환경에서는 모두 -3 / 2 == -1, -3 % 2 == -1로 나오는데요.
3을 만족하지 않습니다.
htna의 이미지

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

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

WOW Wow!!!
Computer Science is no more about computers than astronomy is about telescopes.
-- E. W. Dijkstra

doldori의 이미지

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

위에서 말했듯이 책에서 인용한 것입니다.
이게 널리 통용되는 기준인지는 모르겠네요.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.