题目如下：
已经公式 ：x+y=x|y，0< x, y < 2,000,000,000，求使公式成立的第k小的y值。
输入：x k
输出：y
示例：
输入：5 2
输出：8
输入：5678 88888
输出：11372928
输入：345678989 1234565
输出：1246040098
注意：允许时间1s。（爆力解很容易超时）
解析：2000，000，000足够用int类型存下了，故定义一个位数组，32位（4个字节，初始值全部为0），把x(换算成二进制形式)以右端对齐填入数组中，再把k（换算成二进制形式）也以右端对齐填入数组中取值为0的位置（x+y与x|y的区别在于是否进位，如果保持x+y不进位就可以了。为什么要把k的二进制填充到取值为0的位？因为若x的二进制某一位为1，则y对应位应当为0，否则就会进位。同时直接填充k是由依次搜索推出来的结论，设想一下，依次从右往左搜索与直接填充k的二进制原理是相同的），java代码如下：
package test;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Test {
static Test main = new Test();
class Node{
public int pos; //用于存数的位置
public int value; //该位置的值
public boolean flag = false; //该位置是否已经设置过
public Node(){
}
public Node(int pos, int value){
this.pos = pos;
this.value = value;
}
public int getPos() {
return pos;
}
public void setPos(int pos) {
this.pos = pos;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public boolean isFlag() {
return flag;
}
public void setFlag(boolean flag) {
this.flag = flag;
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int x =scan.nextInt();
int k = scan.nextInt();
// 爆力方法
long pre1 = System.currentTimeMillis();
normCal(x, k);
long aft1 = System.currentTimeMillis();
System.out.println("method 1 takes: "+(aft1-pre1)+" ms!");
// 简便方法 1 （向x的非1位置从右依次填充k的二进制）
long pre2 = System.currentTimeMillis();
unNormalCal(x, k);
long aft2 = System.currentTimeMillis();
System.out.println("method 2 takes: "+(aft2-pre2)+" ms!");
// 简便方法 2
long pre3 = System.currentTimeMillis();
unNormalCal3(x, k);
long aft3 = System.currentTimeMillis();
System.out.println("method 3 takes: "+(aft3-pre3)+" ms!");
}
}
// unNormalCal method（简便方法2，是一位大神想出来的，速度更不用说了）
private static void unNormalCal3(int x, int k) {
int y = 0, n =1;
while(k>0){
if(x%2!=0){
//此时x的二进制最右端为1的话，一直使x右移，就是找到x的为0的位置
while(x%2!=0){
n = n*2; //每移一位，n记录一下变化的值
x = x/2;
}
}
//如果k的二进制最右端为1，就使y加上n
if(k%2!=0)
y = y+n;
n = n*2;
x = x/2;
k = k/2; //同时使x,k右移，以便下一步判断
}
System.out.println(y);
}
// unNormalCal method（简便方法）
private static void unNormalCal(int x, int k) {
//2,000,000,000足够用int类型来存，4个字节，共32位，开始置每位为0
List<Test.Node> list = new ArrayList<Test.Node>();
for(int m = 0;m<32;m++){
Test.Node node = main.new Node(m, 0);
list.add(node);
}
//把x转成二进制，并把x的二进制填充到32位中
char b_x[] = Integer.toBinaryString(x).toCharArray();
for(int i = 0; i<b_x.length;i++){
//从32-b_x.length+i依次填充
Test.Node node = list.get(32-b_x.length+i);
node.setValue(Integer.valueOf(String.valueOf(b_x[i])));
//该位置为1的话，就直接设置为true，不变，因为x+y与x|y的唯一区别就是进位与不进位
if(node.getValue()==1){
node.setFlag(true);
}
}
//把k转成二进制，并把k的二进制填充到32位中，依次从右向左非1的单位
char b_k[] = Integer.toBinaryString(k).toCharArray();
for(int i = b_k.length-1;i>=0;i--){
for(int j=list.size()-1;j>=0;j--){
Test.Node node = list.get(j);
if(!node.isFlag()){
//如果没有访问过，就设置该位
node.setValue(Integer.valueOf(String.valueOf(b_k[i])));
node.setFlag(true);
break;
}
}
}
//res_b用来存放4个字节中的所有二进制位
String res_b = "";
for(int j= 0;j<list.size();j++){
res_b = res_b + String.valueOf(list.get(j).getValue());
}
//输出结果
System.out.println((getInteger(res_b)-x));
}
// norm method（爆力方法）
public static void normCal(int x, int k){
int flag = 0;
for(int i=1;i<=2000000000;i++){
if((x+i)==(x|i)){
flag++;
if(flag==k){
System.out.println(i);
break;
}
}
}
}
//binary to integer（把二进制转化为相应的整数）
public static int getInteger(String s){
int x = 0;
char s_arr[] = s.toCharArray();
for(int i=s_arr.length-1;i>=0;i--){
x = (int) (x + Integer.valueOf(String.valueOf(s_arr[i]))*Math.pow(2, s_arr.length-1-i));
}
return x;
}
}
执行结果如下：
5678 88888
11372928
method 1 takes: 16 ms!
11372928
method 2 takes: 15 ms!
11372928
method 3 takes: 0 ms!
345678989 1234565
1246040098
method 1 takes: 3541 ms!
1246040098
method 2 takes: 16 ms!
1246040098
method 3 takes: 0 ms!