一个关于按位或的故事~~（QDU-码农必修）
今天本是集训队集体刷cf之日，可本人的电脑于进行中途中，断网而终。。更是让本人无奈的是：手机打不开vj。于是好烦的来到qduoj，本市找了到dp的题想做，却它丫的找不到思路，然后更烦了，心累。。
于是就看到这题：码农必修，一个考察二进制或者按位或的题目。
先上题目
码农必修
发布时间: 2016年5月2日 21:03 最后更新: 2016年5月2日 21:05 时间限制: 1000ms 内存限制: 128M
给你 x, k, 求满足 x + y= x | y 这个公式的第 k 小的正整数y。
哦对，“|”表示的是二进制里面的按位或操作
输入文件中包含多组数据，每组数据为两个正整数 x , k。
满足（0 < x , k ≤ 2,000,000,000）。
输出一个数y
5 1
2
这题想了一老会才有的思路，可最后回到宿舍交的时候WA好多次，为什么呢？？因为题目是多组数据。
思路：如果使 x | y = x + y, 很容易知道，只有y的二进制形式1所在的位置在x的二进制0所在的位置。
例： 5: 101，值y若能使5与其按位或与相加相等，则有 010, 1000, 1010;
所以所以很容易会想到求得数便是在5的二进制的0所在位置添加若干个1的过程。
所以，下面便是找填1的规律，首先先来一个白板 ：0 0 0 0
a b c d
现在在d的位置及其之后的位置换1，只有1种方法 0 0 0 1
在c的位置及其之后的位置换1，有3种方法 0 0 0 1, 0 0 1 0, 0 0 1 1;
在b的位置及其之后的位置换1，有7种方法 0 0 0 1 ... 0 1 1 1;
此时规律显而易见了。
那么如何应用此规律呢，题目要求第k小的满足要求的数，那么就把k换成二进制形式，例如k: 10011, 要求第k小的数，所以前10000的数，就是在前4个零不断添加若干1，共2^4-1个，然后加上10000共2^4个，所以在可换1的位置的第五个位置换成1，便代表前2^4小的满足要求的数（这儿最好自己写写+思考便能理会），然后用k-2^4，此时范围缩小至00011，不断如此缩小，当k缩至0时，答案便已经出来了。
代码如下：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define LL long long
using namespace std;
int jk[64] = {0};
int main(){
LL i, x, k, p, kp, l, index, ans, base;
while(~scanf("%lld %lld", &x, &k)){
memset(jk, 0, sizeof jk);
p = x, l = 1;
while(p){
jk[l++] = p%2; //把原数换成二进制形式放入数组，方便之后查询可换成1的0的位置
p >>= 1;
}
while(k){
p = k, kp = 0, index = 0;
while(p){
++kp; //计算此时的k的二进制位数
p >>= 1;
}
for(i = 1;1; ++i){
if(jk[i]==0) ++index;
if(index == kp) break; //找到第kp个0的位置
}
jk[i] = -1; //将之换成-1方便后面求ans
k -= pow(2, kp-1);
}
ans = 0, base = 1;
for(i = 1; i <= 64; ++i){ //其实用不到64位的，但也不知道具体到哪，用64以防意外
if(jk[i] == -1)
ans += base; //当遇到自己放1的位置不断将二进制换成十进制数
base <<= 1;
}
printf("%lld\n", ans);
}
return 0;
}此题是一道思维题，加深我们对二进制和位运算的理解，继续加油~