CF1554 C. Mikasa(位运算+思维)

目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

有两个数字 \(n, \ m\)，求最小 \(n ⊕ i(0<=i<=m)\) 中得不到的最小值

State

\(1<=n,m<=10^9\)

\(1<=t<=30000\)

Input

5
3 5
4 6
3 2
69 696
123456 654321

Output

4
3
0
640
530866

Solution

设最小得不到的数字为 \(k\)，则有 \(n⊕k>=m+1\)，使得 \(k\) 最小，那么在以下四种情况中

当有 \(0 \quad 1\) 的情况时，对应的 \(k\) 那一位需要为 \(1\)；

而当 $1\quad 0 $ 那样的情况出现时，这时即使 \(k\) 对应的那一位为 \(0\)，不等式 \(n⊕k>=m+1\) 也已经成立，此时 \(k\) 最小

Code

signed main()
{
    //IOS;
    rush(){
        sdd(n, m);
        m ++;
        int ans = 0;
        for(int i = 30; ~ i; i --){
            int a = (n >> i) & 1, b = (m >> i) & 1;
            if(a == b) continue;
            if(a > b) break;
            else{
                ans |= (1 << i);
            }
        }
        pd(ans);
    }
    return 0;
}