題目描述：
給定x在抛，k。求滿足x+y=x|y的第k小的正整數(shù)y返吻。
輸入描述：
每組測(cè)試用例僅包含一組數(shù)據(jù)姑子，每組數(shù)據(jù)為兩個(gè)正整數(shù)x，k测僵。滿足0<x,k<2,000,000,000街佑。
輸出描述：
輸出一個(gè)數(shù)y
輸入樣例：
5 1
輸出樣例
2
解析：
總結(jié)：
1.找出符合x+y=x|y的模式
2.找出符合第k小的模式
- 根據(jù)題目表述我們要先找到使x+y與x|y相等的條件，先不管k把樣例化為二進(jìn)制可以發(fā)現(xiàn)
x:5 = 101
y:1 = 010
嗯捍靠，取反沐旨。如果x=9呢
x:9 = 1001
如果y=1
y:1 = 0001
此時(shí)x+y=10，x|y=9,不成立
如果y=2
y:2 = 0010
此時(shí)x+y=11榨婆，x|y=11磁携，成立
`從上面的例子可以看出x+y=x|y的條件是(二進(jìn)制時(shí))只有當(dāng)Xi=0時(shí),Yi才能為1。(這個(gè)地方不知道怎么講解良风，可以自己測(cè)試幾個(gè)例子)`
2.下面要考慮k了谊迄，第k小即符合x+y=x|y的y值的升序排列
以x=9為例
x:9 = 00001001
符合條件的y值為
00000010
00000100
00000110
00010010
00010100
00010110
......
這里可以發(fā)現(xiàn)一個(gè)規(guī)律，如果把x為0位的相應(yīng)的值以升序組成數(shù)組
A[n]=2,4,16......
任意組合再按升序排列為
B[2^n-1]2烟央。4鳞上。2+4。16吊档。16+2。16+4唾糯。16+2+4怠硼。
第1小即為2，第二小為4......
可以發(fā)現(xiàn)如果A的個(gè)數(shù)為n移怯，那么B的個(gè)數(shù)為2^n-1(然而知道這點(diǎn)沒用香璃，根本用不上)
如何把k和這個(gè)數(shù)組(B)聯(lián)系起來呢。
再舉一個(gè)例子
A[3]= 1 , 2 , 8
0 1 2
B[7]= 1 , 2 , 1+2 , 8 , 8+1 , 8+2 , 8+1+2
0 1 2 3 4 5 6
可以看出
B[2]=B[0]+B[1]=A[0]+A[1]
B[4]=B[3]+B[0]=A[2]+A[0]
B[5]=B[3]+B[1]=A[2]+A[1]
B[6]=B[3]+B[2]=A[2]+A[1]+A[0]
是不是發(fā)現(xiàn)了什么規(guī)律
`B[2^l-1](l=0,1,2,3...)都為2^x(x=0,1,2...)舟误。此時(shí)得到的就是結(jié)果`
如果為B[2],B[4],B[5],B[6]葡秒，則需要進(jìn)行遞歸相加
*log(m)/log(2)表示以2為底的向下取整的對(duì)數(shù)*，如log(8)/log(2)=3,log(9)/log(2)=3,log(10)/log(2)=3嵌溢。
...（Ｃ心痢！赖草！一定要多測(cè)試一下学少，理解A和B的關(guān)系，剛才寫解析的時(shí)候把自己給寫暈了）
得到下列結(jié)論
1.如果 m=0 ans=A[0],否則進(jìn)入2
2.如果 m+1=2^(log(m)/log(2)+1),answer=A[log(m)/log(2)+1] 否則進(jìn)入3 (logm/log2 表示以2為底的對(duì)數(shù)秧骑，使用換底公式生成)
3.answer=answer+A[log(m)/log(2)],m=m-2^(log(m)/log(2)),,回到1
代入一個(gè)數(shù)測(cè)試版确，如果m=6
1.m!=0
2.m+1=7!=8
3.m=2,answer=0+A[2]=8,回到1
1.m!=0
2.m+1=3!=4
3.answer=8+A[1]=10,m=0,回到1
1.m=0,返回B[0],answer=10+A[0]=11
# 上碼
```c++
/*
題目描述：
給定x扣囊，k。求滿足x+y=x|y的第k小的正整數(shù)y绒疗。
輸入描述：
每組測(cè)試用例僅包含一組數(shù)據(jù)侵歇，每組數(shù)據(jù)為兩個(gè)正整數(shù)x，k吓蘑。滿足0<x,k<2,000,000,000惕虑。
輸出描述：
輸出一個(gè)數(shù)y
輸入樣例：
5 1
輸出樣例
2
*/
#include <iostream>
#include <math.h>
using namespace std;
const int MAX = 100;//y的范圍沒有限制，限制不能太小
long long int binary_x[MAX];
long long int binary_y[MAX];
void dec2binary(long long int dec, long long int binary[])//十進(jìn)制轉(zhuǎn)二進(jìn)制
{
int i = 0;
while (dec != 0)
{
binary[i++] = dec % 2;
dec /= 2;
}
while (i<MAX)
{
binary[i++] = -1;
}
}
void produce_y()//處理x數(shù)組得到有效y數(shù)組
{
int j = 0;
for (int i = 0; i<MAX; i++)
if (binary_x[i] != 1)
binary_y[j++] = pow((long long)2,(long long) i);
while (j<MAX)
binary_y[j++] = -1;
}
long long int recur_add(long long int m)
{
if (m == 0)
return binary_y[0];
int b = log(m) / log(2) + 1;
if (m + 1 == pow(2, b))
return binary_y[b];
else
return binary_y[b-1] + recur_add(m - pow(2, b-1));
}
int main()
{
int x, k;
cin >> x >> k;
dec2binary(x, binary_x);
produce_y();
cout << recur_add(k - 1);
system("pause");
return 0;
}
