ビット操作を使用して最小値を見つける

Question

誰でも私に次のコード行を説明することができます。これは、2つの数値の最小値を見つけるために使用されます。

int min(int x, int y) 

{ 

    return y + ((x - y) & ((x - y) >> 
      (sizeof(int) * CHAR_BIT - 1))); 

} 

ありがとうございます。

Answer 1

この部分は、そうでなければx<y場合、値-1を有し、0：

(x - y) >> (sizeof(int) * CHAR_BIT - 1) 

（64ビットのint型、などを使用する場合、または63）、これは31ビットの算術シフトすることによってこれを達成します。算術シフトは符号ビットを保持するので、負の値の場合はすべてのビットが1の結果が得られ、正の値の場合はすべてのビットが0の結果が得られます。例えば、x=2とy=4の場合：

(2 - 4) >> (sizeof(int) * CHAR_BIT - 1) 
== (-2) >> (4 * 8 -1) 
== (-2) >> 31 
== 0xFFFFFFFE >> 31 
== 0xFFFFFFFF 
== -1 

この値を使用して(x - y)をマスクします。つまり、x<yの場合は(x - y) & -1 == (x - y)、そうでない場合は(x - y) & 0 == 0になります。

最後に、その値はyに加算され、y + (x - y) == xまたはy + 0 == yのいずれかになります。

Answer 2

（明確にするために、我々はsizeof(int) == 4とCHAR_BIT == 8を想定したが、それは他のサイズのために働く）

私たちは、最も内側の式から、それを解析します。 intため

(x - y) >> (sizeof(int) * CHAR_BIT - 1) 
== (x - y) >> 31 

>>

通常符号拡張右シフト（別名arithmetic right shift）です。 31ビットシフトすると最上位ビットのみが残り、このビットは残りの31ビットに拡張されます。これは実際には⌊（x - y）/ 2 ⌋と等価です。

(x - y) >> 31は、x - yが負の場合は-1となり、それ以外の場合は0となります。これは、実際にここで、我々はx - y < 0がx < yと同等であると言う

x - y < 0 ? -1 : 0 
== x < y ? -1 : 0 

ノートを書くためのファンシーな方法ですが、これだけ作品オーバーフローが存在しないとき。例えば、x == 0とy == INT_MINの場合、x - yは、負であるINT_MINにオーバーフローしますが、x < yは確かに偽です。

プラグ完全な表現にこのバック：

y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))) 
== y + ((x - y) & (x < y ? -1 : 0)) // <- assume no overflow 

x < yは、我々は(x - y) & -1を取得します。 -1にはすべてのビットが設定されているので、x - yに相当します。 x >= yの場合、(x - y) & 0となります。

したがって、を書くのは単なるファンシーな方法です。そのため、オーバーフローのバグの

---

== y + (x < y ? x - y : 0) 
== x < y ? x : y 

、および表現はとてもトリッキーであることを、あなたは実際には、この表現を使うべきではありません。ちょうど (x < y) ? x : yを使用してください。

Answer 3

これは、2つの数字の最小値を見つけるために使用されます。

intの多くの組み合わせでは、このコードは不幸にも失敗します。 @harold良いコンパイラはx < y ? x: y;を認識し、正しい高速コードを生成します。 @David C. Rankin

どのように動作するかは、どのように失敗するかほど重要ではありません。

1. 未定義の動作は：x - yオーバーフロー、対応のコンパイラは、任意の出力を生成し得る必要があります - でもクラッシュ。コンパイラの最適化は、これを新しいプログラマの嫌悪感に利用します。

2. 符号ビットをシフトすると、実装定義の動作はsome_negative_int >> (sizeof(int) * CHAR_BIT - 1)))のようになります。 intの算術右シフトは、最大許容シフトint（これは稀である）パディングを含まなければならないを超えることが一般的であり、まだC.

3. some_int >> (sizeof(int) * CHAR_BIT - 1)))によって指定されていません。下記を参照してください - 31 121のテストケースを失敗しました -

