Cho k dương, tìm n dương sao cho n XOR (n+1) = k. Ví dụ k=7 (111) → n=3 (011 XOR 100 = 111).
Nếu n chẵn, XOR = 1. Nếu n lẻ, XOR = 2^i - 1 (i là vị trí bit 0 đầu tiên từ trái). Do đó k phải dạng 2^i-1, thì n = k/2. Đặc biệt k=1 → n=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); }
Kết quả
The value of n is: 7