二进制表示法中范围[a，b]中的最小数，最大数为“1”

Question

给定一个范围[a，b]（包含两者），我需要在二进制表示中找到最大数量为“1”的最小数字。我目前的方法是找到从a到b的所有数字中设置的位数，并跟踪最大值。然而，这很慢，有更快的方法吗？

Answer 1

您可以将 Jarlax 答案中的循环替换为“并行后缀 OR”，如下所示

uint32_t m = (a ^ b) >> 1;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
uint32_t res = a | m;
if ((res | b) <= b)
    res = b;
return res;

它通常使用ceil（log（k））步骤来概括不同大小的整数。初始测试a==b是不必要的，a^b将为零，因此

或者，这里有一个完全不同的方法:不断将最低的0改为1，直到不再可能。

unsigned x = a;
while (x < b) {
    unsigned newx = (x + 1) | x; // set lowest 0
    if (newx <= b)
        x = newx;
    else
        break;
}
return x;

Answer 2

让我们找出a和b中不同的最高有效位。它将是a中的0，b中的1。如果我们将所有其他位放在1的右边，得到的数字仍在范围[a；b]中。它将是表示最大个数的单个数字。

编辑。此算法的结果始终返回 n-1 位设置为 1 的数字，其中 n 是可以更改的位数。正如注释中所指出的 - 如果b中的所有n位都设置为1，则存在错误。以下是固定的代码片段：

int maximizeBits(int a, int b) {
    if (a == b) {
        return a;
    }
    int m = a ^ b, pow2 = 1; // MSB of m=a^b is bit that we need to find
    while (m > pow2) { // Set other bits to 0
        if ((m & pow2) != 0) {
            m ^= pow2;
        }
        pow2 <<= 1;
    }

    int res = a | (m - 1); // Now m is in form of 2^n and m - 1 would be mask of n-1 bits
    if ((res | b) <= b) { // Fix of problem if all n bits in b are set to 1
        res = b;
    }
    return res;
}