মনে করুন আমাদের একটি ধনাত্মক সংখ্যা 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। কিন্তু এই কেসে, ক্যারি কারণে আরও বিটগুলো ভিন্ন হবে। ক্যারি বাম দিকে চলতে থাকবে যতক্ষণ না প্রথম ০ বিট পাওয়া যায়। তাই n XOR n+1, হবে 2^i - 1, যেখানে i হল 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
