对 3 个数字进行排序而不进行分支

Question

在 C# 或 C++ 中，如何实现三个（整数）数字的无分支排序？

这可能吗？

Answer 1

没有条件。仅对 uint 进行强制转换。完美的解决方案。

int abs (int a) 
{
    int b = a;
    b = (b >> (sizeof(int)*CHAR_BIT-1) & 1);
    return 2 * b * (a) + a; 
}
int max (int a, int b) { return (a + b + abs(a - b)) / 2; }
int min (int a, int b) { return (a + b - abs(a - b)) / 2; }


void sort (int & a, int & b, int & c)
{       
   int maxnum = max(max(a,b), c);
   int minnum = min(min(a,b), c);
   int middlenum = a + b + c - maxnum - minnum;
   a = maxnum;
   b = middlenum;
   c = minnum;
}

Answer 2

您可以编写

max

、

min

和

swap

无分支函数。一旦有了这些函数，您就可以使用它们将

sort

函数编写为：

void sort(int &a, int &b, int &c)
{
    int m1 = max(a,b,c);
    int m2 = min(a,b,c);
    b = a + b + c - m1 - m2;
    swap(m1, a);
    swap(m2, c);
}

这是辅助函数：

void swap(int &a, int &b)
{
   int tmp = a; a = b; b = tmp;
}

int max( int a, int b, int c ) {
   int l1[] = { a, b };
   int l2[] = { l1[ a<b ], c };
   return l2[ l2[0] < c ];
}
int min( int a, int b, int c ) {
   int l1[] = { a, b };
   int l2[] = { l1[ a>b ], c };
   return l2[ l2[0] > c ];
}

测试代码：

int main() {
        int a,b,c;
        std::cin >> a >> b >> c;
        sort(a,b,c);
        std::cout << a <<"," << b << "," << c << std::endl;
        return 0;
}

输入：

21 242 434

输出（降序）：

434, 242, 21

演示：http://ideone.com/3ZOzc

我从

here

的@David的回答中获取了max的实现，并稍加改动地实现了

min

。

Answer 3

您可以在 C++ 中使用以下方法执行此操作：

#include <iostream>

void sort(int *in) {
  const int sum = in[0]+in[1];
  const int diff = abs(in[1]-in[0]);
  in[0] = (sum + diff) / 2;
  in[1] = (sum - diff) / 2;
}

int main() {
  int a[] = {3,4,1};
  sort(a);
  sort(a+1);
  sort(a);
  std::cout << a[0] << "," << a[1] << "," << a[2] << std::endl;

  int b[] = {1,2,3};
  sort(b);
  sort(b+1);
  sort(b);
  std::cout << b[0] << "," << b[1] << "," << b[2] << std::endl;
}

技巧在于将最小/最大元素表示为算术运算，而不是分支，然后对对调用排序足够多次以对它们进行“冒泡排序”。

---

我制作了一个完全通用的版本，使用模板元编程来调用

sort

正确的次数。这一切都按照您在 x86 机器上使用 gcc 4.7.0 所希望的那样内联（尽管

call

无论如何在 x86 上是无条件的）。我还实现了一个避免在 x86 上分支的 abs 函数（它对整数做了一些假设，这使得它的可移植性较差，但它是基于 gcc 对 x86 的

__builtin_abs

实现）：

#include <iostream>
#include <limits.h>

void myabs(int& in) {
  const int tmp = in >> ((sizeof(int) * CHAR_BIT) - 1);
  in ^= tmp;
  in = tmp - in;
}

template <int N, int I=1, bool C=false>
struct sorter {
  static void sort(int *in) {
    const int sum = in[I-0]+in[I-1];
    int diff = in[I-1]-in[I-0];
    myabs(diff);
    in[I-0] = (sum + diff) / 2;
    in[I-1] = (sum - diff) / 2;
    sorter<N, I+1, I+1>=N>::sort(in);
  }
};

template <int N,int I>
struct sorter<N,I,true> {
  static void sort(int *in) {
    sorter<N-1>::sort(in);
  }
};

template <int I, bool C>
struct sorter<0,I,C> {
  static void sort(int *) {
  }
};

int main() {
  int a[] = {3,4,1};
  sorter<3>::sort(a);
  std::cout << a[0] << "," << a[1] << "," << a[2] << std::endl;
}