最大的位或

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

Total Submission(s): 655    Accepted Submission(s): 293

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

 

 

 

//第一次做位运算有关的题目，贪心方案想了好久。。。

1 #include 
       
          2 #include 
        
           3   4 typedef long long LL;  5   6 LL l,r,Max;  7 char bit_l[300];  8 char bit_r[300];  9 char temp[300]; 10  11 LL StrToNum(char s[])//二进制字符变数字 12 { 13     int len=strlen(s); 14     LL ans=0,res=1; 15     for (int i=len-1;i>=0;i--) 16     { 17         if (s[i]=='1') 18             ans+=res; 19         res*=2; 20     } 21     return ans; 22 } 23  24 void NumToStr(LL x)//数字变二进制字符串 25 { 26     if (x==0) 27     { 28         temp[0]='0'; 29         temp[1]='\0'; 30         return ; 31     } 32     char s[300]; 33     int pos=0; 34     while (x!=0) 35     { 36         int tt=x%2; 37         if (tt==1) 38             s[pos++]='1'; 39         else if (tt==0) 40             s[pos++]='0'; 41         x/=2; 42     } 43     s[pos]='\0'; 44     int i; 45     for (i=0;i
         
          Max) Max=res; 92         //printf("l : %s\n",bit_l); 93         //printf("r : %s\n",bit_r); 94         //printf("t : %s\n",test); 95         int k=0; 96         while (bit_l[k]==bit_r[k]) k++; 97         k++; 98         for (i=k;i
          
           Max) Max=res;102             if (bit_l[i]=='0'&&bit_r[i]=='0')103             {104                 test[i]='1';105                 res=StrToNum(test);106                 if (res>Max)107                     Max=res;108             }109         }110         printf("%I64d\n",Max);111     }112     return 0;113 }