区间或

佚名 / 2024-11-17 / 原文

区间或

给定$l,r$, 求$l\mid l + 1 \mid \dots \mid r - 1 \mid r$

思路一

看$l, r$从最高位到最低位中第一个不同的位第$i$位，$l_i$肯定是$0$, $r_i$肯定是$1$， (因为$r < l$), 比第$i$位高的，所有数都一样，比第$i$位低的肯定位或后的结果是$1$,所以第$i$位之前和$a$一样, 第$i$位及其之后都是$1$就好了

代码

void solve()
{
    int l = 0, r = 0;
    std::cin >> l >> r;
    while(l < r) l |= (l + 1);
    std::cout << l << endl;
}

思路二

考虑优化，我们怎么知道第$i$位是哪一位呢？可以用异或，$l\oplus r$的最高位肯定是上面提到的第$i$位，用$log2()$函数能知道这是第几位

假设我们求出来了第$i$位是第$t$位，我们可以构造一个数$2^{t + 1} - 1$,让这个数去和$l$位或就好了

代码

int get_or(int l, int r)
{
    int t = std::__lg(l ^ r);
    return ((1 << (t + 1)) - 1) | l;
}

例题 CF1981B. Turtle and an Infinite Sequence

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

int get_or(int l, int r)
{
    int t = std::__lg(l ^ r);
    return ((1 << (t + 1)) - 1) | l;
}

void solve()
{
    int n = 0, m = 0, l = 0, r = 0;
    std::cin >> n >> m;
    l = std::max(0ll, n - m) , r = n + m;
    std::cout << get_or(l, r) << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    //freopen("out.txt", "w", stdout);
    int t = 1;
    std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}