C++中中间计算临时结果的数据类型判定及计算错误咨询

Hey there, let's break down your question and the code issues step by step:

核心问题解答 #

When calculating a*b before applying the modulo operation in C++, the data type used to store the temporary result is determined by the usual arithmetic conversions defined in the C++ standard. Here's the key rule set:

• For arithmetic operations, the compiler first converts both operands to a common type that can represent the range of values from both operands. The priority of conversions goes like this:
  • If either operand is long double, the other is converted to long double
  • Else if either is double, the other becomes double
  • Else if either is float, the other becomes float
  • For integer types: operands are converted to the type with the higher integer conversion rank. For example, long long has a higher rank than int, and an unsigned integer type has a higher rank than its signed counterpart (e.g., unsigned int > int).
  • In short: if both operands are the same integer type, the temporary result uses that type. If they're different, the result uses the type with the higher rank.

This rule comes directly from the ISO/IEC 14882 (C++ Standard), specifically the "usual arithmetic conversions" section applicable to all C++ versions since C++11.

分析你的两段错误代码 #

第一段代码 #

#include <iostream> 
using namespace std; 
int main() { 
    long long int a=1000000000000000000; // 18 zeroes
    long long int b=1000000000000000000;
    long long int c=1000000007;
    long long int d=(a*b)%c;
    cout<<a<<"\n"<<b<<"\n"<<c<<"\n"<<d; 
}

The problem here is that a and b are both long long, so a*b is computed as a long long. But 1e18 * 1e18 = 1e36, which is way larger than the maximum value of a 64-bit signed long long (which is 2^63-1 ≈ 9.2e18). This causes integer overflow, which is undefined behavior in C++. The corrupted value after overflow is then used for the modulo operation, leading to the wrong result.

第二段代码 #

#include <iostream> 
using namespace std; 
int main() { 
    int a=1000000000; // 9 zeroes
    int b=1000000000;
    long long int c=1000000007;
    long long int d=a*b%c;
    cout<<a<<"\n"<<b<<"\n"<<c<<"\n"<<d; 
}

Here, a and b are int types, so a*b is computed as an int. A 32-bit int can only hold up to 2^31-1 ≈ 2e9, but 1e9 * 1e9 = 1e18 is way beyond that. Again, integer overflow occurs, producing a garbage value. Even though you assign the final result to a long long, the damage is already done during the multiplication step.

修复方案 #

To fix these issues, you need to ensure the multiplication is done in a type that can hold the large intermediate result:

• For the first code, use __int128 (supported by GCC, Clang, and other major compilers) to store the product before taking modulo:

  long long int d = ((__int128)a * b) % c;
  

• For the second code, cast one of the int operands to long long before multiplication to promote the entire operation to long long:

  long long int d = ((long long)a * b) % c;
  

内容的提问来源于stack exchange，提问作者Milan