或与加

Posted by ysd on August 28, 2016

给定 x, k ,求满足 x + y = x | y 的第k小的正整数 y

x在二进制取1的位上,y只能取0

exp.
x = 10010010011
y = 00000000000   k = 0
y = 00000000100   k = 1
y = 00000001000   k = 2
y = 00000001100   k = 3
y = 00000100000   k = 4
y = 00000100100   k = 5

注意粗体的数字,为x取0的比特位,而如果把括号里的数连起来看,正好等于k。

#include <iostream>
using namespace std;
int main() {
    long long x, k;
    while(cin>>x>>k) {
        long long bit = 1;
        long long ans = 0;
        while (k) {
            if ((x & bit) == 0) {
                //目标是把k的各位依次填在x中是0的位上
                // k&1是将k的最低位取出来
                ans += (k & 1) * bit;  
                k = k>>1;
            }
            bit = bit<<1;
        }
        cout<<ans<<endl;
	}
    return 0;
}