c++ - 如何通过对 2 位或更多位数字使用 XOR 运算符来解决此 C++ 问题

Question

XOR 对于单个数字输入工作正常，但在使用 2 位或更多数字时完全搞砸了。我怎样才能仍然使用 XOR 来制作这个程序？

基本上就是这个问题:

找到丢失的号码

给你一个包含 n-1 个整数的列表，这些整数在 1 到 n 的范围内。列表中没有重复项。列表中缺少一个整数。编写高效的代码来查找丢失的整数。

我的程序是:

#include<iostream>

using namespace std;

int main(void)
{
    int n; //number of elements

    cout << "Enter the number of elements : ";
    cin >> n;

    //Declaring array
    int arr[n-1];

    //Taking input
    for(int i = 0; i<n-1; i++)
    cin >> arr[i];

    //printing array
    cout << "\nElements are :";
    for(int i = 0; i<n-1; i++)
    cout << " " << arr[i];

    //Declaring elements to take XOR
    int x1 = arr[0]; // first element of array
    int x2 = 1; //first element in natural number series i.e 1,2,3,4...

    //taking XOR of all elements of the given array
    for(int i = 1; i<n-1; i++)
    x1 ^= arr[i];

    //taking XOR of all the natural numbers till 'n'
    for(int i = 2; i<arr[n-1]; i++)
    x2 ^= i;

    //Finally printing the output by taking XOR of x1 and x2
    //because same numbers will be removed since (A^A) = 0 also (A^0) = A
    cout << "\nMissing number : " << (x1^x2) << endl;

    return 0;
}

上面的程序不适用于下面的输入:

10
1 2 3 4 5 6 7 8 10

Answer 1

你的循环是错误的，你可以改成:

//Declaring elements to take XOR
int x1 = 0; // for element of array
int x2 = 0; // for natural number series i.e 1,2,3,4...

//taking XOR of all elements of the given array
for (int i = 0; i < n-1; i++)
    x1 ^= arr[i];

//taking XOR of all the natural numbers till 'n'
for (int i = 1; i != n + 1; i++)
    x2 ^= i;

请注意，自然数范围大于 arr 大小。