c++ - 整数的字典序比较

Question

我想按字典顺序比较两个小的 (<=20) 整数集 (1..20)。

集合由单个整数表示，例如
1, 2, 4, 6
将表示为

 ... 0 1 0 1 0 1 1
(... 7 6 5 4 3 2 1)

所以在集合中有 1 的地方。

有人可以验证此代码是否正确吗？

bool less_than(unsigned a, unsigned b) {
    unsigned tmp = a ^ b;
    tmp = tmp & (~tmp + 1); //first difference isolated
    return (tmp & a) && (__builtin_clz(b) < __builtin_clz(tmp));
}

__builtin_clz 部分适用于 b 是 a 的前缀的情况。
空集的情况在别处处理(__builtin_clz 未定义为 0)。

编辑:

bool less_than(unsigned a, unsigned b) {
    unsigned tmp = a ^ b;
    tmp &= -tmp; //first difference isolated
    return ((tmp & a) && (__builtin_clz(b) < __builtin_clz(tmp)))
            || (__builtin_clz(a) > __builtin_clz(tmp));
}

和

bool less_than_better(unsigned a, unsigned b) {
    unsigned tmp = a ^ b;
    tmp &= -tmp; //first difference isolated
    return ((tmp & a) && tmp < b) || tmp > a;
}

似乎都是正确的。(在数以千万计的随机测试中使用 std::lexicographical_compare 测试与原始实现相比)

第二个更便携，因为它不使用 __builtin_clz。
我机器上的速度差异可以忽略不计(第二个速度快约 2%)，但是在没有将 __builtin_clz 作为一条处理器指令的机器上(例如 x86 上的 BSR)，差异可能会很大。

Answer 1

在 a == 0 的情况下是不正确的。这应该返回 true 除非 b == 0，但是因为 tmp & a 将是 false 而不管 tmp 的值(这将是b) 中的最低位 1 位)，该函数将返回 false。

a 应该“小于”b 如果:

1. `a` is a proper prefix of `b`, or
2. The lowest-order bit of `a^b` is in `a`.

第一个条件也处理 a 是空集而 b 不是的情况。 (这与您的公式略有不同，它是“(a^b 的最低位在 a 中)而不是 (b 是 a 的正确前缀)。)

假设我们有 a 的最低位这一事实，“a 是 b 的正确前缀”的简单测试tmp中的^b，是tmp>a。这避免了使用 __builtin_clz [注 1]。

另外，你可以这样写

tmp = tmp & (~tmp + 1);

作为

tmp &= -tmp;

但我认为大多数 C 编译器会自行找到优化。 [注2].

应用这些优化，结果将是(未经测试):

bool less_than(unsigned a, unsigned b) {
    unsigned tmp = a ^ b;
    tmp &= -tmp; //first difference isolated
    return tmp > a || tmp & a;
}

---

注意事项

1. 这是值得做的，因为 (1) 尽管 __builtin_clz 是内置的，但它不一定超快； (2) 如果您使用 gcc 或 clang 以外的编译器进行编译，它可能不存在。

如果 tmp 是无符号类型，则

2. -tmp 保证是 tmp 的 2s 补码负数，即使底层实现不是 2s 补码。参见 §6.2.6.2/1(无符号类型的范围是 0..2^N-1 对于某些整数 N)和 &6.3.1.3/2(负值转换为无符号整数类型，通过重复添加 2^N 直到值在范围内。