区间或和（C++）
题目描述
求a|(a+1)|(a+2)|…|(b-1)|b。
其中|表示按位或。
输入描述:
多组输入，每行两个数表示a和b
输出描述:
对于每组输入，输出一个数a|(a+1)|(a+2)|…|(b-1)|b。
示例1
输入
99 109
68 77
55 66
34 43
1111234 1114321
输出
111
79
127
47
1179647
备注:
输入不超过10000行，
题目思路1：
优化的暴力求解，即按照题意直接做。
超时代码：
#include <stdio.h>
int main()
{
long long a,b,result;
while( scanf( "%lld%lld",&a,&b ) != EOF )
{
result = a;
for(int i=a;i<b;++i)
{
result |= (i+1);
}
printf("%lld
",result);
}
}
考虑到超时肯定是循环次数太多，再仔细理解题目，发现代码可以优化：
先用示例1的第一组数据来举例说明：
| 十进制 | 二进制 | |
|---|---|---|
| a | 99 | 1100011 |
| a+1 | 100 | 1100100 |
| a+2 | 101 | 1100101 |
| a+3 | 102 | 1100110 |
| a+4 | 103 | 1100111 |
| a+5 | 104 | 1101000 |
| b-4 | 105 | 1101001 |
| b-3 | 106 | 1101010 |
| b-2 | 107 | 1101011 |
| b-1 | 108 | 1101100 |
| b | 109 | 1101101 |
考虑a和b的二进制表示从高到低第一个不同的位i（即这个例子中的第4位），必定b的第i位=1，a的第i位=0（因为a<b）。
那么可以断定，对于答案的二进制表示，
(1) 比第i位更高的那些位一定跟a相同。
(2) 第i位及比第i位更低的那些位一定为1。（是由于把a中比第i位更低的那些位都置为1得到的数一定在区间[a,b]中）
所以，我们没有必要从a | (a+1) | (a+2) | …… | (b-1) | b 这样一个一个按位或。我们可以越阶。
因为你可以发现：
1次循环：99 | 100 = 103
2次循环：103 | 101 = 103
3次循环：103 | 102 = 103
4次循环：103 | 103 =103
5次循环：103 | 104 = 111
6次循环：111 | 105 = 111
7次循环：111 | 106 = 111
8次循环：111 | 107 = 111
9次循环：111 | 108 = 111
10次循环：111 | 109 = 111
这样可以说大多数逐一循环都是在做无用功。只有第1吃循环和第5次循环才是有效的。
得到启发，那么下一步可以改写代码：
解题代码1（C语言）：
#include <stdio.h>
int main()
{
long long a,b;
while( scanf( "%lld%lld",&a,&b ) != EOF )
{
while( a<b ) a |= (a+1);
printf("%lld
",a);
}
}
解题代码1（C++语言）：
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0);//加速
long long a, b;
while( cin>>a>>b )
{
while( a<b ) a |= (a+1);
cout << a << endl;
}
}
题目思路2：
按位或：0|1=1；1|0=1；1|1=1；0|0=0; 即二进制有1则1。
那么其实根据思路1的推断，我们就把比第i个位高的数位全部保留，把比第i个位低的数位全部改为1（即相同部分相同，其他部分都是1），然后再把这个二进制转换为十进制输出即可。
解题代码：
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);//加速
long long a,b;
while( cin >> a >> b )
{
long long cnt = 0; //统计从高位数起，a,b有多少位不一样
//统计不同的个数，当a，b相同时退出循环，
//此时a，b的值都为与b相同的部分
while(a != b)
{
cnt++;
a >>= 1;
b >>= 1;
}
//将截掉不同部分的b左移cnt位，
//同时每左移一次，再b右边加个1(二进制)，
//这样就变成，相同部分相同，其他部分都是1
while(cnt--) b = (b<<1)^1;
cout << b << endl;
}
}