今日头条笔试题_或与加(打表,构造)

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

 

输入例子:

 

输出例子:

一看就是数学题…?
打表观察…

 

发现如果x的二进制表示中,如果某位为1,那么对应的y的位置上一定为0.

如果某位为0,那么对应的y的位置上可以为0也可以为1…

就是说…x的二进制表示中,为1的的那些位置是能改变的.

影响当前第几大的就是那些为0的位置…

所以我们可以把k转化成二进制表示,按顺序填充到x中为0的那些位置(主要可以填充到x最大权值的1之后的0的位置),然后得到的数就是x+y的答案,最后再减去x即可

因为数组开小了..第一次只过了90%….

果然是个废k了呜呜呜,数组开小这种错误我也是服了…

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz