首页 > 试题广场 >

或与加

[编程题]或与加
  • 热度指数:5223 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定 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
import java.util.*;
public class Main{
    private static int[] getBits(int x){
        int[] bits=new int[32];
        for(int i=0;i<32;++i){
            bits[i]=x%2;
            x>>=1;
        }
        return bits;
    }
    
    private static long bitsToLong(int[] bits){
        long res=0;
        for(int i=bits.length-1;i>=0;--i){
            res=(res<<1)+bits[i];
        }
        return res;
    }
    
    public static void main(String[] args){
         Scanner input=new Scanner(System.in);
         int x=input.nextInt(),k=input.nextInt();
         int[] bits_x=getBits(x),bits_k=getBits(k);
         int[] bits_res=new int[64];
         int i=0,j=0,m=0;
         for (;i<32;++i){
            if(bits_x[i]==0){
                bits_res[m++]=bits_k[j++];
            }else{
                bits_res[m++]=0;
            }
         }
         for (;j<32;++j)
            bits_res[m++]=bits_k[j];
         System.out.println(bitsToLong(bits_res));
    }
}
发表于 2022-04-01 12:15:11 回复(0)

热门推荐

通过挑战的用户