给定 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

1 收藏


直接登录
最新评论
  • ★小V★ 程序員 2016/10/01

     

    • ★小V★ 程序員 2016/10/01

      兩個小錯

      String[] s = br.readLine().split(“\s”); 應該是String[] s = br.readLine().split(” “);

      第13行漏了個分號在結尾..其他應該沒啥問題

    • 廖宇康   2016/10/09

      这个代码交上去  100分  最多30分吧

      看看数据范围

      • ★小V★ 程序員 2016/10/10

        的確沒留意到數值範圍..已經直接在bit operation上下手…..我想出來的話在貼個答案上去

        • bord   2016/10/10

          这样可以的。

          • ★小V★ 程序員 2016/10/11

            畢竟帶了個範圍,我就想了個很變態的case

            x = k = 2000000000

            根據我目前的想法會出現heap space 不夠…在java里…..

      • ★小V★ 程序員 2016/10/11

        我感覺我這個應該是最好的solution了把?想法是這樣的…先把x換成binary string, k就代表第k個0的位置(從右數起),用pos表示,在不用加leading 0的情況下,最後的答案應該是1 << pos,然後換成10進制; 如果要找不到第k個0,那就說明我們要加leading zero,那麼加多少個呢?先算出目前有多少個0,然後得到需要增加leading zero的數目為k – (0的數量),得到這一信息後,pos就是加完0之後總長度-1,最終的答案也是 1 << pos。

         

        沒測試過k到什麼值是java 會throw outofmemeoryerror,畢竟原題給了最大範圍值,我就測了個最變態的x = k = 2000000000,這妥妥的拋error了,只能用print statement說要left shift多少位了…

         

        • bord   2016/10/11

          这么算不对的,k>=3时,结果就错了。

          应该是把x转成2进制xbits,k转成kbits,然后从低位到高位,依次把xbits为0

          的位用kbits填充,xbits为1的位设为0,最后得到的结果就是。

          假设x=11,k=6;
          二进制表示:x=1011,k=110
          拼结果:(从低到高)
          位数    1    2    3    4
          x        1   1    0    1
          k        0    1    1

          res:    0    x第1位为1,结果为0
          0    x第2位为1,结果为0
          0    x第3位为0,所以取k的第1位,结果为0
          0    x第4位为1,结果为0
          1    x第5位为0,所以取k的第2位,结果为1
          1    x第6位为0,所以取k的第3位,结果为1

          res = 110000  转为10进制 –> 48

          • ★小V★ 程序員 2016/10/11

            哦是的…當時列舉沒把k大於3的情況列出來看…

          • ★小V★ 程序員 2016/10/12

            按照你的方法我改進成這樣子了,logic應該沒錯,也很容易handle到x= k = 2,000,000,000的case了

             

  • Java实现我就不会了,谈谈方法。

    用字符串方法读取数字,再不断mod 2,生成另一个字符串。注意哦,所有满足x+y=x|y条件的y,他的二进制一定是只在二进制x的某一位为0时才可能为1,当然,也不一定是1。

    然后根据给定的k跑循环,造出第k小的二进制数。,随后转换成十进制。题目给出的2000…0在这个算法中用于define字符串最大长度。算法开销好像只取决于k吧。

  • 王念一 高二学生 2016/10/11

    x+y==x|y当且仅当x&y==0。

    若(1<<BitCount(x)<<1)-1<k的话,y不存在。(BitCount是计数x中1的个数)

    否则将k中的每一位按顺序位移到~x上去,剩下的位数用0填充即可

    (不知道这样说大家能不能明白,因为我不会java就不给代码了)

  • Robin.G Java Developer 2016/10/12

    我们不妨首先来看看 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 的二进制表示:10,插回 0101 中的“0”对应的位置得到:1101。这个数就是第 k 小的 x | y。
    下一步如何得到 y?还记得我们开始的时候就通过观察发现这是一种特殊情况下的“异或”,所以我们可以将 x 与 x | y 再进行一次“异或”操作就可以得到 y:1000

    ok,思路已经理清楚了。Talk is cheap, show me the code,让我们撸代码吧!

    大功告成!

    • Robin.G Java Developer 2016/10/12

      更正:

      在 x = 5,k = 1 时,后面的分析迷糊了套用了 k = 2,实际上:
      x = 0101, k = 0001 -> 第 k 小的 x | y = 0111。
      与 x 进行异或操作得到 y = 0010,即 y = 2。
      与题目一致。

    • Vinozly   2016/10/13

      y的值是有可能超过32位的,你的实现貌似没有考虑到。

      • Robin.G Java Developer 2016/10/13

        确实是这样,根据题意,0 < x, k <= 2,000,000,000。
        而 2,000,000,000 < 2^31。

        那在极端的情况下 x,k 可能除去符号位外,每一位都为 1。这样 y 最多有 31 + 31 + 1 = 63 位,用 long 可以解决。

        那我们在 for 循环之后再加一个循环来直接插入 k 剩下的二进制位就可以了。

        代码如下:

        修改了循环的终止条件,同时将 x,k,y 的类型改为了 long,当 x,k 的类型为 int,y 为 long 时, y 并不能输出正确的十进制结果(打印二进制显示是正确的)。不清楚原因,不知道有没有大牛愿意解释一下。

        ps: Integer.MAX_VALUE = 214748364

        • Vinozly   2016/10/14

          可否提供测试数据?

          • Robin.G Java Developer 2016/10/16

            将 x,k 的类型定义修改为 int 型,输入为全1,其实就是 Integer.MAX_VALUE。然后修改一下输出,增加二进制的输出,你就可以看到 y 的二进制结果正确,十进制却错了。

             

            • Vinozly   2016/10/18

              当x,k为int类型时,问题出在第二个循环中:

              在这个循环的第一次遍历时,i==31, (k & 1)<< i 为0x80000000,32位中的最高位为1,其余位为0。然后和y进行或运算,这时隐含了类型转换,int型被转换成了long,这个long的高33为全为1,所以在第一次遍历结束时,结果就已经出问题了。

              • Robin.G Java Developer 2016/10/18

                也就是说 int 在向 long 进行类型转换的时候,高位不是自动补 0,而是根据第 32 位“符号位”自动补充?

                • Vinozly   2016/10/19

                  是的,你可以打印下Long.toBinaryString(Integer.MIN_VALUE)的结果,如果我没记错的话,long的高位全为1。

                   

        • 逐风   2016/10/14

          因为已经超出 Long 的范围了,猜测你打印出来的十进制应该是个负数。

          栗子:x=1, k=200000000,x^y=x|y,第1小的数的二进制为10,第2小的数的二进制为110,那么第2000000000小的数的二进制应该是1111…(一共1999999999个1)…1110,即 y 有2000000000位。

          • ★小V★ 程序員 2016/10/14

            (數字用的是二進制)你這個例子,第一小的時候是10,第二小難道不是100麼…然後第三小才是110…

            • Robin.G Java Developer 2016/10/16

              回复不小心点了赞,不过这不重要。

              这个我在下面补充更正了一下,例子中的 k 本来应该为 1(0001),不过我后面分析的时候弄混了,记成了 k = 2(0010)。

              所以最小是 0001, 然后 0010, 0011… 其实第 k 小就是对应二进制的 k

            • 逐风   2016/10/17

              额,确实是这样的,之前理解有误

          • Robin.G Java Developer 2016/10/16

            Long 的范围没有超,你仔细看下我第二次贴代码的分析,x + k 的位平移最多其实就是 int + int 一共 64 位,Long 就有 64 位。

            然后 k 最小应该为 k = 1(0001),这个是我的笔误。原答案不能所以在后面补充了一条评论,可能给你造成了困扰。

  • 冷月小刀 小学三年级 2016/10/14

    x+y=x|y(算术加法等于逻辑加法)  可以导出 x&y=0 即x与y在相同的位上不能同时为1,根据Robin.G 的评论的启发,以及排列组合的相关知识,可以得出第k个y的值就是将k的二进制按顺序插入到x的二进制中的0上。

  • 冷雨轩 java web 2016/10/14

    我不知道我是不是没有读清题意     但是貌似…………………看评论贴的代码也是迷迷糊糊……………

  • 严九天   2016/10/17

    受评论区启发写出的答案,省略了输入过程

     

  • 冷月小刀 小学三年级 2016/10/17

    private static void printValue(int x, int k) {

    long y = 0;
    int indexX = 0, indexK = 0, indexY = 0;
    while ((x >> indexX != 0) || (k >> indexK != 0)) {
    if ((x >> indexX & 1) == 0) {
    y += (k >> indexK & 1) << (indexY);
    indexK++;
    }
    indexX++;
    indexY++;
    }
    System.out.println(“y=” + y);
    }

  • 两个数字先转化为二进制,然后把第二个数字的二进制数据插入到第一个数据的零位上,其他用零填充就得到了    比如说第一个为10001001001

    第二个为101

    结果为10010

  • 来个野路子

    public static void main(String[] args){
    int x =99;
    int k =2;

    String value1=Integer.toBinaryString(x);
    String value2 = Integer.toBinaryString(~x);
    int value3 =20000000;
    int index = value2.length()-value1.length()-k-1;
    if(index>value2.length()) {
    System.out.println(“k值太么大了”);
    return ;
    }

    String value4 = value2.substring(index);
    Integer result=Integer.parseInt(value4, 2);
    if(result>value3){
    System.out.println(“y超范围了:”+result);
    return;
    }
    System.out.println(“y:”+result);
    }