Đếm số nhỏ hơn n có XOR lớn hơn n trong C++

Cho số nguyên num. Đếm số nguyên y < num sao cho y XOR num > num.

Ví dụ: num = 11 → 4; num = 12 → 3 (lưu ý: ví dụ trong bài gốc có vẻ nhầm, đúng là 11 cho num=12).

Giải thuật tương tự bài trước: Duyệt bit của num từ LSB, nếu bit = 0 thì cộng 2^temp vào kết quả.

Ví dụ

#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);
        temp++;
        n >>= 1;
    }
    return count;
}

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

Đầu ra

Count of smaller numbers whose XOR with n produces greater value are: 11