在“伯乐在线”上看到的一个美团笔试题，解答了一下，顺便把思考过程和答案贴回来。
题目
给定 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。
输入例子: 5 1
输出例子: 2
解答
我们不妨首先来看看 x + y == x | y 在什么样的条件下成立。
先看 x = 3, y = 5，转为二进制计算： 0011 + 0101 = 1000 0011 | 0101 = 0111
其实我们可以发现在对应的某一位上，二进制的加法实际上是在执行“异或”的操作，与“或”操作相比，只有在这一位上都为“1”时，结果不同。 也就是如果 x,y 符合 x + y == x | y，那 x,y 二进制在同一位上必然只有一个有“1”。问题就可以转化为：怎样将 x 二进制里面的“0”，转化为“1”才能获得第 k 小的数？
当 x = 5, k = 1 时，y 为多少？ 我们在 0101 中插入的“1”要尽量小，不妨刨去 0101 中的“1”，剩下全“0”的情况，因为只有“0”才能让我们有机会插入“1”。而第 k 小的数自然就是 k 本身。所以我们得到 k 的二进制表示：01，插回 0101 中的“0”对应的位置得到：0111。这个数就是第 k 小的 x | y。 下一步如何得到 y？还记得我们开始的时候就通过观察发现这是一种特殊情况下的“异或”，所以我们可以将 x 与 x | y 再进行一次“异或”操作就可以得到 y：0010
ok，思路已经理清楚了。Talk is cheap， show me the code，让我们撸代码吧！
import java.util.Scanner;
/**
* Created by Robin on 12/10/2016.
*/
public class Meituan {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("x: ");
long x = scan.nextInt();
System.out.print("k: ");
long k = scan.nextInt();
long y = x;
for (int i = 0; i < 31 && k != 0; i++) {
if ((x >> i & 1) == 0) {
y = ((k & 1) << i) | y;
k = k >> 1;
}
}
for (int i = 31; i < 63 && k != 0; i++) {
y = ((k & 1) << i) | y;
k = k >> 1;
}
y = y ^ x;
System.out.println(y);
}
}
在编写上面的代码的时候发现一个问题：当 y 为 long，而 x,k 为 int 类型的时候，代码会得到错误的结果。
这是因为 Java 在对 int 型向 long 自动转型的时候，高位不是自动补 0，而是根据最高位符号位自动补充。就造成了我代码中的错误。