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

Cho số nguyên x. Đếm số nguyên dương y < x sao cho y XOR x > x.

Ví dụ: x = 11 → 4 (các y: 4,5,6,7).
x = 12 → 11.

Giải thuật quan sát bit: y XOR x > x khi và chỉ khi tại bit cao nhất mà y khác x, bit của y là 1 và của x là 0. Duyệt bit của x từ LSB, nếu bit = 0 thì cộng 2^position vào kết quả.

Ví dụ

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

int XOR_smaller(int x) {
    int count = 0, num = 1;
    while (x != 0) {
        if (x % 2 == 0) count += num;
        num *= 2;
        x /= 2;
    }
    return count;
}

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

Đầu ra

Count of smaller values whose XOR with x is greater than x are: 11