标签搜索

目 录CONTENT

文章目录

字节--或与加.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 2,091 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字节--或与加

@[toc]

一、题目描述

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

输出例子1:
2

二、分析

同样,别看这道题简单,如果在本地进行暴力枚举y的值再进行编译肯定是没问题的,但是在OJ上就不一定了,因为k <= 2,000,000,000;普通解法肯定会超时,同样需要另辟捷径

  •  对于这道题,没有什么太大的意义,只是扩展思维而已;
  •  为了快速找到第k小的正整数y,我们既然不能暴力枚举,就只能从公式 x + y = x | y 下手,那么 x + y 和 x | y 有什么相同点和不同点呢?
  •  x + y = x | y 这里可以推出一个结论,如果x & y = 0。也就是说,在二进制上看,x取1的地方,y必定不能取1。
  •  从最低位考虑,若x与y在某一位上同时取1,则x + y在该位上为0,x | y在该位上为1,前面说这是最低一位x y同时取1,也就是说没有更低位加法的进位,所以这里两个结果不相等,出现了矛盾

例子:
x = 0 0 1 0 1 0
y = 1 1 0 1 1 0
x + y = 1 0 0 0 0 0
x | y = 1 1 1 1 1 0
偏差产生的原因是倒数第二位,x+y=0 x|y=1 且倒数第一位加法没有进位

  •  结论:x在二进制取1的位上,y不能做出改变,只能取0,因为如果x的某一位为1了,y在枚举 的时候相同的比特位还为1的话那么就不能满足x + y == x | y了
  •  有了上述结论,可以进一步推出只要在x取0的地方,y可以做出改变
  •  例如:

x = 10010010011
y = 00000000(0)00 k = 0
y = 00000000(1)00 k = 1
y = 0000000(1)(0)00 k = 2
y = 0000000(1)(1)00 k = 3
y = 00000(1)0(0)(0)00 k = 4
y = 00000(1)0(0)(1)00 k = 5
...
注意观察括号里的数,为x取0的比特位,而如果把括号里的数连起来看,正好等于k
得出结论,把k表示成二进制数,填入x取0的比特位,x取1的比特位保持为0,得到y

  •  ---代码说明--- 思路有了,接着就是代码,显然用位操作是最合适的方式。

三、代码

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;

int main()
{
    long long x, k;
    cin>>x>>k;
    long long bitNum = 1;
    long long ans = 0;
    while(k)
    {
        if((x & bitNum) == 0)
        {
            ans += (bitNum * (k & 1));
            k >>= 1;
        }
        bitNum <<= 1;
    }
    cout<<ans<<endl;
    return 0;
}
  •  循环的思想是每次取得k的最低一位,填入到低位开始,x中比特位为0的位置上。
  •  所以用while来判断k是否大于0,若是,说明k还未完全填完
  •  循环体内,需要找到x当前可以填的位置,我们用bitNum来从右往左扫描x的每一位
  •  (x & bitNum) == 0 说明x该位为0,可以把k的当前最后一位填入,用 (k & 1) 取出最后一位,用 ans += (bitNum * (k & 1)) 把k的最后一位填入到当前bitNum指向的位置。
  •  填完后,k右移一位,去掉已经被填过的最后一位,bitNum也向左走一位,避免重复填入x的某个位置。
  •  若x的某个位置为1,则跳过该位置,向左走一位并观察是否可以填入。
  •  两次bitNum向左走一位,合并成一句 bitNum <<= 1;
  •  如果上面的结论:x在二进制取1的位上,y不能做出改变,只能取0 不明白,我们再换一种讲解方式
但是可以举几个数字组合来找其中的规律:x + y = x | y
例如:
k = 1 时,5 + 2 == 5 | 2
k = 2 时,5 + 8 == 5 | 8
k = 3 时,5 + 10  == 5 | 10
k = 4 时,5 + 16  == 5 | 16
k = 5 时,5 + 18  == 5 | 18
…

在这里插入图片描述
转二进制
在这里插入图片描述
满足这个运算规律 x + y == x | y 的二进制有:

  • 0 + 0 == 0 | 0
  • 1 + 0 == 1 | 0
  • 1 + 1 != 1 | 1 (只有这个不满足)
  •  所以 x 和y 各自相对应的二进制位不能同时为 1,换言之, x 中 当前位 为 1 时, 与之对应的 y 那一位 肯定是 0 ,所以x 位为 1 的就确定了,可以去除1

X:
在这里插入图片描述
Y:
在这里插入图片描述
将 Y 中红色 的 0 去掉看看,得到一组新数据
在这里插入图片描述

  •  这正是 从 1 2 3 4 5 6 7,由于 y 表是按照 k 从1递增的顺序得到的值。所以你有理由猜想 这组新数据正是 k !
  •  X Y K 之间 有了这个关系,就大胆的编写代码去验证吧。
  •  总之这就是一个找规律的游戏
0

评论区