나는 a b = c 의 모든 솔루션을 찾기 위해 C ++로 프로그램을 작성 중이었습니다 . 여기서 a , b 및 c 는 모두 0-9를 정확히 한 번만 사용합니다. 프로그램의 값 이상 반복 및 B를 , 그리고 숫자 카운팅 루틴을 실행 한 각 시간 , B 및 B 숫자 조건이 만족되었는지를 확인하기 위해.
그러나, 스퓨리어스 솔루션을 생성 할 수 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 ++을 통해 액세스하는 것을 본 적이 없습니다.
조심하십시오 서명 int 오버 플로우가 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.
답변
이 인 작업이 피연산자에서 가장 중요한 1의 비트의 위치와 약간의 기본적인 이진 – 수학 지식을 사용하여, 오버 플로우 가능성이 있는지 여부를 확인하는 방법.
또한 두 피연산자가 있으면 최대 피연산자의 가장 높은 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);
}곱셈의 경우, 두 피연산자는 피연산자의 비트 합계를 (최대) 계산합니다. 예를 들면 다음과 같습니다.
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 비트의 위치를 결정하는 가장 빠른 방법은 확실하지 않습니다. 다음은 무차별 대입 방법입니다.
size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;
}완벽하지는 않지만 작업을 수행하기 전에 두 숫자가 넘칠 수 있는지 여부를 알 수 있습니다. highestOneBitPosition함수 의 루프로 인해 제안 된 방식으로 결과를 확인하는 것보다 더 빠를 지 여부는 알 수 없지만 (특히 피연산자에 몇 비트가 있는지 알고 있다면) 특히 그렇습니다.
답변
Clang 3.4+ 및 GCC 5+ 는 확인 된 산술 내장 기능을 제공합니다. 특히 비트 테스트 안전 점검과 비교할 때이 문제에 대한 매우 빠른 솔루션을 제공합니다.
OP의 질문에 대한 예는 다음과 같이 작동합니다.
unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
// Returned non-zero: there has been an overflow
}
else
{
// Return zero: there hasn't been an overflow
}Clang 문서는 c_test오버플로가 발생한 경우 오버플로 된 결과를 포함 할지 여부를 지정하지 않지만 GCC 문서는 그 결과를 나타냅니다. 이 두 가지가 __builtin호환 되는 것을 좋아한다면 Clang이 작동하는 방식이라고 가정하는 것이 안전 할 것입니다.
존재하는 __builtinINT 크기 긴 크기 및 긴 긴 크기 서명 부호 변형 넘칠 수있는 각각의 산술 연산 (가산, 감산, 승산), 대. 이름의 구문은 __builtin_[us](operation)(l?l?)_overflow다음과 같습니다.
u에 대한 서명 또는s를위한 서명 ;- 동작 중 하나
add,sub또는mul; l접미사 없음 은 피연산자가ints 임을 의미합니다 . 하나의l수단long; 두ls 의미long long합니다.
따라서 부호있는 긴 정수 덧셈의 경우는입니다 __builtin_saddl_overflow. 전체 목록은 Clang 문서 페이지 에서 찾을 수 있습니다 .
GCC 5+와 연타 3.8+ 추가로 값의 유형을 지정하지 않고 작업이 일반적인 내장 명령을 제공합니다 __builtin_add_overflow, __builtin_sub_overflow하고 __builtin_mul_overflow. 이것들은보다 작은 타입에서도 작동합니다 int.
내장은 플랫폼에 가장 적합한 것보다 낮습니다. x86에서는 캐리, 오버플로 및 부호 플래그를 확인합니다.
Visual Studio 의 cl.exe에는 해당 항목이 없습니다. 서명되지 않은 추가 및 빼기를 들어, 포함하여 <intrin.h>사용할 수 있도록 addcarry_uNN하고 subborrow_uNN(NN 같이, 비트 수입니다 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는 입력시 carry / borrow 플래그이고 리턴 값은 출력시 carry / borrow입니다. 부호있는 연산이나 곱셈에 해당하는 것으로 보이지 않습니다.
그렇지 않으면 Windows 용 Clang이 이제 프로덕션 용으로 준비되어 있으므로 (Chrome에는 충분) 옵션이기도합니다.
답변
일부 컴파일러는 CPU에서 정수 오버플로 플래그에 대한 액세스를 제공하므로 테스트 할 수는 있지만 표준은 아닙니다.
곱셈을 수행하기 전에 오버플로 가능성을 테스트 할 수도 있습니다.
if ( b > ULONG_MAX / a ) // a * b would overflow답변
경고 : GCC는로 컴파일 할 때 오버플로 확인을 최적화 할 수 있습니다 -O2. 이 옵션 -Wall은 다음과 같은 경우 경고를 표시합니다.
if (a + b < a) { /* Deal with overflow */ }이 예에서는 그렇지 않습니다.
b = abs(a);
if (b < 0) { /* Deal with overflow */ }유일한 안전한 방법은 CERT 논문에 설명 된 것처럼 오버플로가 발생하기 전에 확인하는 것인데, 이는 체계적으로 사용하는 것은 매우 지루할 것입니다.
컴파일 -fwrapv하면 문제 가 해결되지만 일부 최적화는 비활성화됩니다.
더 나은 솔루션이 절실히 필요합니다. 오버플로가 발생하지 않는 최적화를 만들 때 컴파일러가 기본적으로 경고를 발행해야한다고 생각합니다. 현재 상황에서 컴파일러는 오버플로 검사를 최적화 할 수 있습니다.
답변
Clang은 이제 부호있는 정수와 부호없는 정수 모두에 대해 동적 오버플로 검사를 지원합니다. -fsanitize = integer 스위치를 참조하십시오 . 현재로서는 디버그 목적으로 완전히 지원되는 동적 오버플로 검사 기능을 갖춘 유일한 C ++ 컴파일러입니다.
답변
많은 사람들이 오버플로에 대한 질문에 대답 한 것을 보았습니다. 그는 문제는 모든 숫자가 반복되지 않고 사용되도록 b = c 를 찾는 것이라고 말했다 . 좋아, 그는이 게시물에서 요구 한 것이 아니지만 여전히 문제의 상한을 연구하고 그가 오버플로를 계산하거나 감지 할 필요가 없다고 결론을 내릴 필요가 있다고 생각합니다 (참고 : 능숙하지 않습니다. 수학에서는 단계별 로이 작업을 수행했지만 최종 결과는 너무 간단하여 간단한 수식을 가질 수 있습니다).
요점은 문제가 a, b 또는 c에 필요한 상한이 98.765.432라는 것입니다. 어쨌든 사소한 부분과 사소한 부분에서 문제를 나누는 것으로 시작하십시오.
- x 0 == 1 (9, 8, 7, 6, 5, 4, 3, 2의 모든 순열은 해입니다)
- x 1 == x (가능한 해결책 없음)
- 0 b == 0 (가능한 해결책 없음)
- 1 B == 1 (해결책 없음 가능)
- a b , a> 1, b> 1 (사소하지 않음)
이제 우리는 다른 솔루션이 가능하지 않고 순열 만 유효하다는 것을 보여 주어야합니다 (그런 다음 그것을 인쇄하는 코드는 간단합니다). 우리는 상한으로 돌아갑니다. 실제로 상한은 c ≤ 98.765.432입니다. 8 자리 (각 a와 b에 대해 총 10 자리에서 1을 뺀 숫자)가 가장 큰 숫자이므로 상한입니다. 이 상한은 c에만 해당합니다. a와 b에 대한 경계는 지수 성장으로 인해 훨씬 낮아야하기 때문에 b는 2에서 상한까지 다양합니다.
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에서 멈 춥니 다. 모든 결과는 ~ 98M보다 작아야합니다.
이제 위의 모든 조합을 테스트하고 숫자를 반복하지 않는 조합을 찾으십시오.
['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’가 없으면 볼 수 있습니다).
이를 해결하는 예제 코드는 다음과 같습니다. 또한 임의의 정밀 정수 (코드가 98 백만보다 큰 것을 계산하지 않음)가 필요하지 않기 때문에 Python으로 작성되었지만 테스트 양이 너무 적어서 고급 언어를 사용해야한다는 것을 알았습니다. 내장 컨테이너 및 라이브러리를 사용하십시오 (참고 : 코드에는 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)