题目描述
Description
Let’s denote as popcount($x$) the number of bits set (‘1’ bits) in the binary representation of the non-negative integer $x$.
You are given multiple queries consisting of pairs of integers $l$ and $r$. For each query, find the $x$, such that $l$ ≤ $x$ ≤ $r$, and popcount($x$) is maximum possible. If there are multiple such numbers find the smallest of them.
Input
The first line contains integer $n$ — the number of queries (1 ≤ $n$ ≤ 10000).
Each of the following $n$ lines contain two integers $l_i$, $r_i$ — the arguments for the corresponding query (0 ≤ $l_i$ ≤ $r_i$ ≤ $10^{18}$).
Output
For each query print the answer in a separate line.
Sample test(s)
| input |
|---|
| 3 |
| 1 2 |
| 2 4 |
| 1 10 |
| output |
|---|
| 1 |
| 3 |
| 7 |
Note
The binary representations of numbers from 1 to 10 are listed below:
$1_{10} = 1_2$
$2_{10} = 10_2$
$3_{10} = 11_2$
$4_{10} = 100_2$
$5_{10} = 101_2$
$6_{10} = 110_2$
$7_{10} = 111_2$
$8_{10} = 1000_2$
$9_{10} = 1001_2$
$10_{10} = 1010_2$
题目链接
http://codeforces.com/problemset/problem/485/C
解题思路
题目大意是给定一个区间[l, r]，求这个区间里的数在转化为二进制的情况下，1的个数最多的数字；同时，当1的个数相同的时候，输出数最小的那个。
首先设置一个数组，用来存储1、10、100、1000这些二进制数，然后对这些数进行累加，直到大于等于r为止。此时的sum就是1的个数最多的那个数，但是有可能不在这个区间中，所以我们需要进行判断。假如他大于r的话，就减去最后相加的那个数，这样可以保证得出的结果是区间中1最多的但是数值最小的。
AC代码
31 ms/0 KB/GNU C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#include <cstdio>
typedef long long ll;
ll bit[65];
int main()
{
bit[0] = 1;
for (int i = 1; i <= 63; i++)
{
bit[i] = 2 * bit[i - 1];
}
int t;
ll l, r, sum;
scanf("%d", &t);
while (t--)
{
sum = 0;
scanf("%I64d%I64d", &l, &r);
int i;
for (i = 0; sum <= r; i++)
{
sum += bit[i];
}
i--;
while (sum > r)
{
sum -= bit[i];
if (sum < l)
sum += bit[i];
i--;
}
printf("%I64d\n", sum);
}
return 0;
}