自动搬运

查看原文

来自洛谷，原作者为

	沉石鱼惊旋 已完成今日我对着铁质的凳子踢了五下然后把那堆钢栏杆在地上滚了一下然后把椅子夹在了篮筐上大学习

搬运于2025-08-24 21:16:20，当前版本为作者最后更新于2024-06-06 12:46:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个很小朋友的做法是把每个数转二进制字符串或者用数组存下来判断。这里给一个时间复杂度为 $\mathcal O(n\log V)$ 但空间复杂度为 $\mathcal O(1)$ 的写法：使用位运算，通过 x >> i & 1 获得 $x$ 在二进制下的第 $i$ 位。

#include <bits/stdc++.h>
using namespace std;
int a, b;
int ans;
bool check(int x)
{
    for (int i = 30; i >= 0; i--)
    {
        if ((i < 30 ? (x >> i + 1 & 1) ^ (x >> i & 1) : 1) && (i > 0 ? (x >> i & 1) ^ (x >> i - 1 & 1) : 1))
            return 0;
    }
    return 1;
}
int main()
{
    cin >> a >> b;
    for (int i = a; i <= b; i++)
        ans += check(i);
    cout << ans << endl;
    return 0;
}