使用C++找出在第L个和第R个索引之间只有设置位的数字

什么是只有设置位的数字？

只有设置位的数字指的是二进制表示下只有一些特定位被设置成1，其余位都是0的数字。例如，101、1000、11000等都是只有设置位的数字。

如何找出在第L个和第R个索引之间只有设置位的数字？

暴力枚举

我们可以从第L个数字开始往后枚举，一直到第R个数字。在每一个数字上，我们可以逐位判断是否只有一个位被设置成1。

vector<int> findNumbers(int L, int R) {

    vector<int> res;
    for (int i = L; i <= R; ++i) {
        int num = i, cnt = 0;
        while (num) {
            cnt += num & 1;
            num >>= 1;
        }
        if (cnt == 1) {
            res.push_back(i);
        }
    }
    return res;
}

这个算法的时间复杂度是O((R ? L + 1) log N)，其中N是数字的范围。在数字范围很大时，这个算法的效率较低。

位运算

我们也可以使用位运算来快速判断一个数字是否只有一个位被设置成1。对于任意一个二进制表示下只有一个位被设置成1的数字，我们将这个数减去1并与原数取&操作，得到的结果一定是0。例如，6的二进制表示是110，减去1后得到101，将101与110取&操作，得到的结果是100，也就是把110中最后一个1变成了0，得到了100。对于任意一个二进制表示下不只一个位被设置成1的数字，我们都无法通过这个方法得到0。

因此，我们可以遍历[L, R]区间内的所有数字，依次进行判断。如果一个数字num满足(num & (num - 1)) == 0，那么它就是只有设置位的数字。

vector<int> findNumbers(int L, int R) {

    vector<int> res;
    for (int i = L; i <= R; ++i) {
        if ((i & (i - 1)) == 0) {
            res.push_back(i);
        }
    }
    return res;
}

这个算法的时间复杂度是O(R ? L + 1)。

完整代码

// 暴力枚举

vector<int> findNumbers(int L, int R) {
    vector<int> res;
    for (int i = L; i <= R; ++i) {
        int num = i, cnt = 0;
        while (num) {
            cnt += num & 1;
            num >>= 1;
        }
        if (cnt == 1) {
            res.push_back(i);
        }
    }
    return res;
}
// 位运算
vector<int> findNumbers(int L, int R) {
    vector<int> res;
    for (int i = L; i <= R; ++i) {
        if ((i & (i - 1)) == 0) {
            res.push_back(i);
        }
    }
    return res;
}