---

OPのコードはx,yの多くの組み合わせのために失敗しました。 "It accomplishes this by an arithmetic shift"は実装定義の振る舞いです。 x-yの潜在的なオーバーフローは未定義の動作です。これらに対処することなく、すべての答えは不完全です。

コーナーケース"it works for any other sizes"が一般的ですが、まれなプラットフォームでは、埋め込みをintで利用すると、sizeof(int) * CHAR_BIT - 1に問題があります。

#include <stdio.h> 

int minz(int x, int y) { 
    return y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); 
} 

void testmin(int x, int y) { 
    static unsigned count = 0; 
    static unsigned fail = 0; 
    int min0 = x < y ? x: y; 
    int min1 = minz(x,y); 
    count++; 
    if (min0 != min1) { 
    fail++; 
    printf("%u/%u min(%d, %d)--> %d, should be %d\n", fail,count, x,y, min1, min0); 
    } 
} 
int main(void) { 
    const int i[]={INT_MIN, INT_MIN+1, INT_MIN+2, -2,-1,0, 1, 2, INT_MAX-2,INT_MAX-1, INT_MAX}; 
    int x,y; 
    for (x=0; x<sizeof i/sizeof i[0]; x++) { 
    for (y=0; y<sizeof i/sizeof i[0]; y++) { 
     testmin(i[x],i[y]); 
    } 
    } 
} 

出力（失敗）

1/7 min(-2147483648, 1)--> 1, should be -2147483648 
2/8 min(-2147483648, 2)--> 2, should be -2147483648 
3/9 min(-2147483648, 2147483645)--> 2147483645, should be -2147483648 
4/10 min(-2147483648, 2147483646)--> 2147483646, should be -2147483648 
5/11 min(-2147483648, 2147483647)--> 2147483647, should be -2147483648 
6/19 min(-2147483647, 2)--> 2, should be -2147483647 
7/20 min(-2147483647, 2147483645)--> 2147483645, should be -2147483647 
8/21 min(-2147483647, 2147483646)--> 2147483646, should be -2147483647 
9/22 min(-2147483647, 2147483647)--> 2147483647, should be -2147483647 
10/31 min(-2147483646, 2147483645)--> 2147483645, should be -2147483646 
11/32 min(-2147483646, 2147483646)--> 2147483646, should be -2147483646 
12/33 min(-2147483646, 2147483647)--> 2147483647, should be -2147483646 
13/44 min(-2, 2147483647)--> 2147483647, should be -2 
14/56 min(0, -2147483648)--> 0, should be -2147483648 
15/67 min(1, -2147483648)--> 1, should be -2147483648 
16/68 min(1, -2147483647)--> 1, should be -2147483647 
17/78 min(2, -2147483648)--> 2, should be -2147483648 
18/79 min(2, -2147483647)--> 2, should be -2147483647 
19/80 min(2, -2147483646)--> 2, should be -2147483646 
20/89 min(2147483645, -2147483648)--> 2147483645, should be -2147483648 
21/90 min(2147483645, -2147483647)--> 2147483645, should be -2147483647 
22/91 min(2147483645, -2147483646)--> 2147483645, should be -2147483646 
23/100 min(2147483646, -2147483648)--> 2147483646, should be -2147483648 
24/101 min(2147483646, -2147483647)--> 2147483646, should be -2147483647 
25/102 min(2147483646, -2147483646)--> 2147483646, should be -2147483646 
26/103 min(2147483646, -2)--> 2147483646, should be -2 
27/111 min(2147483647, -2147483648)--> 2147483647, should be -2147483648 
28/112 min(2147483647, -2147483647)--> 2147483647, should be -2147483647 
29/113 min(2147483647, -2147483646)--> 2147483647, should be -2147483646 
30/114 min(2147483647, -2)--> 2147483647, should be -2 
31/115 min(2147483647, -1)--> 2147483647, should be -1