c - 有没有一种方法可以在不使用大量分支语句的情况下为无符号整数编写 qsort 比较函数？

Question

我为其中包含一些无符号字段的结构编写了一个(qsort 兼容的)比较函数:

typedef struct {
   int      a;
   unsigned b;
} T;

int cmp(T t1, T t2)
{
   // Decreasing order in "a"
   if (t1.a < t2.a) return +1;
   if (t1.a > t2.a) return -1;
   // Increasing order in "b"
   if (t1.b < t2.b) return -1;
   if (t1.b > t2.b) return +1;
   return 0;
}

有没有一种方法可以编写此函数而不需要对每个字段进行两次比较？我不能使用 t1.b - t2.b 技巧，因为无符号整数的减法回绕。

我愿意接受使用 GCC 扩展的答案。

Answer 1

使用更广​​泛的数学。

给定int和 unsigned字段，给定的平台很可能支持更广泛的整数类型，例如 long long可以将这两个放在一起。

int cmp(T t1, T t2)
{
   // An optimized compilation will not do any multiplication nor addition,
   // Just simply load `n1` high/low halves with `t1.a`, `t1.b`.
   long long n1 = t1.a * (UINT_MAX + 1LL) + t1.b;
   long long n2 = t2.a * (UINT_MAX + 1LL) + t2.b;
   return (n1 > n2) - (n1 < n2);  
}

如果这种方法更快 - 分析将针对特定平台回答这个问题。

虽然这使用较少的比较，但比较使用更广泛的数学 - 可能是零和增益。

当 2x 整数宽度可用时，如 How to determine integer types that are twice the width as `int` and `unsigned`? .这行得通。为了实现高可移植性，请坚持使用 OP 的原始方法。

(var1 > var2) - (var1 < var2)被一些人认为是无分支的。当然 OP 的原始代码可以以:

return (t1.b > t2.b) - (t1.b < t2.b);