牛客332G-区间或和

题目

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

求$a|(a+1)|(a+2)|…|(b-1)|b$。

其中|表示按位或

输出描述

1
对于每组输入，输出一个数a|(a+1)|(a+2)|...|(b-1)|b。

示例1

输入

1
2
3
4
5
99 109
68 77
55 66
34 43
1111234 1114321

输出

1
2
3
4
5
111
79
127
47
1179647

备注

输入不超过10000行，$0≤a,b≤10^{18}，a≤b$

解析

如果 a=b ，那么答案 =a ；

否则 a≠b ，

考虑a和b的二进制表示从高到低第一个不同的位i，

必定b的第i位=1，a的第i位=0。

那么可以断定，对于答案的二进制表示，

(1) 比第i位更高的那些位一定跟a相同。

(2) 第i位及比第i位更低的那些位一定为1。

(1)是显然的，(2)是由于把a中比第i位更低的那些位都置为1得到的数一定在区间[a,b]中

参考：

https://ac.nowcoder.com/discuss/153349?type=101&order=0&pos=8&page=1

举个例子

  1. [2300，2323]：

    2300： 100011111100

    2323: 100100010011

    总的结果就是2559： 100111111111

  2. [787，2323]：

    787： 001100010011

    2323: 100100010011

    而这个 我们注意到前面段是没有相同，那也就是可变化范围就是那整段了。

    所以答案就是：4095：111111111111

参考：

http://keyblog.cn/article-67.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
提交时间：2019-02-09 18:48:22 语言：C++14 代码长度：797 运行时间： 29 ms 占用内存：868K 
运行状态：答案正确
*/
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <set>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <bitset>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+10;
const int INF = 0xffffff;
const int MAXN = 1e5+5;

int arr[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll a, b;
    while(cin >> a >> b)
    {
        ll 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;
    }
    return 0;
}