最大的位或

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 3589 Accepted Submission(s): 1369

Problem Description

B君和G君聊天的时候想到了如下的问题。

给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。

其中|表示按位或，即C、 C++、 Java中的|运算。

Input

包含至多10001组测试数据。

第一行有一个正整数，表示数据的组数。

接下来每一行表示一组数据，包含两个整数l,r。

保证 0 <= l <= r <= 1018。

Output

对于每组数据输出一行，表示最大的位或。

Sample Input

5

1 10

0 1

1023 1024

233 322

1000000000000000000 1000000000000000000

Sample Output

15

1

2047

511

1000000000000000000

Source

2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）

【分析】

我们想要得到的位或最大，那么进行位或的一个数一定是最右边的数，因为它的二进制位最多假设区间为5-10那我们观察5的二进制有效位是3，10的二进制有效位是4像这样区间的端点的有效位不相同，那么从有效位少的左端点3位增加到4位的过程中一定会出现一个3位都是1的数字，对应于我举得例子就是7，7的二进制为111，那么111和1010或运算得到1111，即15.这就是或运算最大的值。如果区间俩个端点有效位相同假设区间为8-108的二进制是100010的二进制是1010.我们这样想因为他们分别是左右端点，那么从左端点增加至右端点一定不会超过右端点。且因为二进制增加是从末尾增加，那么从8增加到10，一定不会出现1011，因为1011已经大于10，不属于区间了那我们从前往后找，找到8和10的二进制的第一个不同位是第三位。那我们来看10的第三位往后是10，8的第三位往后是00，那么从00增加到10，是不是一定会出现01，也就是小于10的有效位一位的全为1的数字。那么1010和1001或运算为1011，即11再举一个例子：假设区间是16-22他们的二进制分别为10000，10110，首先他们有效位相同，那么从左往右找到第三位开始不同，把前面的忽略，为什么忽略？因为左边的高位即使有0，但是在左端点增加至右端点过程，也不会出现那个位是1得数，因为那个位是1的数肯定大于右端点。忽略前面的位，他们二进制分别是000，110，那么从000增加至110，一定会出现011，对吧。那么最大位或就是10011和10110的或运算结果

---

【代码】

#include
    
     #define ll long longusing namespace std;const int N=1005;ll l,r,ans;ll a[N],b[N];int main(){    int t;    cin>>t;    while(t--)    {        memset(a,0,sizeof(a));        memset(b,0,sizeof(b));        cin>>l>>r;        //十进制转换为二进制         ll n=l,m=r;        int cl=0,cr=0;        while(n)        {            a[cl++]=n%2;            n/=2;        }         while(m)        {            b[cr++]=m%2;            m/=2;        }        ans=0;        for(int i=cr-1;i>=0;i--)        {            if(a[i]==b[i])            {                if(b[i])                {                    ans+=(ll)pow(2,i);                }            }            else            {                ans+=(ll)pow(2,i+1)-1;break;            }        }        cout<
     
      <
     
    

1000010110--- 10000+   111因为中间一定遇到001而R必须选那么001|110——>111