Processing math: 100%

C++中满足(n XOR x) = (n – x)条件的x的值的数量(x <= n)

给定一个输入数字n。目标是找到满足条件(n xor x)=(n-x)的x值。并且x的范围在[0,n]之间。

让我们通过例子来理解

输入 − n=10

输出 − 满足(n XOR x) = (n – x)条件的x的值的数量(x <= n)为4

解释 − 满足10 xor x = 10-x的x值为0, 2, 8和10。

输入 − n=15

输出 − 满足(n XOR x) = (n – x)条件的x的值的数量(x <= n)为16

解释 − 满足15 xor x = 15-x的x值为0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14和15。

下面程序中使用的方法如下

我们将使用两种方法。第一种是使用for循环的朴素方法。从i=0遍历到i<=n，将i作为可能的x值。现在检查(n - i == (n ^ i) //xor)是否成立。如果成立，则计数器加1。

  • 将整数变量n作为输入。

  • 函数unique_pair(int arr[], int size)接受数组及其长度并返回满足条件(arr[i],arr[j])(其中i

  • 将计数器的初始值设置为0。

  • 创建一个包含整数对的集合'se'。(set<pair<int, int>> se)

  • 使用两个for循环遍历arr[]。从i=0到i

  • 对于每一对(总是i

  • 在两个for循环结束后，更新count=se.size()。

  • 现在count包含'se'中对的数量。(所有都是唯一的)。

  • 返回count作为结果。

高效方法

在这种方法中，我们将首先将n转换为其二进制等价形式。我们知道：

1 xor 0 = 1-0

1 xor 1 = 1-1

但是

0 xor 0 ≠ 0-1

0 xor 1 ≠ 0-1

因此，对于n的二进制表示中的每一个1，都有2种情况。对于n的二进制表示中p个1，将有2p个值满足条件。

索引i。然后将这些单独的计数相加以得到总的唯一对数。

  • 将整数变量n作为输入。

  • 函数unique_pair(int arr[], int size)接受数组及其长度并返回满足条件(arr[i],arr[j])(其中i

  • 将计数器的初始值设置为0。

  • 使用number=bitset<8>(n).to_string();将n转换为字符串。

  • 令length=number.length()。

  • 使用for循环从索引i=0遍历到i

  • 将count=pow(2,count)设置为最终的x值。

  • 返回count作为结果。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例（朴素方法）

 在线演示

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
   int count = 0;
   for (int i = 0; i <= n; i++){
      if (n - i == (n ^ i)){
         count++;
      }
   }
   return count;
}
int main(){
   int n = 25;
   cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
   return 0;
}

输出

如果我们运行上面的代码，它将生成以下输出：

Count of values of x <= n for which (n XOR x) = (n – x) are: 8

示例（高效方法）

 在线演示

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
   int count = 0;
   string number = bitset<8>(n).to_string();
   int length = number.length();
   for (int i = 0; i < length; i++){
      if (number.at(i) == '1')
         { count++; }
   }
   count = (int)pow(2, count);
   return count;
}
int main(){
   int n = 25;
   cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
   return 0;
}

输出

如果我们运行上面的代码，它将生成以下输出：

Count of values of x <= n for which (n XOR x) = (n – x) are: 8

更新于：2020年12月2日

298 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告