สมมติว่ามีจำนวนบวก k เราต้องหาจำนวนบวก n ซึ่ง XOR ของ 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 บิตอื่นๆ เหมือนกัน ดังนั้น XOR จะเป็น 1 เมื่อ n เป็นคี่ บิตสุดท้าย 1 และบิตสุดท้ายของ n + 1 คือ 0 แต่ในกรณีนี้ บิตอื่นๆ ที่แตกต่างเนื่องจากมีการยืม (Carry) การยืมจะแพร่กระจายไปทางซ้ายจนกว่าจะได้บิต 0 แรก ดังนั้น n XOR n + 1 จะเป็น 2^i - 1 โดยที่ i คือตำแหน่งของบิต 0 แรกใน n จากซ้าย ดังนั้นเราสามารถพูดได้ว่า ถ้า 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
