缺少在C ++中输入的值中的元素(Missing element in values entered in C++)

缺少在C ++中输入的值中的元素(Missing element in values entered in C++)

代码采用整数n并且采用n-1元素。 输入的元素是从1到n所有数字，除了其中一个。 我们应该找到缺失的元素。

这个解决方案是最快的。 但是，我不明白。 有谁能解释一下？

#include <iostream> int main(){ int g,n,i,k; std::cin>>n; for(i=1; i<n; i++){ std::cin>>g; k^=i^g; } std::cout<<(k^n); }

输入：

10 3 8 10 1 7 9 6 5 2

输出：

4

The code takes an integer n and takes in n-1 elements. The elements entered are all the numbers from 1 to n, except one of them. We are supposed to find the missing element.

This solution is the fastest. However, I don't understand it. Can anyone explain it ?

#include <iostream> int main(){ int g,n,i,k; std::cin>>n; for(i=1; i<n; i++){ std::cin>>g; k^=i^g; } std::cout<<(k^n); }

Input:

10 3 8 10 1 7 9 6 5 2

Output:

4

最满意答案

这使用了XOR是可交换和关联的事实（所以顺序无关紧要），并且对于所有x ， x^x == 0 。

它取所有数字在1和n之间的XOR，并且它与所有输入数字相关。 输入的任何数字将在最终结果中进行两次异或，因此将被取消。 剩下的唯一数字是未输入的数字。 这个数字只被XOR一次，因此这将是所有XOR的结果的值。

对于您给出的示例：输入数字为：3 8 10 1 7 9 6 5 2

1^2^3^4^5^6^7^8^9^10 ^ 3^8^10^1^7^9^6^5^2 = (1^1)^(2^2)^(3^3)^4^(5^5)^(6^6)^(7^7)^(8^8)^(9^9)^(10^10) = 4

请注意，代码编写有些令人困惑，因为XOR的顺序并不简单：它在对输入进行异或运算和对1和n之间的下一个数字进行异或运算之间进行交替。 这样做只是为了保持代码简短。 它会更清楚：

k = 0; for (i=1; i<=n; i++) k ^= i; for (i=0; i<n-1; i++) { std::cin >> g; k ^= g; } std::cout << k;

This uses the fact that XOR is commutative and associative (so order doesn't matter), and that x^x == 0 for all x.

It takes the XOR of all numbers between 1 and n, and also xors it with all the input numbers. Any number that was input will be XORed twice into the final result, and therefore will be cancelled out. The only number remaining will be the number that wasn't input. This number was only XORed once, and therefore this will be the value of the result of all the XORs.

For the example you gave: The input numbers are: 3 8 10 1 7 9 6 5 2

1^2^3^4^5^6^7^8^9^10 ^ 3^8^10^1^7^9^6^5^2 = (1^1)^(2^2)^(3^3)^4^(5^5)^(6^6)^(7^7)^(8^8)^(9^9)^(10^10) = 4

Note that the code is written somewhat confusingly, because the order of XORs is not straightforward: it alternates between XORing an input and XORing the next number between 1 and n. This is only done to keep the code short. It would be clearer as:

k = 0; for (i=1; i<=n; i++) k ^= i; for (i=0; i<n-1; i++) { std::cin >> g; k ^= g; } std::cout << k;