Codeforces 276D. Little Girl and Maximum XOR（模拟）

ゞ浴缸里的玫瑰 2022-06-07 13:16 225阅读 0赞

A little girl loves problems on bitwise operations very much. Here's one of them.

You are given two integers *l* and *r*. Let's consider the values of ![4044ca87d9d7298f84b83138e9d1049c_v_1508041262][] for all pairs of integers *a* and *b* (*l* ≤ *a* ≤ *b* ≤ *r*). Your task is to find the maximum value among all considered ones.

Expression ![b6c25253add7f19654760f9ea40fe9c0_v_1508041262][] means applying bitwise excluding or operation to integers *x* and *y*. The given operation exists in all modern programming languages, for example, in languages *C*\++ and *Java* it is represented as "^", in *Pascal* — as «xor».

Input

The single line contains space-separated integers *l* and *r* (1 ≤ *l* ≤ *r* ≤ 1018).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

In a single line print a single integer — the maximum value of ![4044ca87d9d7298f84b83138e9d1049c_v_1508041262][] for all pairs of integers *a*, *b* (*l* ≤ *a* ≤ *b* ≤ *r*).

Example

Input

1 2

Output

Input

8 16

Output

Input

1 1

Output

题解：

看起来很难其实想清楚了就很水的一题，就是求数组x，y之间的数异或的最大值

思路：

最后找规律可以发现只要把x，y都转化为二进制，从高位往低位找到第一个“1 0”（顺序不能反）情况，记录下位置，然后输出pow（2，tag+1）-1就行了

原理是可以把该位后面的数字改成每一位是0 1或者1 0，也就是异或一定为1,

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    #define ll long long
    #define INF 1008611111
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    int main()
    {
        int a[105],b[105],c[105],len1=0,len2=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        ll l,r,i,j;
        scanf("%lld%lld",&l,&r);
        if(l==r)
        {
            printf("0\n");
            return 0;
        }
        while(l!=0)
        {
            a[len1]=l%2;
            l/=2;
            len1++;
        }
        while(r!=0)
        {
            b[len2]=r%2;
            r/=2;
            len2++;
        }
        int tag=0;
        for(i=max(len1,len2)-1;i>=0;i--)
        {
            if(b[i]==1&&a[i]==0)
            {
                tag=i;
                break;
            }
        }
        printf("%lld\n",(ll)pow(2,tag+1)-1);
        return 0;
    }

[4044ca87d9d7298f84b83138e9d1049c_v_1508041262]: https://odzkskevi.qnssl.com/4044ca87d9d7298f84b83138e9d1049c?v=1508041262
[b6c25253add7f19654760f9ea40fe9c0_v_1508041262]: https://odzkskevi.qnssl.com/b6c25253add7f19654760f9ea40fe9c0?v=1508041262