分岐せずに3つの数値を並べ替える

Question

C＃またはC++では、3つの（整数）数値のブランチのない並べ替えをどのように実装できますか？

これは可能ですか？

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

。

---

私は倍のsort右の番号に電話して、テンプレートメタプログラミングを使用して、完全にジェネリック版を作りました。私のx86ボックスでgcc 4.7.0を望むのとまったく同じようにインライン展開されます（ただし、callはx86でも無条件ですが）。私も（ただし、それはx86用のgccの__builtin_abs実装に基づいている、それが少ないポータブル作る整数についていくつかの仮定を行う）のx86上の枝を避け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; 
} 

Answer 3

あなたはmaxを書くことができ、 minおよびswapブランチフリー機能

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

入力：

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

そして、ここでは、ヘルパー関数は次のとおりです。あなたがこれらの機能を持っていたら、あなたはsort関数を記述するためにそれらを使用することができます

21 242 434 

出力（降順）：

434, 242, 21 

デモ：http://ideone.com/3ZOzc

私はhereからデビッドの答え@からmaxの実装を取り、少しひねりを加えたminを実装しています。