信息奥赛题解｜Bits

---

🚀 题目浏览

【题目描述】

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 \le x \le r$, and $popcount(x)$ is maximum possible. If there are multiple such numbers find the smallest of them.

【输入】

The first line contains integer $n$ — the number of queries $(1 \le n \le 10000)$.

Each of the following $n$ lines contain two integers $l_i$, $r_i$ — the arguments for the corresponding query $(0 \le l_i \le r_i \le 10^{18})$.

【输出】

For each query print the answer in a separate line.

【输入样例】

3
1 2
2 4
1 10

【输出样例】

1
3
7

【原题链接】

https://codeforces.com/problemset/problem/484/A

---

☘️ 题解分析

或运算 の 经典使用。

令 $l$ 的二进制从右往左不断添1（通过或运算实现），只要保证当前数始终小于等于 r，就可以得到该区间内二进制 1 最多的值。

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
LL n, l, r;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l >> r;

        LL t = 1;  // t的值取二进制1、10、100、1000...，不断与l或运算
        while ((l | t) <= r) { 
            l = l | t;  // 或运算
            t <<= 1;
        }
        cout << l << endl;
    }

    return 0;
}