整数的字典序比较

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

这是计算 2 位输入的所有组合的清单：

#include <stdio.h>

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));
}

#define BITPATTERN "%d%d%d"
#define BYTETOBITS(byte)  \
  (byte & 0x04 ? 1 : 0), \
  (byte & 0x02 ? 1 : 0), \
  (byte & 0x01 ? 1 : 0) 

int main(int argc, char** argv) {
  for ( int a = 0; a < 4; a ++ )
    for ( int b = 0; b < 4; b ++)
      printf("a: "BITPATTERN" b: "BITPATTERN": %d\n",
        BYTETOBITS(a), BYTETOBITS(b), less_than(a,b)
      );
}

这是输出：

a: 000 b: 000: 0
a: 000 b: 001: 0
a: 000 b: 010: 0
a: 000 b: 011: 0
a: 001 b: 000: 0
a: 001 b: 001: 0
a: 001 b: 010: 1
a: 001 b: 011: 0
a: 010 b: 000: 0
a: 010 b: 001: 0
a: 010 b: 010: 0
a: 010 b: 011: 0
a: 011 b: 000: 0
a: 011 b: 001: 0
a: 011 b: 010: 1
a: 011 b: 011: 0

好像不太对..

Answer 2

在a == 0的情况下是不正确的。这应该 return 为真，除非 b == 0，但由于 tmp & a 将是假的，无论 tmp 的值如何（这将是 b 中的最低阶 1 位），该函数将 return 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是b的正确前缀”，因为我们在[=中有a^b的最低位17=]，是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) 尽管 __builtin_clz 是内置的，但它不一定超快； (2) 如果您使用 gcc 或 clang 以外的编译器进行编译，它可能不存在。
-tmp 保证是 tmp 的 2s-补负如果 tmp 是无符号类型，即使底层实现不是 2s-补充。见§6.2.6.2/1（无符号类型的范围是 0..2^N-1 对于一些整数 N）和 &6.3.1.3/2（负值是通过重复添加 2^N 直到值在范围内，将其转换为无符号整数类型。

整数的字典序比较

Lexicographical comparison of integers

c++

bit-manipulation

备注