Reverse-Bits einer 32-Bit-Ganzzahl ohne Vorzeichen

Question

Das Problem besteht darin, die Bits einer 32-Bit-Ganzzahl ohne Vorzeichen umzukehren (da Java keine vorzeichenlosen Ganzzahlen hat, die wir lange verwenden).

Hier sind zwei Versionen meines Codes. Ich habe zwei Bedenken:

(1), warum meine 1. und 2. Lösung nicht zurück den gleichen Wert (richtig oder nicht)

(2), wo meine erste und zweite Lösung schief gelaufen ist nicht die richtige bekommen Antwort

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

Zweite Version:

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

Dieser Code (die Lösung) gibt die richtige Antwort, aber:

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

    } 

Danke!

Answer 1

In beiden Versionen haben Sie ein logisches Problem hier:

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

, weil die beiden Zahlen auf den gleichen Bitmuster Bit 31 (die 32.) gesetzt wird multipliziert.

In der Version 1, die zugegebene Menge -2^31 wenn Bit 0 gesetzt, weil Sie ein int Bit-Verschiebung, so dass das Bit-verschobene Ergebnis int ist die oder 2^31 für jeden anderen gesetzt werden -2^31 als das hohe Bit repräsentiert Bit, was aufgrund der Auto-Cast zu lange des Ergebnisses möglich ist. Sie haben zwei von jeder Art von Bit (0 und nicht 0), so dass das Ergebnis Null ist.

Version 2 hat das gleiche Problem, aber ohne das negative int Problem, weil Sie eine long bit Verschiebung sind. Jedes Bit, das 1 ist, fügt 2^31 hinzu. Die Nummer 3 hat 2 Bits, also ist Ihr Ergebnis 2 * 2^31 (oder 2^32), also 4294967296.

---

Ihre Logik zu beheben, verwenden Version 2, aber die Multiplikation mit ithBit entfernen.

Answer 2

Sehen wir uns Ihre Werte bei der Iteration an. Zur Verdeutlichung werden wir einen Blick auf den Zwischenwert haben, so dass wir Code ändern:

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

Ihr Startwert 3:

a = 0000 0000 0000 0000 0000 0000 0000 0011 

Erste Schleifeniterationslatenzzeit (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 

Zweite Schleifeniteration (i = 1):

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

Wie Sie sehen können, setzt die erste Iteration n = 1 << 31, die -2147483648 ist. In Ihrer zweiten Version tun Sie n = 1L << 31, die 2147483648 ist, und deshalb geben Ihre zwei Versionen unterschiedliche Ergebnisse.

Wie Sie auch sehen können, tun Sie auf jeden Fall nicht wollen den m = ithBit * n Teil tun.

Schauen Sie sich Ihre Nummer an, indem Sie sie selbst ausdrucken, und Sie werden es herausfinden.

BTW, hier ist meine Version. Wenn Sie das Problem nicht verstehen, versuchen Sie, die Zwischenwerte zu drucken, um zu sehen, was passiert.

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

Problem mit Ihren beiden Beispielen ist, dass das „i-te Bit“ ist keine 0 oder 1, sondern maskiert. In beiden Fällen ist das 31. Bit 0x8000_0000. Im ersten Fall ist dies ein int, also ist es negativ, und wenn es in ein long umgewandelt wird, bleibt es negativ. Im zweiten Fall ist es schon lang, also bleibt es positiv. Um es zu beheben, so dass es das tut, was man beabsichtigt, zu tun:

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

By the way, mit long ist dumm; Unsigned vs Signed macht keinen Unterschied, solange Sie verstehen, dass es zwei Arten von Verschiebungen in Java gibt.

Übrigens sind alle drei Beispiele schrecklich. Wenn du etwas manipulierst, willst du Geschwindigkeit, richtig? (Warum sonst mit Bits die Mühe machen?)

Dies ist, wie man es richtig macht (nicht von mir, gestohlen von http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith32Bits):

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

da Java nicht über ganze Zahlen ohne Vorzeichen wir lange verwenden.

Das für nicht signierte und signierten Zahlen in two's complement representation da alle arithmetischen Operationen mit Ausnahme der Division und Vergleichsergebnis in identischen Bitmuster allgemein unecessary ist, die Java verwendet. Und für die letzten beiden Ops Integer.divideUnsigned(int, int) und Integer.compareUnsigned(int, int) sind verfügbar.

Das Problem ist, die Bits eines 32-Bit-Integer ohne Vorzeichen

Es gibt Integer.reverse(int)

Relevant docs, verbringen einige Zeit zu umkehren sie zu lesen ist sehr zu empfehlen.