C++-এ XOR গ্রেটার ভ্যালু: n-র চেয়ে ছোট যাদের XOR n-র চেয়ে বড়

একটি পূর্ণসংখ্যা n দেওয়া আছে। n-র চেয়ে ছোট কতগুলো পূর্ণসংখ্যা y আছে যাতে y XOR n > n?

উদাহরণ

n = 11 (1011) → আউটপুট: 4 (y = 4,5,6,7)

n = 12 (1100) → আউটপুট: 3 (y = 1,2,3)

অ্যালগরিদম (বিটওয়াইজ)

1. temp = 0 (বিট পজিশন), count = 0।
2. while (n > 0):
   • যদি n & 1 == 0 (LSB ০ হয়), count += 2^temp।
   • temp++, n >>= 1।
3. count ফেরত দিন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

int XOR_greater(int n) {
    int temp = 0, count = 0;
    while (n > 0) {
        if ((n & 1) == 0)
            count += (1 << temp);  // pow(2, temp) এর চেয়ে ফাস্ট
        temp++;
        n >>= 1;
    }
    return count;
}

int main() {
    int n = 20;
    cout << "Count: " << XOR_greater(n);
    return 0;
}

ব্যাখ্যা n=20 (10100)

বিট পজিশন: 0(0), 1(0), 2(1), 3(0), 4(1)

০ বিট পজিশন: 0, 1, 3 → 2⁰ + 2¹ + 2³ = 1 + 2 + 8 = 11

দ্রষ্টব্য

আর্টিকেল ১৬৫ ও ১৬৬ প্রায় একই সমস্যা, শুধু ভেরিয়েবল নাম ভিন্ন।