একটি পূর্ণসংখ্যা x দেওয়া আছে। x-র চেয়ে ছোট কতগুলো পূর্ণসংখ্যা y আছে যাতে y XOR x > x?
XOR সত্য টেবিল
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
উদাহরণ
x = 11 (1011)
y = 1..10 যাচাই করলে: 4,5,6,7 এর XOR 11-র চেয়ে বড়। মোট 4টি।
বিটম্যানিপুলেশন লজিক
y XOR x > x হলে y-র সেই বিটগুলো ১ হবে যেখানে x-র বিট ০। কারণ XOR-এ ০^১=১ হয়ে মান বাড়ায়।
সুতরাং, x-র ০ বিটগুলোতে যেকোনো কম্বিনেশন দিলে যাবতীয় সংখ্যা তৈরি হবে।
সূত্র
যদি x-র বাইনারি রিপ্রেজেন্টেশনে kটি ০ বিট থাকে (MSB 제외한), তবে উত্তর = 2^k - 1।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
int XOR_smaller(int x) {
int count = 0, num = 1;
while (x != 0) {
if ((x & 1) == 0) // বিট 0 হলে
count += num;
num <<= 1;
x >>= 1;
}
return count;
}
int main() {
int x = 20;
cout << "Count: " << XOR_smaller(x);
return 0;
}
উদাহরণ x=20 (10100)
বিট: 1 0 1 0 0 (পজিশন 4,3,2,1,0)
০ বিটগুলো: পজিশন 3, 1, 0 → ৩টি
উত্তর = 2³ - 1 = 7? না, কোড অনুযায়ী: 1<<3 + 1<<1 + 1<<0 = 8+2+1 = 11।
আউটপুট: 11
