Tìm số n nhỏ nhất sao cho n XOR n + 1 bằng với k đã cho trong C ++

Giả sử chúng ta có một số k dương. Chúng ta phải tìm số dương n, sao cho XOR của n và n + 1 giống với k. Vì vậy, nếu k =7 (111), đầu ra sẽ là 3. Là 3 (011) và 3 + 1 =4 (100), do đó 011 XOR 100 =111 (7)

Có hai trường hợp có thể xảy ra. Coi n là chẵn. Bit cuối cùng của n =0. Sau đó, bit cuối cùng của n + 1 =1. Phần còn lại của các bit giống nhau. Vì vậy, XOR sẽ là 1, khi n là số lẻ, bit cuối cùng là 1 và bit cuối cùng của bit n + 1 là 0. Nhưng trong trường hợp này, nhiều bit khác nhau do mang. Thực hiện tiếp tục lan truyền sang trái cho đến khi chúng tôi nhận được 0 bit đầu tiên. Vì vậy, n XOR n + 1, sẽ là 2 ^ i -1, trong đó i là vị trí của bit 0 đầu tiên trong n từ trái sang. Vì vậy, chúng ta có thể nói rằng nếu k có dạng 2 ^ i - 1, câu trả lời sẽ là k / 2.

Ví dụ

#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);
}

Đầu ra

The value of n is: 7