ধরুন আমাদের একটি ধনাত্মক সংখ্যা 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 এর শেষ বিট। বাকি বিটগুলো একই। সুতরাং XOR হবে 1, যখন n বিজোড়, শেষ বিট 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
