c++ - 对于非常大的输入，从 1...n 丢失和重复数字数组。使用 1...n 系列属性的解决方案。溢出问题

Question

这是为 https://www.interviewbit.com/problems/repeat-and-missing-number-array/ 提供的代码通过同一网站:

vector<int> repeatedNumber(const vector<int> &V) {
   long long sum = 0;
   long long squareSum = 0;
   long long temp;
   for (int i = 0; i < V.size(); i++) {
       temp = V[i];
       sum += temp;
       sum -= (i + 1);
       squareSum += (temp * temp);
       squareSum -= ((long long)(i + 1) * (long long)(i + 1));
   }
   // sum = A - B
   // squareSum = A^2 - B^2 = (A - B)(A + B)
   // squareSum / sum = A + B
   squareSum /= sum;

   // Now we have A + B and A - B. Lets figure out A and B now. 
   int A = (int) ((sum + squareSum) / 2);
   int B = squareSum - A;

   vector<int> ret;
   ret.push_back(A);
   ret.push_back(B);
   return ret;
}

现在，我写了一个类似的代码，但没有进行类型转换，它会为更大的输入返回错误。谁能解释一下类型转换是如何解决溢出的？

另外，我看到了这个问题的 XOR 方法，但我不知道位操作问题。如果有人可以帮助我提供一些链接/资源以使用位操作方法处理问题，那就太好了!

感谢阅读我的问题并愿意提供帮助!干杯!

Answer 1

(i + 1) * (i + 1) 将在 int 算术中计算，有可能溢出，其行为是未定义的.

写作

((long long)(i + 1) * (long long)(i + 1)); 

是一种避免这种影响的冗长方法；你可以使用清洁器

(i + 1LL) * (i + 1)

相反，这会导致其他术语的转换。