Count smaller numbers whose XOR with n produces greater value in C++

โจทย์เดียวกับข้อ 165: กำหนด num นับ y < num ที่ (y XOR num) > num

ตัวอย่าง: num = 11 → 4, num = 12 → 3 (โจทย์ต้นฉบับมีข้อผิดพลาดในตัวอย่าง x=12 ควรเป็น 11)

วิธีแก้ปัญหา (Bitwise)

เหมือนข้อ 165: วนตรวจสอบ bit ของ num จาก LSB ถ้า bit = 0 ให้เพิ่ม 2^position ลงในคำตอบ

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

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

int XOR_greater(int n) {
    int count = 0, pos = 0;
    while(n > 0) {
        if((n & 1) == 0) count += (1 << pos);
        pos++;
        n >>= 1;
    }
    return count;
}

int main() {
    cout << XOR_greater(11) << endl; // 4
    cout << XOR_greater(12) << endl; // 11 (ไม่ใช่ 3 ตามโจทย์ต้นฉบับ)
    cout << XOR_greater(20) << endl; // 11
}

Input

11

Output

4