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

Question

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

Answer 1

让我们找出a和b中不同的最高有效位。它将在 a 中为 0，在 b 中为 1。如果我们将所有其他位放在 1 的右边 - 结果数字仍将在范围 [a; b].并且它将是表示中个数最多的单个数。

编辑。该算法的结果总是 returns 将 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;
}

Answer 2

您可以用 "parallel suffix OR" 替换 Jarlax 答案中的循环，像这样

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 将为零，因此 m 为零，因此没有任何有趣的事情发生。

或者，这是一种完全不同的方法：不断将最低的 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;

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

Smallest number in a range [a,b] with maximum number of '1' in binary representation

algorithm

bit-manipulation