Count smaller values whose XOR with x is greater than x in C++

กำหนดจำนวนเต็ม x นับจำนวน y ที่ 0 < y < x และ (y XOR x) > x

ตัวอย่าง: x = 11 (binary 1011) → Output: 4 (y = 4,5,6,7)

หลักการ (Bitwise Analysis)

y XOR x > x ก็ต่อเมื่อ bit แรกที่ต่างกัน (จาก MSB) ของ y เป็น 1 และของ x เป็น 0

→ นับ bit 0 ใน x: สำหรับแต่ละ bit 0 ที่ตำแหน่ง i สามารถเลือก y ที่ bit i = 1 และ bit สูงกว่า = 0 ได้ → เพิ่ม 2^i ตัวเลือก

ตัวอย่างโค้ด C++

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

int XOR_smaller(int x) {
    int count = 0, bit = 1;
    while(x > 0) {
        if((x & 1) == 0) count += bit;
        bit <<= 1;
        x >>= 1;
    }
    return count;
}

int main() {
    cout << XOR_smaller(11); // 4
    cout << XOR_smaller(12); // 11
}

Input

11

Output

4