부호 없는 정수 곱셈 오버플로를 감지하려면 어떻게 해야 합니까?
a = c의 모든b 솔루션을 찾기 위해 C++로 프로그램을 작성하고 있었습니다.여기서 a, b, c는 모두 0-9의 숫자를 정확히 한 번 사용합니다.이 프로그램은 a와 b의 값을 루프하여 a, b 및b a에서 매번 디짓 카운트 루틴을 실행하여 디짓 조건이 충족되었는지 확인합니다.
단, 가 정수 제한을 오버플로하면b 스플리어스 솔루션이 생성될 수 있습니다.결국 다음과 같은 코드를 사용하여 확인하게 되었습니다.
unsigned long b, c, c_test;
...
c_test=c*b; // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test; // No overflow
오버플로우를 테스트하는 더 좋은 방법이 있나요?일부 칩에는 오버플로가 발생했을 때 내부 플래그가 설정되어 있는 것은 알고 있습니다만, C나 C++로 액세스 하는 것은 본 적이 없습니다.
서명된 오버플로는 C 및 C++에서 정의되지 않은 동작이므로 실제로 발생시키지 않고 검출해야 합니다.추가 전에 서명된 int 오버플로는 C/C++에서 서명된 오버플로 감지를 참조하십시오.
부호 없는 정수를 쓰시는군요정의상, C에서는(C++에 대해서는 모릅니다) 부호 없는 산술은 오버플로하지 않습니다.따라서 적어도 C의 경우 포인트는 무트입니다.
부호 있는 정수를 사용하면 일단 오버플로가 발생하면 정의되지 않은 동작(UB)이 발생하여 프로그램이 모든 작업을 수행할 수 있습니다(예: 렌더 테스트 미결).
#include <limits.h>
int a = <something>;
int x = <something>;
a += x; /* UB */
if (a < 0) { /* Unreliable test */
/* ... */
}
적합한 프로그램을 만들려면 해당 오버플로를 생성하기 전에 오버플로를 테스트해야 합니다.이 메서드는 부호 없는 정수에도 사용할 수 있습니다.
// For addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
// For subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;
// For multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
나눗셈의 경우(단,INT_MIN ★★★★★★★★★★★★★★★★★」-1한 경우 없습니다.INT_MIN ★★★★★★★★★★★★★★★★★」INT_MAX.
C23부터<stdckdint.h>에는 다음 3가지 기능성 매크로가 있습니다.
bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);
서 ''는type1,type2 ★★★★★★★★★★★★★★★★★」type3을 사용하다는 각각 그 를 a에 합니다.*result를 정확하게 수 type1는 "이러다"를 반환합니다true(''). 정밀도는 이후 한 거의 할 수 을 사용법계산 속도가 매우 빠르고 1990년대 초반 이후 사용 가능한 거의 모든 하드웨어에서 한두 가지 명령만으로 실행할 수 있습니다.)
OP의 예를 다시 쓰는 중:
unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
// returned non-zero: there has been an overflow
}
else
{
c = c_test; // returned 0: no overflow
}
c_test에는 모든 경우의 곱셈 결과가 포함되어 있습니다.
C23보다 훨씬 전에 GCC 5+ 및 Clang 3.8+는 같은 방식으로 동작하는 빌트인을 제공합니다.단, 결과 포인터는 처음에 전달되지 않고 마지막에 전달됩니다.__builtin_add_overflow,__builtin_sub_overflow ★★★★★★★★★★★★★★★★★」__builtin_mul_overflow은 또한 . 작은 가 있습니다.int.
unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
// returned non-zero: there has been an overflow
}
else
{
c = c_test; // returned 0: no overflow
}
Clang 3.4+는 고정 타입의 산술 오버플로우 빌트인을 도입했지만 유연성이 훨씬 떨어졌고 Clang 3.8은 오랫동안 사용 가능했습니다.찾다__builtin_umull_overflow더 편리한 새로운 대안에도 불구하고 이 방법을 사용해야 할 경우.
Visual Studio의 cl.exe에는 직접 동등한 항목이 없습니다.부호 없는 덧셈 및 뺄셈의 경우 다음을 포함합니다.<intrin.h> 하면 '어느 정도'를 할 수 .addcarry_uNN ★★★★★★★★★★★★★★★★★」subborrow_uNNNN'과 ) .addcarry_u8 ★★★★★★★★★★★★★★★★★」subborrow_u64)의 둔감합니다 : ) 그시 ). ). ). ). ). ). ). ). ). ). ). ). ). ). ). ). ). 。
unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);
c_in/b_in는 입력 시 반송/반송 플래그, 반환 값은 출력 시 반송/반송 플래그입니다.서명된 연산 또는 곱셈에 해당하는 항목이 없는 것 같습니다.
그렇지 않으면, Clang for Windows는 현재 가동 준비가 되어 있기 때문에(Chrome에 충분히 적합), 그것도 옵션이 될 수 있습니다.
여기에서는, 적어도 덧셈의 오버플로를 검출할 수 있습니다.이것에 의해, 곱셈, 나눗셈, 거듭제곱이 가능하게 됩니다.
프로세서가 값을 0으로 되돌리고 C/C++가 특정 프로세서에서 추상화되기 때문에 다음과 같은 작업을 수행할 수 있습니다.
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);
이것에 의해, 1개의 오퍼랜드가 제로인 경우와 1개의 오퍼랜드가 제로인 경우, 오버플로는 잘못 검출되지 않고, 이전에 제시된 많은 NOT/XOR/AND/테스트 조작보다 큰폭으로 고속이 됩니다.
지적한 바와 같이, 이 접근방식은 다른 보다 정교한 방법보다 낫지만 여전히 최적입니다.다음은 최적화가 포함된 원래 코드의 개정판입니다.
uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work
곱셈 오버플로를 검출하는 보다 효율적이고 저렴한 방법은 다음과 같습니다.
uint32_t x, y;
const uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
(a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;
그 결과 UINT32_MAX는 오버플로우 또는 곱셈의 결과 중 하나가 됩니다.이 경우 부호 있는 정수에 대해 곱셈이 진행될 수 있도록 하는 것은 엄밀하게 정의되지 않은 동작입니다.
주의: 이것은 부분적인 Karatsuba 방식의 곱셈 분해를 사용하여 64비트 곱셈의 상위 32비트를 계산하고 32비트 곱셈 오버플로우 여부를 확인하도록 설정되어 있는지 여부를 확인합니다.
C++를 사용하는 경우 이를 깔끔한 작은 람다로 변환하여 오버플로우를 계산하여 디텍터의 내부 작동을 숨길 수 있습니다.
uint32_t x, y;
const bool overflow
{
[](const uint32_t x, const uint32_t y) noexcept -> bool
{
const uint32_t a{(x >> 16U) * uint16_t(y)};
const uint32_t b{uint16_t(x) * (y >> 16U)};
return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
}(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};
오퍼랜드에서 가장 중요한 1비트의 위치와 약간의 기본적인 바이너리 산술 지식을 사용하여 연산이 오버플로우할 가능성이 있는지 여부를 판단하는 방법이 있습니다.
또한, 임의의 2개의 오퍼랜드에 의해 (최대) 최대 오퍼랜드의 최대 1비트보다 1비트가 많아집니다.예를 들어 다음과 같습니다.
bool addition_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits<32 && b_bits<32);
}
곱셈의 경우, 임의의 2개의 피연산자는 (최대) 피연산자의 비트의 합이 됩니다.예를 들어 다음과 같습니다.
bool multiplication_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits+b_bits<=32);
}
할 수 .a껏껏의 b음음음같 뭇매하다
bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}
(물론 타겟 정수의 비트수를 바꿉니다).
숫자에서 가장 높은 1비트의 위치를 확인하는 가장 빠른 방법은 무엇인지 잘 모르겠습니다. 다음은 brute-force 방법입니다.
size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;
}
완벽하지는 않지만 작업을 수행하기 전에 두 개의 숫자가 넘칠 수 있는지 알 수 있습니다.하신 대로 보다 더 이 입니다. 왜냐하면 루프가 있기 때문입니다.highestOneBitPosition(특히 오퍼랜드에 몇 비트가 있는지 미리 알고 있는 경우) 동작할 수 있습니다.
일부 컴파일러는 CPU의 정수 오버플로 플래그에 액세스할 수 있습니다.이 플래그는 테스트 할 수 있지만 표준이 아닙니다.
곱셈을 수행하기 전에 오버플로 가능성을 테스트할 수도 있습니다.
if ( b > ULONG_MAX / a ) // a * b would overflow
이제 Clang은 서명된 정수 및 서명되지 않은 정수 모두에 대해 동적 오버플로우 검사를 지원합니다.-fsanitize=syslog 스위치를 참조하십시오.현재 디버깅을 위해 완전히 지원되는 동적 오버플로우 체크를 가진 유일한 C++ 컴파일러입니다.
는 ": GCC"로 때할 수 .-O2. ★★★-Wall하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다, 경고하다.
if (a + b < a) { /* Deal with overflow */ }
단, 이 예에서는 제외됩니다.
b = abs(a);
if (b < 0) { /* Deal with overflow */ }
유일하게 안전한 방법은 CERT 문서에서 설명한 바와 같이 오버플로가 발생하기 전에 확인하는 것입니다.이 방법은 체계적으로 사용하는 것이 매우 번거롭습니다.
「」를 한 컴파일-fwrapv는 문제를 해결하지만 일부 최적화를 디세블로 합니다.
우리는 더 나은 해결책이 절실히 필요하다.오버플로에 의존하는 최적화를 할 때 컴파일러는 기본적으로 경고를 해야 한다고 생각합니다.현재의 상황으로 인해 컴파일러는 오버플로우 체크를 최적화할 수 있으며, 이는 내 생각에 받아들일 수 없다.
많은 사람들이 오버플로에 대한 질문에 답했지만, 저는 그의 원래 문제를 해결하고 싶었습니다.그는 모든 숫자가 반복되지 않고 사용되도록 a=c를 찾는b 것이 문제라고 말했다.네, 이 투고에서 그가 요청한 것은 아니지만, 저는 여전히 문제의 상한을 연구하여 오버플로를 계산하거나 탐지할 필요가 없다고 결론을 내릴 필요가 있었다고 생각합니다(주:수학은 서툴러서 차근차근 했는데 결과는 너무 간단해서 간단한 공식이 나올지도 몰라요.
요점은 문제가 a, b 또는 c에 필요한 상한은 98.765.432라는 것입니다.우선 문제를 사소한 부분과 그렇지 않은 부분으로 나눕니다.
- x0 == 1(9, 8, 7, 6, 5, 4, 3, 2의 모든 배열은 솔루션)
- x1 == x (해결 불가능)
- 0b == 0 (해결 불가능)
- 1b == 1 (해결 불가능)
- ab, a > 1, b > 1 (비표준)
이제 다른 솔루션은 불가능하고 순열만 유효하다는 것을 보여주면 됩니다(그리고 인쇄하는 코드는 간단).상한선으로 돌아갑니다.실제로 상한은 c 9898.765.432입니다.8자리 숫자(10자리 합계에서 a와 b 각각에 대해 1을 뺀 값)로 가장 큰 숫자이기 때문에 상한입니다.a와 b의 경계가 2에서 상한까지 변화하는 지수 성장 때문에 훨씬 더 낮아야 하기 때문에 이 상한은 c에 대해서만 적용됩니다.
9938.08^2 == 98765432
462.241^3 == 98765432
99.6899^4 == 98765432
39.7119^5 == 98765432
21.4998^6 == 98765432
13.8703^7 == 98765432
9.98448^8 == 98765432
7.73196^9 == 98765432
6.30174^10 == 98765432
5.33068^11 == 98765432
4.63679^12 == 98765432
4.12069^13 == 98765432
3.72429^14 == 98765432
3.41172^15 == 98765432
3.15982^16 == 98765432
2.95305^17 == 98765432
2.78064^18 == 98765432
2.63493^19 == 98765432
2.51033^20 == 98765432
2.40268^21 == 98765432
2.30883^22 == 98765432
2.22634^23 == 98765432
2.15332^24 == 98765432
2.08826^25 == 98765432
2.02995^26 == 98765432
1.97741^27 == 98765432
예를 들어 마지막 줄에는 1.97^27~98M이라고 표시되어 있습니다.예를 들어, 1^27 == 1 및 2^27 == 134.217.728 이며, 이는 9자리 숫자(2 > 1.97)이므로 실제로 테스트해야 할 값보다 큽니다.보시다시피, a와 b의 테스트에 사용할 수 있는 조합은 매우 작습니다.b == 14의 경우 2와 3을 시도해야 합니다.b == 3의 경우 2에서 시작하여 462에서 멈춥니다.모든 결과는 최대 9800만 미만으로 인정됩니다.
위의 모든 조합을 테스트하고 숫자를 반복하지 않는 조합을 찾습니다.
['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
['1', '2', '3', '5', '8'] 8^3 = 512
['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
['1', '2', '4', '6'] 4^2 = 16
['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
['1', '2', '4', '6'] 2^4 = 16
['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
['1', '2', '8', '9'] 9^2 = 81
['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
['1', '3', '4', '8'] 3^4 = 81
['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
['2', '3', '6', '7', '9'] 3^6 = 729
['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
['2', '3', '8'] 2^3 = 8
['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
['2', '3', '9'] 3^2 = 9
['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
['2', '4', '6', '8'] 8^2 = 64
['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
['2', '4', '7', '9'] 7^2 = 49
['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)
어느 것도 이 문제와 일치하지 않습니다('0', '1', '...', '9'가 없는 경우에도 알 수 있습니다).
이 문제를 해결하는 코드 예는 다음과 같습니다.또한 Python으로 작성된 것은 임의의 정밀 정수가 필요하기 때문이 아니라(코드는 9800만 이상의 정수를 계산하지 않음), 테스트의 양이 너무 적기 때문에 내장된 컨테이너와 라이브러리를 사용하기 위해 고급 언어를 사용해야 한다는 것을 알게 되었기 때문입니다(또한 코드에는 28줄의 줄이 있습니다).
import math
m = 98765432
l = []
for i in xrange(2, 98765432):
inv = 1.0/i
r = m**inv
if (r < 2.0): break
top = int(math.floor(r))
assert(top <= m)
for j in xrange(2, top+1):
s = str(i) + str(j) + str(j**i)
l.append((sorted(s), i, j, j**i))
assert(j**i <= m)
l.sort()
for s, i, j, ji in l:
assert(ji <= m)
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d' % (s, i, j, ji)
# Try with non significant zero somewhere
s = ['0'] + s
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)
C/C++에서 오버플로 플래그를 액세스할 수 없습니다.
일부 컴파일러에서는 트랩 명령을 코드에 삽입할 수 있습니다.의 경우 은 GCC입니다.-ftrapv.
포터블과 컴파일러에 의존하지 않고 할 수 있는 것은, 스스로 오버플로우를 체크하는 것 뿐입니다.당신이 예에서 했던 것처럼요.
★★★★★★★★★★★★★★.-ftrapv최신 GCC를 사용하는 x86에서는 아무것도 할 수 없는 것 같습니다.이전 버전이나 다른 아키텍처에 특화된 잔여물인 것 같습니다.컴파일러가 추가될 때마다 INTO opcode를 삽입할 것으로 예상했습니다.불행하게도 그것은 이것을 하지 않는다.
테스트하는 데이터 타입보다 큰 데이터 타입이 있는 경우(32비트 추가가 이루어지고 64비트 타입이 있는 경우), 오버플로가 발생했는지 여부를 검출합니다.이 예는 8비트 추가용입니다.하지만 규모를 늘릴 수 있습니다.
uint8_t x, y; /* Give these values */
const uint16_t data16 = x + y;
const bool carry = (data16 > 0xFF);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);
이 페이지에서 설명하는 개념을 기반으로 합니다.http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html
에서는 32비트입니다.0xFF becomes가 되다0xFFFFFFFF ★★★★★★★★★★★★★★★★★」0x80 becomes가 되다0x80000000uint16_tbecomes becomes a uint64_t.
메모: 이것은 정수 덧셈/감산 오버플로우를 포착하고, 당신의 질문이 곱셈과 관련되어 있음을 깨달았습니다.이 경우, 분할이 최선의 접근법일 수 있습니다.이것은 흔히 하는 방법이다.calloc구현에서는 최종 크기를 얻기 위해 매개 변수를 곱할 때 매개 변수가 오버플로하지 않도록 합니다.
x86 명령어 세트에는 결과를 2개의 레지스터에 저장하는 부호 없는 곱셈 명령이 포함되어 있습니다.C로부터의 이 명령을 사용하려면 64비트 프로그램(GCC)에 다음 코드를 쓸 수 있습니다.
unsigned long checked_imul(unsigned long a, unsigned long b) {
unsigned __int128 res = (unsigned __int128)a * b;
if ((unsigned long)(res >> 64))
printf("overflow in integer multiply");
return (unsigned long)res;
}
32비트 프로그램의 경우 64비트와 파라미터 32비트로 결과를 만들어야 합니다.
다른 방법으로는 플래그 레지스터를 체크하기 위해 컴파일러에 의존하는 내수를 사용하는 것입니다.오버플로우 본질에 대한 GCC 설명서는 6.56 내장 함수에서 오버플로우 검사를 통한 산술 수행에 대해 확인할 수 있습니다.
mozilla::CheckedInt<T> 정수 유형에 대해 오버플로우 체크된 정수 계산을 제공합니다.T(사용 가능한 경우 clang 및 gcc의 컴파일러 내장 함수를 사용합니다).이 코드는 MPL 2.0으로 되어 있으며 3개의 IntegerTypeTraits.h다른 헤더 전용 비표준 라이브러리 헤더와 Mozilla 고유의 어설션 머신에 의존합니다.코드를 Import 하는 경우는, 어설션 머신을 교환할 필요가 있을 가능성이 있습니다.
입니다.unsigned long는 에 s s sunsigned long long, 0x4400000, 0x4400000과 .LLL.
이 방법이 예시와 같이 나눗셈을 수행하는 것보다 더 효율적이라는 것을 알게 될 것입니다.
아, 그리고 C와 C++(문항에 태그를 붙였으므로) 모두 사용할 수 있습니다.
glibc 매뉴얼을 보고 있었어요정수 오버플로 트랩에 대한 언급이 있습니다.FPE_INTOVF_TRAP의 일부로서SIGFPE매뉴얼에 기재되어 있는 불쾌한 부분을 제외하면 이상적입니다.
FPE_INTOVF_TRAP정수 오버플로(하드웨어 고유의 방법으로 오버플로우 트래핑을 이노블로 하지 않는 한 C 프로그램에서는 불가능).
좀 아쉽네요.
어셈블리 언어를 사용하는 솔루션의 또 다른 변형은 외부 절차입니다.이 예에서는 Linux x64에서 g++ 및 fasm을 사용하여 부호 없는 정수 곱셈을 수행합니다.
이 절차에서는 부호 없는 2개의 정수 인수(32비트)를 곱합니다(amd64 사양(섹션 3.2.3 파라미터 패싱)).
클래스가 INTEGER인 경우 시퀀스 %rdi, %rsi, %rdx, %rcx, %r8 및 %r9의 다음 사용 가능한 레지스터가 사용됩니다.
(edi 및 esi가 내 코드에 등록됨) 및 오버플로가 발생한 경우 결과를 반환하거나 0을 반환합니다.
format ELF64
section '.text' executable
public u_mul
u_mul:
MOV eax, edi
mul esi
jnc u_mul_ret
xor eax, eax
u_mul_ret:
ret
테스트:
extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);
int main() {
printf("%u\n", u_mul(4000000000,2)); // 0
printf("%u\n", u_mul(UINT_MAX/2,2)); // OK
return 0;
}
프로그램을 asm 객체 파일과 링크합니다.내 경우 Qt Creator에서 다음 항목에 추가합니다.LIBS.찬성하다
비트 마스킹과 시프트가 유망해 보이지 않는 부동소수점 숫자에 대해서도 같은 질문에 답해야 했습니다.내가 정한 접근법은 부호 있는 숫자와 부호 없는 숫자, 정수 및 부동 소수점 숫자에 적용된다.중간 계산을 위해 승격할 더 큰 데이터 유형이 없어도 작동합니다.이 모든 타입에서 가장 효율적인 것은 아니지만, 모든 타입에서 사용할 수 있기 때문에 사용할 가치가 있습니다.
서명된 오버플로 테스트, 더하기 및 빼기:
MAXVALUE 및 MINVALUE 유형의 가능한 최대값과 최소값을 나타내는 상수를 구합니다.
피연산자의 기호를 계산하고 비교합니다.
a. 두 값 중 하나가 0일 경우 덧셈과 뺄셈 모두 오버플로할 수 없습니다.나머지 테스트는 건너뜁니다.
b. 부호가 반대일 경우 덧셈이 넘칠 수 없습니다.나머지 테스트는 건너뜁니다.
c. 부호가 같으면 뺄셈은 오버플로할 수 없습니다.나머지 테스트는 건너뜁니다.
MAXVALUE의 양의 오버플로를 테스트합니다.
a. 두 부호가 모두 양수이고 MAXVALUE - A < B이면 덧셈이 오버플로우됩니다.
b. B의 부호가 음수이고 MAXVALUE - A < - B이면 뺄셈이 오버플로우됩니다.
MINVALUE의 음수 오버플로에 대해 검정합니다.
a. 두 부호가 모두 음수이고 MINVALUE - A > B이면 덧셈이 오버플로우됩니다.
b. A 부호가 음수이고 MINVALUE - A > B일 경우 뺄셈이 오버플로우됩니다.
그렇지 않으면 오버플로는 없습니다.
서명된 오버플로 테스트, 곱셈 및 나눗셈:
MAXVALUE 및 MINVALUE 유형의 가능한 최대값과 최소값을 나타내는 상수를 구합니다.
피연산자의 크기(절대값)를 계산하여 1과 비교합니다(아래에서 A와 B는 부호 있는 원고가 아닌 이러한 크기라고 가정합니다).
a. 어느 하나의 값이 0일 경우 곱셈은 오버플로할 수 없으며 나눗셈은 0 또는 무한을 산출합니다.
b. 어느 하나의 값이 1일 경우 곱셈과 나눗셈은 오버플로 할 수 없습니다.
c. 한 피연산자의 크기가 1 미만이고 다른 피연산자의 크기가 1보다 클 경우 곱셈은 오버플로할 수 없습니다.
d. 둘 다 크기가 1보다 작을 경우 분할은 오버플로할 수 없습니다.
MAXVALUE의 양의 오버플로를 테스트합니다.
a. 두 오퍼랜드가 모두 1보다 크고 MAXVALUE / A < B일 경우 곱셈이 오버플로우됩니다.
b. B가 1 미만이고 MAXVALUE * B < A일 경우 분할이 오버플로우됩니다.
그렇지 않으면 오버플로는 없습니다.
주의: 절대값을 취했기 때문에 MINVALUE의 최소 오버플로는 3으로 처리됩니다.단, ABS(MINVALUE)> MAXVALUE의 경우는 드물게 false positive가 발생합니다.
언더플로우 테스트는 비슷하지만 EPSILON(0보다 큰 최소 양의 수)이 포함됩니다.
CERT는 "as-if" 무한범위(AIR) 정수 모델을 사용하여 부호 있는 정수 오버플로, 부호 없는 정수 래핑 및 정수 절단을 검출하고 보고하는 새로운 접근법을 개발했습니다.CERT는 모델을 기술한 기술 보고서를 발행하여 GCC 4.4.0 및 GCC 4.5.0에 기반한 작업용 프로토타입을 제작했습니다.
AIR 정수 모델은 무한 범위 정수를 사용하여 얻을 수 있는 값과 동일한 값을 생성하거나 런타임 제약 조건 위반을 초래합니다.이전 정수 모델과 달리 AIR 정수에는 정확한 트랩이 필요하지 않으므로 대부분의 기존 최적화가 중단되거나 금지되지 않습니다.
다음은 이 질문에 대한 "노트북이 아닌" 해결책입니다.인텔 x86 및 x64 CPU에는 EFLAGS-register라고 불리는 기능이 탑재되어 있습니다.EFLAGS-register는 정수 연산 후에 프로세서에 의해 입력됩니다.자세한 설명은 생략하겠습니다.관련된 플래그는 "오버플로우" 플래그(마스크 0x800)와 "캐리" 플래그(마스크 0x1)입니다.이들을 올바르게 해석하기 위해서는 오퍼랜드가 부호 있는 타입인지 부호 없는 타입인지를 고려해야 한다.
다음은 C/C++에서 플래그를 확인하는 실용적인 방법입니다.다음 코드는 GNU C/C++ 64비트뿐만 아니라 Visual Studio 2005 이상(32비트 및 64비트)에서도 작동합니다.
#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif
inline size_t query_intel_x86_eflags(const size_t query_bit_mask)
{
#if defined( _MSC_VER )
return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
// This code will work only on 64-bit GNU-C machines.
// Tested and does NOT work with Intel C++ 10.1!
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);
return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
return 0;
#endif
}
int main(int argc, char **argv)
{
int x = 1000000000;
int y = 20000;
int z = x * y;
int f = query_intel_x86_eflags(0x801);
printf("%X\n", f);
}
오버플로우 경우 .query_intel_eflags(0x801) 플래그도되어 있지 제공된 main()의 예시 코드에서는 오버플로가 발생하고 양쪽 플래그가 1로 설정됩니다.이 검사는 더 이상의 계산을 의미하지 않으므로 매우 빠릅니다.
결과를 2배로 계산하세요.유효 자리수는 15자리입니다.요건의 c 상한은8 10입니다.최대 8자리까지 가능합니다.따라서 범위 내에 있으면 결과가 정확하고 그렇지 않으면 오버플로가 발생하지 않습니다.
또 다른 흥미로운 도구는 IOC: C/C++용 Integer Overflow Checker입니다.
컴파일 시 코드에 체크를 추가하는 패치 적용 Clang 컴파일러입니다.
출력은 다음과 같습니다.
CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
이 매크로를 사용하여 32비트 머신의 오버플로 비트를 테스트합니다(Angel Sinigersky 솔루션 채택).
#define overflowflag(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
그렇지 않으면 오버플로 비트가 덮어쓰기되기 때문에 매크로로 정의했습니다.
다음은 위의 코드 구분을 사용한 작은 응용 프로그램입니다.
#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif
using namespace std;
#define detectOverflow(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
int main(int argc, char **argv) {
bool endTest = false;
bool isOverflow;
do {
cout << "Enter two intergers" << endl;
int x = 0;
int y = 0;
cin.clear();
cin >> x >> y;
int z = x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow occured\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
z = x * x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow ocurred\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;
char c = 0;
do {
c = getchar();
} while ((c == '\n') && (c != EOF));
if (c == 'y' || c == 'Y') {
endTest = true;
}
do {
c = getchar();
} while ((c != '\n') && (c != EOF));
} while (!endTest);
}
Msalter의 대답은 좋은 생각이다.
정수 계산이 필요하지만(정밀도를 위해) 부동 소수점을 사용할 수 있는 경우 다음과 같은 작업을 수행할 수 있습니다.
uint64_t foo(uint64_t a, uint64_t b) {
double dc;
dc = pow(a, b);
if (dc < UINT_MAX) {
return (powu64(a, b));
}
else {
// Overflow
}
}
휴대용 방식으로 오버플로하지 않고 부호 없는 곱셈을 수행하려면 다음을 사용할 수 있습니다.
... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
product += multiplicand;
if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */
int number_of_leading_zeroes( unsigned value ){
int ctZeroes;
if( value == 0 ) return 32;
ctZeroes = 1;
if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
if( ( value >> 24 ) == 0 ){ ctZeroes += 8; value = value << 8; }
if( ( value >> 28 ) == 0 ){ ctZeroes += 4; value = value << 4; }
if( ( value >> 30 ) == 0 ){ ctZeroes += 2; value = value << 2; }
ctZeroes -= x >> 31;
return ctZeroes;
}
작업을 수행하기 전에 특히 모든 연산자(+ 및 *)를 덮어쓰고 오버플로를 확인하는 것이 좋습니다.
어디에 쓰느냐에 따라 다르죠.Unsigned long(DWORD)의 덧셈 또는 곱셈을 수행할 때 가장 좋은 솔루션은 ULARGE_INTEGER를 사용하는 것입니다.
ULARGE_INTEGER는 2개의 DWORD로 구성되어 있습니다.전체 값은 "QuadPart"로 액세스 할 수 있습니다.높은 DWORD는 "HighPart"로 액세스 하고 낮은 DWORD는 "LowPart"로 액세스 할 수 있습니다.
예를 들어 다음과 같습니다.
DWORD
My Addition(DWORD Value_A, DWORD Value_B)
{
ULARGE_INTEGER a, b;
b.LowPart = Value_A; // A 32 bit value(up to 32 bit)
b.HighPart = 0;
a.LowPart = Value_B; // A 32 bit value(up to 32 bit)
a.HighPart = 0;
a.QuadPart += b.QuadPart;
// If a.HighPart
// Then a.HighPart contains the overflow (carry)
return (a.LowPart + a.HighPart)
// Any overflow is stored in a.HighPart (up to 32 bits)
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int mltovf(int a, int b)
{
if (a && b) return abs(a) > MAX/abs(b);
else return 0;
}
main()
{
int a, b;
for (a = 0; a <= MAX; a++)
for (b = 0; b < MAX; b++) {
if (mltovf(a, b) != (a*b > MAX))
printf("Bad calculation: a: %d b: %d\n", a, b);
}
}
C/C++에서 오버플로 플래그를 액세스할 수 없습니다.
나는 이것에 동의하지 않는다.몇 개 , 「」를 할 수 있습니다.jo(x86 상에서 오버플로를 트랩하는 것을 전제로 한 명령입니다.물론 코드를 다른 아키텍처에 이식할 수 없게 됩니다.
info as ★★★★★★★★★★★★★★★★★」info gcc.
오버플로를 테스트하는 간단한 방법은 현재 값이 이전 값보다 작은지 여부를 확인하는 것입니다.예를 들어, 2의 거듭제곱을 인쇄하기 위한 루프가 있다고 가정합니다.
long lng;
int n;
for (n = 0; n < 34; ++n)
{
lng = pow (2, n);
printf ("%li\n", lng);
}
오버플로우 체크를 추가하면 다음과 같은 결과가 됩니다.
long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
lng = pow (2, n);
if (lng <= lng_prev)
{
printf ("Overflow: %i\n", n);
/* Do whatever you do in the event of overflow. */
}
printf ("%li\n", lng);
lng_prev = lng;
}
부호 없는 값뿐만 아니라 양수 및 음수 부호 값에도 사용할 수 있습니다.
것이 아니라 값을 것과 을 하고 , 값을 줄이는 것을 .<=>=언더플로우의 동작이 오버플로우의 동작과 동일하다고 가정합니다.솔직히 말하면 CPU의 오버플로 플래그에 액세스하지 않고 얻을 수 있는 휴대성은 거의 비슷합니다(또한 인라인 어셈블리 코드가 필요하기 때문에 여러 구현에서 코드를 이식할 수 없습니다).
부호 없는 정수의 경우 결과가 다음 인수 중 하나보다 작은지 확인합니다.
unsigned int r, a, b;
r = a + b;
if (r < a)
{
// Overflow
}
부호 있는 정수의 경우 인수와 결과의 부호를 확인할 수 있습니다.
다른 부호의 정수는 오버플로할 수 없으며, 같은 부호의 정수는 결과가 다른 부호의 경우에만 오버플로합니다.
signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
// Overflow
}
인라인 어셈블리를 사용하면 오버플로 비트를 직접 확인할 수 있습니다.만약 당신이 C++를 사용한다면, 당신은 정말로 조립을 배워야 합니다.
C에서 Integer Overflow를 포착하면 GCC 확장이 필요한 경우에도 CERT에서 논의한 솔루션보다 일반적인 솔루션이 나타납니다(처리된 유형의 경우 더 일반적입니다).
언급URL : https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-multiply-overflow
'source' 카테고리의 다른 글
| mysql2 gem으로 앱을 설치하려고 하면 오류가 발생했습니다. (0) | 2022.09.17 |
|---|---|
| 웹 팩을 통한 깜박임이 다른 결과를 반환함 (0) | 2022.09.17 |
| @Bean과 @Autowired의 차이점 (0) | 2022.09.17 |
| 자바에는 인라인 함수가 있나요? (0) | 2022.09.17 |
| 절차를 사용하여 열의 기본값을 변경하는 방법 (0) | 2022.09.17 |