今日头条笔试题-或与加

问题描述

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。
比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。

输入描述

每组测试用例仅包含一组数据，每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。

输出描述

输出一个数y。

示例 1

输入

5 1

输出

2

解题思路

如果要使 x + y = x | y 成立，那么x的二进制码是1的地方，y只能是0。
如果要找到第k小的y，那么满足$y \ge k$，因为如果1..k都满足要求，那么第k小就是k。
现在问题已经转化为固定位为0，填充其它位使其满足第k小。
这时候就要把k绕开固定0位，按二进制插入到新值中。

例如：
x = 5
$5_2 \eq 0101$
k = 2
$2_2 \eq 10$
y 的 第二第四位固定为零，然后将k插入
y = 1000

解题代码

#include <iostream>
 
using namespace std;
 
int main() {
    unsigned long long x=0,k=0;
    cin>>x>>k;
    unsigned long long ans = 0;
    int n = 0;
    while(k){
        if (!(x&1)){
            ans |= (1&k)<<n;
            k = k>>1;
        }
        x = x>>1;
        n++;
    }
    cout << ans<<endl;
}