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

给定 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 0000001
2 0000010
3 0000011
4 0000100
5 0000101
6 0000110
7 0000111
8 0001000
9 0001001
10 0001010
11 0001011
12 0001100
13 0001101
14 0001110
15 0001111
16 0010000
17 0010001
18 0010010
19 0010011
20 0010100
21 0010101
22 0010110
23 0010111
24 0011000
25 0011001
26 0011010
27 0011011
28 0011100
29 0011101
30 0011110
31 0011111
32 0100000
33 0100001
34 0100010
35 0100011
36 0100100
37 0100101
38 0100110
39 0100111
40 0101000
41 0101001
42 0101010
43 0101011
44 0101100
45 0101101
46 0101110
47 0101111
48 0110000
49 0110001
50 0110010
51 0110011
52 0110100
53 0110101
54 0110110
55 0110111
56 0111000
57 0111001
58 0111010
59 0111011
60 0111100
61 0111101
62 0111110
63 0111111
64 1000000
65 1000001
66 1000010
67 1000011
68 1000100
69 1000101
70 1000110
71 1000111
72 1001000
73 1001001
74 1001010
75 1001011
76 1001100
77 1001101
78 1001110
79 1001111
80 1010000
81 1010001
82 1010010
83 1010011
84 1010100
85 1010101
86 1010110
87 1010111
88 1011000
89 1011001
90 1011010
91 1011011
92 1011100
93 1011101
94 1011110
95 1011111
96 1100000
97 1100001
98 1100010
99 1100011
100 1100100

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

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

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

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

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

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

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

/* ***********************************************
Author :111qqz
Created Time :2017年03月30日 星期四 10时17分40秒
File Name :code/toutiao4.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
int bin_y[80],cnt_y=0;
int bin_x[80],cnt_x=0;
int bin_k[80],cnt_k=0;
int x,k;
void bin( int x)
{
    while (x)
    {
	bin_x[++cnt_x] = x%2;
	x/=2;
    }
}
void bin2( int x)
{
    while (x)
    {
	bin_k[++cnt_k] = x%2;
	x/=2;
    }
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	//打表得到的规律:对于x的二进制表示中,某位为1,那么对应的y的位置上一定为0;
	//如果某位为0,那么可以为1,可以为0.
	//所以保留x中,为1的位置,将k的二进制填写到为0的位置上,最后得到的数就是ans...
	//全程口胡,写一发先.
	cin>>x>>k;
	bin(x);
	bin2(k);
	ms(bin_y,-1);
	int cur = 0 ;
	for ( int i = 1 ; i <= 60 ; i++)
	{
	    if (bin_x[i]==0)
	    {
		bin_x[i] = bin_k[++cur];
	    }
	}
	unsigned long long  ans = 0 ;
	unsigned long long p = 1;
	for ( int i = 1 ; i <= 60 ; i++)
	{
	    ans = ans + p * bin_x[i];
//	    cout<<bin_x[i]<<endl;
	   // cout<<"p:"<<p<<endl;
	    p<<=1;
	}
	cout<<ans-x<<endl;
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}