排序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

您可以在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;
}

诀窍是将min/max元素表示为算术运算,而不是分支,然后在对上调用足够的次数来"冒泡"它们.

我已经制作了一个完全通用的版本,使用模板元编程来调用sort正确的次数.这一切都完全按照你希望在我的x86盒子上使用gcc 4.7.0进行内联(尽管call在x86上是无条件的).我还实现了一个abs函数,它避免了x86上的分支(它对整数进行了一些假设,使其不那么便携,它基于gcc的__builtin_absx86实现):

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

Answer 3

你可以写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

我max从这里开始实施@@ David的答案,并且实现min了一点点扭曲.