J

B君和G君聊天的时候想到了如下的问题。
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。
其中|表示按位或，即C、 C++、 Java中的|运算。

Input包含至多10001组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每一行表示一组数据，包含两个整数l,r。
保证 0 <= l <= r <= $10^{18}$ Output对于每组数据输出一行，表示最大的位或。Sample Input

5
1 10
0 1
1023 1024
233 322
1000000000000000000 1000000000000000000

Sample Output

15
1
2047
511
100000000000000000


解法: 我的思路是先将最大和最小的数转换成二进制,
如果最小的数的二进制位数 < 最大的数的二进制位数 , 就把最大的每一位都变成1;
如果位数相同,就找到二个二进制中第一次不相同的网站 i ,把 i 和 i 后面的都变成1;

 1 include <iostream>
 2 #include <string.h>
 3 
 4 using namespace std;
 5 
 6 typedef unsigned long long ull;
 7 const int MAX = 200;
 8 int a[2][MAX];
 9 int visit[MAX];
10 
11 void DP_1(int ti2)
12 {
13     ull temp =1;
14     ull sum = 0;
15     for(int i = 0;i <= ti2 -1;i++)
16     {
17         if(i!=0) temp *= 2;
18         if(visit[i]==1)
19         {
20             sum += temp;
21         }
22     }
23     cout<<sum<<endl;
24 }
25 
26 void DP(int ti1,int ti2)
27 {
28     int temp = -1;
29     for(int i = ti1 -1;i>=0;i--)
30     {
31         if(a[0][i]!=a[1][i])
32         {
33             temp = i;
34             break;
35         }
36     }
37 
38     for(int i = ti2 - 1;i >=0;i--)
39     {
40         if(i<=temp)
41             visit[i] = 1;
42         else
43             visit[i] = a[1][i];
44     }
45 }
46 
47 int two(ull x,int n)
48 {
49     int ti = 0;
50     if(x==1||x==0)
51     {
52         a[n-1][ti++] = x;
53         return ti;
54     }
55 
56     while(1)
57     {
58         a[n-1][ti++] = x % 2;
59         x = x / 2;
60         if(x == 1)
61         {
62             a[n-1][ti++] = x;
63             break;
64         }
65     }
66     return ti;
67 
68 }
69 
70 int main()
71 {
72     int N;
73     cin>>N;
74     while(N--)
75     {
76         memset(visit,0,sizeof(visit));
77         int ti1,ti2;
78         ull x,y;
79         cin>>x>>y;
80         ti1 = two(x,1);
81         ti2 = two(y,2);
82 
83         if(ti1<ti2)
84         for(int i = ti2-1;i >=0;i--)
85             visit[i] = 1;
86         else if(ti1 == ti2)
87             DP(ti1,ti2);
88 
89    /*     for(int i = ti2 -1;i >=0;i--)
90             cout<<visit[i];
91         cout<<endl;
92     */
93         DP_1(ti2);
94 
95     }
96 
97 
98     return 0;
99 }