数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找最小的数字 n，使得 n XOR n+1 等于给定的 k
假设我们有一个正数 k。我们需要找到一个正数 n，使得 n 和 n+1 的异或结果等于 k。因此，如果 k = 7 (111)，则输出将为 3。因为 3 (011) 和 3 + 1 = 4 (100)，所以 011 XOR 100 = 111 (7)
有两种可能的情况。考虑 n 是偶数。n 的最后一位为 0。那么 n + 1 的最后一位为 1。其余位相同。因此，当 n 为奇数时，异或结果为 1，最后一位为 1，而 n + 1 的最后一位为 0。但在这种情况下，由于进位，更多位会发生差异。进位会一直向左传播，直到我们得到第一个为 0 的位。因此，n XOR n + 1 将为 2^i -1，其中 i 是从左起 n 中第一个 0 位的位置。因此，我们可以说，如果 k 的形式为 2^i – 1，则答案将为 k/2。
示例
#include<iostream>
using namespace std;
int findNValue(int k) {
if (k == 1)
return 2;
if (((k + 1) & k) == 0)
return k / 2;
return -1;
}
int main() {
int k = 15;
cout << "The value of n is: " << findNValue(k);
}输出
The value of n is: 7
更新于: 2019年12月18日
215 次查看
广告