2進演算子のみを使用して符号付き整数を分割するにはどうすればよいですか？

Question

私は使用することができます！ 〜&^| + < < >>

私は2^nで数xを分割しようとしていますC.

でこれを書いています。 だから私はx >> nをシフトすると思っていましたが、奇数の負の整数では機能しません。もともとは次のようになりました。

int dl18(int x, int n) { 
    return (x >> n); 
} 

x34 = -9かつn = 1の場合、出力は-4になりますが、-5になります。 x = -9かつn = 0の場合、出力は正しい（-9）。

ありがとうございます。

だから私は、これを行うことは、それがない限り、すべてのもののために働く可能n = 0で、xが負の数である考え出し：符号付き整数のtwo's complement表現と>>オペレータのarithmetic shift行動を想定し

return (~(x >> 31) & (x >> n)) | ((x >> 31) & ((x >> n) + 1)); 

Answer 1

、答えは可能性があり：負の無限大に向かって負の数値の>>ラウンドため

int dl18(int x, int n) { 
    if (x < 0) { 
     x += (1 << n) - 1; 
    } 
    return x >> n; 
} 

添加が必要です。 2^n - 1を追加すると、結果は常に/演算子の場合のようにゼロに向かって切り捨てられます。ための要件に

、intは4バイトを持っている（と余分な杓子定規CHAR_BIT = 8する）と仮定し、式として（難読化）に書き換えることがあります。

(x + ((x >> 31) & ((1 << n) + ~0))) >> n 

x >> 31のアイデアは、MSBビットを複製することですしたがって、マスクはすべてのもの（すなわち0xFFFFFFFF）、またはすべて0になり、追加から((1 << n) - 1)を保存または削除するために使用されます。加算にはビット単位のANDよりもhigher precedenceがあるため、括弧は&である必要があります。

このアルゴリズムは、GCCコンパイラでも使用されています。例えば：負の数によってシフトするundefined behaviorを呼び出し、unsigned intように、第2のパラメータを宣言するために安全であり得ることを

dl18_4: 
     lea  eax, [rdi+3] ; eax = rdi + 3 
     test edi, edi  ; set sign flag if edi < 0 
     cmovns eax, edi  ; eax = edi if SF = 0 
     sar  eax, 2   ; eax = eax >> 2 
     ret 

注

int dl18_4(int x) { return x/4; } 

は-O1へと変換します。

Answer 2

ここでは、負の値をビットシフトすることを避けるソリューションです。これは2の補数表示を想定していますが、単項負演算子は使用しません。

ビットマスクを使用して、xが負の場合はnegをゼロ以外の値に設定し、xが負でない場合はゼロに設定します。ここでは@Grzegorz Szpetkowskiで示唆されているトリックを使用して、1で減算するのを避けます。代わりに~0を追加してください。 xが負の場合、xの値はxの値に変更されます。@chuxが提案するトリックを使用して、ここで単項負数を使用しないようにするには、2の補数の負の値の場合、対応する正の値が負の表現のビット否定に1を加えたものに等しいという事実を利用します。

この大きさのxは、実装依存の動作に遭遇することなくビットシフトさせることができます。除算を実行した後、以前と同じ変換を実行することによって、元の値が負の場合は結果が負の値に戻されます。

#include <stdio.h> 
#include <limits.h> 

int divide_2n(int x, unsigned n); 

int main(void) 
{ 
    printf("-7/4 = %d\n", divide_2n(-7, 2)); 
    printf("27/8 = %d\n", divide_2n(27, 3)); 
    printf("-27/8 = %d\n", divide_2n(-27, 3)); 
    printf("-9/2 = %d\n", divide_2n(-9, 1)); 
    printf("-9/1 = %d\n", divide_2n(-9, 0)); 

    return 0; 
} 

int divide_2n(int x, unsigned n) 
{ 
    unsigned n_bits = CHAR_BIT * sizeof(int); 
    unsigned neg = x & (1U << (n_bits + ~0)); 

    if (neg) { 
     x = ~(unsigned)x + 1; 
    } 

    x = (unsigned)x >> n; 

    if (neg) { 
     x = ~x + 1; 
    } 

    return x; 
} 

-7/4 = -1 
27/8 = 3 
-27/8 = -3 
-9/2 = -4 
-9/1 = -9