32ビット符号なし整数の逆ビット

Question

問題は32ビット符号なし整数のビットを反転することです（Javaは符号なし整数を使用しないため）。

私のコードには2つのバージョンがあります。私は2つの懸念を持っている：

（1）私の第一及び第二ソリューションは、（正しいかどうか）と同じ値を返さない理由

（2）私の第一及び第二ソリューションは正しいが届かないで間違っていたところしかし、正しい答えを返し

//reverse(3) return 4294967296 
    public static long reverse(long a) { 
     long numBits = 32L; 
     long finalResult = 0L; 
     for(long i = 0L; i < numBits; i++){ 
      long ithBit = a & (1L << i); 
      finalResult = finalResult + ithBit * (1L << (numBits - i - 1L)); 
     } 
     return finalResult; 
    } 

このコード（溶液）：

//reverse(3) returns 0 
    public static long reverse(long a) { 
     long numBits = 32; 
     long finalResult = 0; 
     for(int i = 0; i < numBits; i++){ 
      long ithBit = a & (1 << i); 
      finalResult = finalResult + ithBit * (1 << (numBits - i - 1)); 
     } 
     return finalResult; 
    } 

セカンドバージョンに答える

//reverse(3) returns 3221225472 
    public static long reverse(long A) { 
     long rev = 0; 

     for (int i = 0; i < 32; i++) { 
      rev <<= 1; 
      if ((A & (1 << i)) != 0) 
       rev |= 1; 
     } 

     return rev; 

    } 

ありがとうございます！ 2つの数字はビット31の同じビットパターン（第32回）というセットに掛けるため

ithBit * (1 << (numBits - i - 1)); 

：あなたがここにロジックの問題を抱えているの両方のバージョンで

Answer 1

。バージョン1では

、添加量は-2^31あるあなたがintをビットシフトしているので、ビット0が設定されている場合ので、ビットシフトされた結果は、高ビットがセットされているものとして-2^31を表しint、または他のすべてのための2^31でありますビットは、結果の長時間にわたる自動キャストのために可能です。各種類のビット（0と非0）の2つがあり、結果はゼロです。

バージョン2には同じ問題がありますが、をビットシフトしているため、intという問題はありません。各ビットが1の場合、2^31が追加されます。番号3には2ビットが設定されているため、結果は2 * 2^31（または2^32）です。4294967296です。

---

ロジックを修正するには、バージョン2を使用しますが、乗算はithBitで削除してください。

Answer 2

繰り返しながら値を見てみましょう。明確にするために、我々は中間の値を見て必要がありますので、我々は、コードを変更します：

int n = (1 << (numBits - i - 1)); 
long m = ithBit * n; 
finalResult = finalResult + m; 

あなたの開始値は3：

a = 0000 0000 0000 0000 0000 0000 0000 0011 

まずループの繰り返し（I = 0） ：

ithBit  = 00000000 00000000 00000000 00000001 
n   = 11111111 11111111 11111111 11111111 10000000 00000000 00000000 00000000 
m   = 11111111 11111111 11111111 11111111 10000000 00000000 00000000 00000000 
finalResult = 11111111 11111111 11111111 11111111 10000000 00000000 00000000 00000000 

第2のループ反復（I = 1）：

ithBit  = 00000000 00000000 00000000 00000010 
n   = 01000000 00000000 00000000 00000000 
m   = 10000000 00000000 00000000 00000000 
finalResult = 00000000 00000000 00000000 00000000 

ご覧のとおり、最初の反復はn = 1 << 31（-2147483648）と設定されています。 2番目のバージョンではn = 1L << 31（2147483648）です。そのため、2つのバージョンで異なる結果が得られます。

ご覧のとおり、間違いなくはありませんは、m = ithBit * nの部分をしたいと思います。

あなたの番号をあなた自身で印刷して見てください。あなたはそれを理解します。

ここに私のバージョンです。理解できない場合は、中間値を印刷して何が起こっているかを確認してください。

public static long reverse4(long a) { 
    long rev = 0; 
    for (int i = 0; i < 32; i++, a >>= 1) 
     rev = (rev << 1) | (a & 1); 
    return rev; 
} 

Answer 3

"i番目のビット"は0または1ではなく、むしろマスクされていないという問題点があります。いずれの場合も、31番目のビットは0x8000_0000です。最初のケースでは、これはintであるため、負の値になり、longに変換すると負の値になります。後者の場合は既に長いので、肯定的なままです。それはあなたが意図したものありませんので、それを修正するために実行します。

ithBit = (a >>> i) & 1; 

ところで、longは愚かである使用。署名されていない署名と署名された署名は、Javaに2種類のシフトがあることを理解している限り、違いはありません。

ところで、3つの例すべてがひどいです。あなたがビット操作をしているなら、あなたはスピードを望んでいますか？ （なぜ他のビットを気に？）

これは右（http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith32Bitsから盗まれていない鉱山、）それを行う方法です：私たちは長い間使用して符号なし整数を持っていないJava以来​​

a = ((a >>> 1) & 0x55555555) | ((a & 0x55555555) << 1); 
a = ((a >>> 2) & 0x33333333) | ((a & 0x33333333) << 2); 
a = ((a >>> 4) & 0x0F0F0F0F) | ((a & 0x0F0F0F0F) << 4); 
a = ((a >>> 8) & 0x00FF00FF) | ((a & 0x00FF00FF) << 8); 
a = (a >>> 16   ) | (a    << 16); 

Answer 4

を。一般に、不要な情報

Javaが使用two's complement representation符号なしと符号付きの数、のための同一のビットパターンで分割し、比較結果を除くすべての算術演算からです。後者の2つの操作についてはInteger.divideUnsigned(int, int)とInteger.compareUnsigned(int, int)が利用可能です。

問題がInteger.reverse(int)

Relevant docsがあります32ビット符号なし整数のビット

を逆にすることで、それらを読んでいくつかの時間を費やすことを強くお勧めします。