c++ - 找出(在 C++ 中)二进制数是否是另一个的前缀

Question

我需要一个带有这样标题的函数:

bool is_prefix(int a, int b, int* c) {
    // ...
}

如果 a 是，读取为二进制数字字符串，b 的前缀，然后将 *c 设置为 b 的其余部分(即“b 比 a 多”)并返回 true。否则，返回假。假设二进制字符串总是以“1”开头。

当然 - 通过逐位比较很容易做到(左移 b 直到 b==a)。但是有没有更有效的解决方案，无需迭代位？

示例:a=100 (4), b=1001 (9)。现在将 *c 设置为 1。

Answer 1

可以用自己喜欢的"fast" method to find the highest set bit .让我们调用函数 msb()。

bool is_prefix (int a, int b, int *c) {
    if (a == 0 || b == 0 || c == 0) return false;
    int d = msb(b) - msb(a);
    if (d < 0) return false;
    if ((b >> d) == a) {
        *c = b ^ (a << d);
        return true;
    }
    return false;
}

移位 b 使其高位与 a 对齐，并将其与 a 进行比较。如果它们相等，则 a 是 b 的“前缀”。

该算法的性能取决于msb() 的性能。如果它是常数，那么这个算法是常数。如果 msb() 开销很大，那么“简单方法”可能是最快的方法。