找出最小的数字n，以使n XOR n + 1等于C ++中给定的k

假设我们有一个正数k。我们必须找到正数n，以使n和n + 1的XOR与k相同。因此，如果k = 7(111)，输出将为3。由于3(011)和3 +1 = 4(100)，所以011 XOR 100 = 111(7)

有两种可能的情况。考虑n是偶数。n的最后一位=0。然后n + 1的最后一位=1。其余位相同。因此，当n为奇数时，XOR为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