สมมติว่าเรามีจำนวนบวก 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 แต่ในกรณีนี้ บิตที่มากกว่าซึ่งแตกต่างกันเนื่องจากการพกพา แครี่ยังคงแพร่กระจายไปทางซ้ายจนกว่าเราจะได้ 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
