在C ++中找到与整数数组的每个数字进行XOR运算时得出最小和的数字

概念

对于给定的非负整数数组Arr []，任务是确定一个整数X，使得（Arr [0] XOR X）+（Arr [1] XOR X）+…+ Arr [n – 1] XOR X是最小可能的。

输入值 

Arr[] = {3, 4, 5, 6, 7}

输出结果 

X = 7, Sum = 10

方法

因此，我们将以二进制表示形式验证数组中每个数字的'i'位，并考虑并计数那些包含将'i'位设置为'1'的数字，因为这些设置位将有助于使总和最大化而不是使其最小化。结果，如果计数大于N / 2，并且计数小于N / 2，那么必须将第i个位设置为“ 0”，那么将第i个位设置的数字就较少因此，它不会影响答案。根据两个位的XOR运算，当A XOR B以及A和B都相同时，其结果为'0'，因此我们将数字(num)中的'i'位构建为'1'结果是（1 XOR 1）将给出'0'并最小化和。

示例

// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void findX1(int arr1[], int n1){
   int* itr1 = max_element(arr1, arr1 + n1);
   int p1 = log2(*itr1) + 1;
   int X1 = 0;
   for (int i = 0; i < p1; i++) {
      int count1 = 0;
      for (int j = 0; j < n1; j++) {
         if (arr1[j] & (1 << i)) {
            count1++;
         }
      }
      if (count1 > (n1 / 2)) {
         X1 += 1 << i;
      }
   }
   long long int sum1 = 0;
   for (int i = 0; i < n1; i++)
      sum1 += (X1 ^ arr1[i]);
   cout << "X = " << X1 << ", Sum = " << sum1;
}
//驱动程式码
int main(){
   int arr1[] = { 3, 4, 5, 6, 7 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   findX1(arr1, n1);
   return 0;
}

输出结果

X = 7, Sum = 10