CodeForces 484A Bits

题目链接：http://codeforces.com/contest/484/problem/A
题目大意：

　　给定一个区间[l, r]，输出这个区间上二进制1的位数最多并且数值最小的数。
分析：

　　典型的位运算
　　需要注意的是，由于数据规模很大，用log2函数会产生超过1e-9以上的误差
代码如下：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3  
  4 #define rep(i,n) for (int i = 0; i < (n); ++i)
  5 #define For(i,s,t) for (int i = (s); i <= (t); ++i)
  6 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
  7 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
  8 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
  9  
 10 #define pr(x) cout << #x << " = " << x << "  "
 11 #define prln(x) cout << #x << " = " << x << endl
 12  
 13 #define LOWBIT(x) ((x)&(-x))
 14  
 15 #define ALL(x) x.begin(),x.end()
 16 #define INS(x) inserter(x,x.begin())
 17  
 18 #define ms0(a) memset(a,0,sizeof(a))
 19 #define msI(a) memset(a,inf,sizeof(a))
 20 #define msM(a) memset(a,-1,sizeof(a))
 21  
 22 #define pii pair<int,int> 
 23 #define piii pair<pair<int,int>,int> 
 24 #define mp make_pair
 25 #define pb push_back
 26 #define fi first
 27 #define se second
 28  
 29 inline int gc(){
 30     static const int BUF = 1e7;
 31     static char buf[BUF], *bg = buf + BUF, *ed = bg;
 32      
 33     if(bg == ed) fread(bg = buf, 1, BUF, stdin);
 34     return *bg++;
 35 } 
 36  
 37 inline int ri(){
 38     int x = 0, f = 1, c = gc();
 39     for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
 40     for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
 41     return x*f;
 42 }
 43  
 44 typedef long long LL;
 45 typedef unsigned long long uLL;
 46 const double EPS = 1e-9;
 47 const int inf = 1e9 + 9;
 48 const LL mod = 1e9 + 7;
 49 const int maxN = 1e5 + 7;
 50 const LL ONE = 1;
 51  
 52 int n;
 53 LL l, r, ans;
 54 // lbit ： l的二进制位数 
 55 // rbit ： r的二进制位数 
 56 // hbit ： r的最高二进制位
 57 LL lbit, rbit, hbit;
 58  
 59 // 二分计算x的二进制位数 
 60 inline int getBits(LL x) {
 61  
 62         int cnt = 1;
 63  
 64         while((x >> 1) != 0) {
 65  
 66             ++cnt;
 67  
 68             x >>= 1;
 69  
 70         }
 71  
 72         return cnt;
 73  
 74 } 
 75  
 76 // 取x的最高二进制位 
 77 inline LL HighBit(LL x) {
 78     while(x & (~LOWBIT(x)) != 0) x &= ~LOWBIT(x);
 79     return x;
 80 } 
 81  
 82 int main(){
 83     cin >> n;
 84     while(n--) {
 85         cin >> l >> r;
 86         ans = 0;
 87         if(r == 0) {
 88             cout << ans << endl;
 89             continue;
 90         }
 91         if(l == 0) ++l;
 92          
 93         lbit = getBits(l);
 94         rbit = getBits(r);
 95         hbit = ONE << (rbit - 1);
 96          
 97         // 把相同的高二进制位取下来 
 98         while(lbit == rbit) {
 99             l &= hbit - 1;
100             r &= hbit - 1;
101             ans += hbit;
102             if(r == 0) break;
103             if(l == 0) ++l;
104             lbit = getBits(l);
105             rbit = getBits(r);
106             hbit = ONE << (rbit - 1);
107         }
108         if(r == 0) {
109             cout << ans << endl;
110             continue;
111         }
112          
113         if(getBits(r + 1) > rbit) ans += r; // 如果r是11111，那直接选r 
114         else ans += hbit - 1; // 否则选01111 
115          
116         cout << ans << endl;
117     }
118     return 0;
119 }
120  
121 /*
122 1
123 7849325874389577 8477432355483974
124  
125 ans:7881299347898367
126 */
View Code