找出最小的数字n,以使n XOR n + 1等于C ++中给定的k
假设我们有一个正数k。我们必须找到正数n,以使n和n+1的XOR与k相同。因此,如果k=7(111),输出将为3。由于3(011)和3+1=4(100),所以011XOR100=111(7)
有两种可能的情况。考虑n是偶数。n的最后一位=0。然后n+1的最后一位=1。其余位相同。因此,当n为奇数时,XOR为1,最后一位为1,而n+1位的最后一位为0。但是在这种情况下,由于进位而导致更多位不同。进位继续向左传播,直到获得第一个0位。因此nXORn+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