贪心、位运算

答案显然是在 $[\max(n-m,0),n+m]$ 内的整数的按位或和。

常规做法。令 $l=\max(n-m,0),r=n+m$，结果为 $ans = l \operatorname{or} r$。找到 $l,r$ 二进制意义下不相同的最高二进制位（由于 $l \leq r$ 当 $l \neq r$ 时 $r$ 这个位上肯定为 $1$ 且 $l$ 这个位上为 $0$），然后把 $ans$ 中比这个二进制位低的所有二进制位置 $1$ 即可。按照这个思路可以做到 $O(1)$ 求区间按位或和。

但是，求 $\operatorname{or} \limits_{i=l}^{r} i$ 存在相当简洁的做法。

int solution(int l,int r){
    int ret=l;
    while(ret<r) ret|=ret+1;
    return ret;
}

首先由于循环中 $ret<r$ 所以每次被或上的 $ret+1$ 都不超过 $r$，而 $ret+1$ 的操作实质是把 $ret$ 二进制下最低位的 $0$ 变成 $1$，这样每一次循环都有一个 $0$ 变成 $1$，所以循环次数是 $O(\log (n+m))$ 的。

由于 $n,m$ 同阶，时间复杂度 $O(\log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
void solution(){
    cin>>n>>m;
    ans=max(n-m,0);
    while(ans<n+m) ans|=ans+1;
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}

举一反三，按位与和按位或运算本质相同，无非是把 $0$ 变成 $1$ 而已，将 $l,r$ 按位取反之后按照大小关系重新标号，最后把结果取反即可。也可以照葫芦画瓢写出如下代码。

int solution(int l,int r){
    int ret=r;
    while(ret>l) ret&=ret-1;
    return ret;
}

按位异或则不太一样，但异或有高贵的可减性，所以可以先求 $\operatorname{xor}\limits_{i=1}^{l-1} i$ 和 $\operatorname{xor}\limits_{i=1}^{r} i$ 的值再异或一下得到区间 $[l,r]$ 中所有整数的异或和。现在问题是如何求 $\operatorname{xor}\limits_{i=1}^{n} i$ 的值。

打表找规律可以发现结论，证明问了 zmy123456 正在等回复。

$$\operatorname{xor}\limits_{i=1}^{n} i = \begin{cases} n & n \equiv 0 \ (\bmod\ 4) \\ 1 & n \equiv 1 \ (\bmod\ 4) \\ n+1 & n \equiv 2 \ (\bmod\ 4) \\ 0 & n \equiv 3 \ (\bmod\ 4) \end{cases}$$

然后 zmy 跟我说数学归纳法秒了，我想了想发现确实，我说确实。

顺带记录一下子集枚举的手法，这是状压的常用技巧。

这一段会遍历所有状态的子状态，但被遍历到的状态不包含 $0$。无论是否遍历 $0$ 代码的时间复杂度都为 $O(3^n)$，这是容易通过组合意义或二项式反演证明的。

    const int lim=(1<<n)-1;
    for(int i=1;i<=lim;i++)
        for(int j=i;j;j=(j-1)&i){
            //do something
        }

遍历到的状态包含 $0$ 的版本如下。

    const int lim=(1<<n)-1;
    for(int i=0;i<=lim;i++)
        for(int j=i;;j=(j-1)&i){
            //do something
            if(j==0) break;
        }

每次 j=(j-1)&i 可以分成两段看，将 $j$ 减去 $1$ 即删除状态 $j$ 二进制下最低的等于 $1$ 的位并将比这一位更低的所有 $0$ 变成 $1$，这之后对 $i$ 进行的按位与删除了所有不在 $i$ 中的位。

由于减去 $1$ 的操作不可逆，整个过程不会重复遍历任何状态。