wake-up-neo.com

Bitweiser Operator zum einfachen Umdrehen aller Bits einer ganzen Zahl

Ich muss alle Bits in einer binären Darstellung einer Ganzzahl umdrehen. Gegeben:

10101

Die Ausgabe sollte sein 

01010

Was ist der bitweise Operator, um dies zu erreichen, wenn er mit einer Ganzzahl verwendet wird? Wenn ich beispielsweise eine Methode wie int flipBits(int n); schreibe, was würde dann im Körper funktionieren? Ich muss nur das drehen, was bereits in der Zahl vorhanden ist, nicht alle 32 Bits in der Ganzzahl.

42
Naftuli Kay

Der unäre Operator ~ ist eine bitweise Negation. Wenn Sie weniger Bits benötigen, als in eine int passen, müssen Sie sie nach der Tatsache mit & maskieren.

Verwenden Sie einfach den bitweisen Nicht-Operator ~.

int flipBits(int n) {
    return ~n;
}

Um die niedrigstwertigen Bits zu verwenden, konvertieren Sie sie in die rechte Maske.
(Ich gehe davon aus, dass Sie natürlich mindestens 1 Bit benötigen, weshalb die Maske bei 1 beginnt.)

int flipBits(int n, int k) {
    int mask = 1;
    for (int i = 1; i < k; ++i)
        mask |= mask << 1;

    return ~n & mask;
}

Wie von Lưu Vĩnh Phúc vorgeschlagen, kann die Maske als (1 << k) - 1 erstellt werden, anstatt eine Schleife zu verwenden.

int flipBits2(int n, int k) {
    int mask = (1 << k) - 1;
    return ~n & mask;
}
23
George

Es gibt verschiedene Möglichkeiten, alle Bits mithilfe von Operationen umzukehren

x = ~x; // has been mentioned and the most obvious solution.
x = -x - 1; or x = -1 * (x + 1);
x ^= -1; or x = x ^ ~0;
12
Peter Lawrey

Nun, da es bisher nur eine Lösung gibt, die das "richtige" Ergebnis liefert, und das ist wirklich keine schöne Lösung (mit einer Zeichenfolge führende Nullen zählen? Das wird mich in meinen Träumen verfolgen;))

Also, hier geht es mit einer sauberen Lösung von Nice, die funktionieren sollte. Sie wurde zwar nicht gründlich getestet, aber Sie erhalten den Gist. Wirklich ärgerlich ist Java, das keinen vorzeichenlosen Typ hat, für diese Art von Problemen, aber es sollte trotzdem recht effizient sein (und wenn ich so sagen darf, VIEL eleganter als das Erstellen einer Zeichenfolge aus der Anzahl).

private static int invert(int x) {
    if (x == 0) return 0; // Edge case; otherwise returns -1 here
    int nlz = nlz(x);
    return ~x & (0xFFFFFFFF >>> nlz);
}

private static int nlz(int x) {
    // Replace with whatever number leading zero algorithm you want - I can think
    // of a whole list and this one here isn't that great (large immediates)
    if (x < 0) return 0;
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF0000) == 0) {
        n += 16;
        x <<= 16;
    }
    if ((x & 0xFF000000) == 0) {
        n += 8;
        x <<= 8;
    }
    if ((x & 0xF0000000) == 0) {
        n += 4;
        x <<= 4;
    }
    if ((x & 0xC0000000) == 0) {
        n += 2;
        x <<= 2;
    }
    if ((x & 0x80000000) == 0) {
        n++;
    }       
    return n;
}
4
Voo

schnellere und einfachere Lösung:

/* inverts all bits of n, with a binary length of the return equal to the length of n
k is the number of bits in n, eg k=(int)Math.floor(Math.log(n)/Math.log(2))+1
if n is a BigInteger : k= n.bitLength();
*/
int flipBits2(int n, int k) {
    int mask = (1 << k) - 1;
    return n ^ mask;
}
4
serge boisse

Ich muss einige Beispiele sehen, um sicher zu sein, aber Sie erhalten möglicherweise unerwartete Werte aufgrund der Zweierkomplement-Arithmetik. Wenn die Zahl führende Nullen hat (wie im Fall von 26), würde der Operator ~ diese zu führenden Nullen umkehren, was zu einer negativen Zahl führt.

Eine mögliche Problemumgehung wäre die Verwendung der Integer-Klasse:

int flipBits(int n){
    String bitString = Integer.toBinaryString(n);
    int i = 0;

    while (bitString.charAt(i) != '1'){
        i++;
    }

    bitString = bitString.substring(i, bitString.length());

    for(i = 0; i < bitString.length(); i++){
        if (bitString.charAt(i) == '0')
            bitString.charAt(i) = '1';
        else
            bitString.charAt(i) = '0';
    }

    int result = 0, factor = 1;

    for (int j = bitString.length()-1; j > -1; j--){
        result += factor * bitString.charAt(j);
        factor *= 2;
    }

    return result;
}

Ich habe momentan noch keine Java-Umgebung zum Testen, aber das ist die allgemeine Idee. Konvertieren Sie die Zahl einfach in einen String, schneiden Sie die führenden Nullen ab, drehen Sie die Bits um und konvertieren Sie sie zurück in eine Zahl. Die Integer-Klasse kann sogar eine Möglichkeit haben, einen String in eine Binärzahl zu parsen. Ich weiß nicht, ob das Problem so gelöst werden muss, und es ist wahrscheinlich nicht der effizienteste Weg, aber es würde das richtige Ergebnis liefern.

Edit: polygenlubricants Antwort auf diese Frage kann auch hilfreich sein

0
Ben Sutton

Ich habe einen anderen Weg, um diesen Fall zu lösen, 

public static int complementIt(int c){
 return c ^ (int)(Math.pow(2, Math.ceil(Math.log(c)/Math.log(2))) -1);
}

Es verwendet XOR, um das Komplement-Bit zu erhalten, um es zu ergänzen, müssen wir XOR die Daten mit 1 angeben, beispielsweise

101 XOR 111 = 010

(111 ist der 'Schlüssel', er wird durch Suchen der 'n'-Quadratwurzel der Daten erzeugt.)

wenn Sie ~ (Komplement) verwenden, hängt das Ergebnis von seinem Variablentyp ab. Wenn Sie int verwenden, wird es als 32Bit verarbeitet.

0
Rio
import Java.math.BigInteger;
import Java.util.Scanner;

public class CodeRace1 {

    public static void main(String[] s) {
        long input;
        BigInteger num,bits = new BigInteger("4294967295");
        Scanner sc = new Scanner(System.in);
        input = sc.nextInt();
        sc.nextLine();
        while (input-- > 0) {
            num = new BigInteger(sc.nextLine().trim());
            System.out.println(num.xor(bits));
        }
    }
}
0
user5914697

Da wir nur die für die ganze Zahl erforderlichen Mindestbits umkehren müssen (beispielsweise 50 ist 110010 und wenn sie invertiert zu 001101 werden, was 13 ist), können wir einzelne Bits einzeln vom LSB in das MSB invertieren und das Bit weiter verschieben Bits nach rechts und wenden dementsprechend die Potenz von 2 an. Der folgende Code erfüllt die erforderliche Aufgabe:

int invertBits (int n) {
        int pow2=1, int bit=0;
            int newnum=0;
            while(n>0) {
              bit = (n & 1);
              if(bit==0)
                  newnum+= pow2;
              n=n>>1;
              pow2*=2;
          }
          return newnum;
        }
0
tycoon_9990

Wenn Sie nur die Bits drehen möchten, die in der Ganzzahl "verwendet" werden, versuchen Sie Folgendes:

public int flipBits(int n) {
    int mask = (Integer.highestOneBit(n) << 1) - 1;
    return n ^ mask;
}
0
xwb1989

Sie können dies versuchen:

/**
 * Flipping bits of a decimal Integer.
 */
public class FlipBits {

    public static final char ONE_CHAR = '1';
    public static final char ZERO_CHAR = '0';

    static int flipBits(int n) {
        String nBinary = Integer.toBinaryString(n);
        System.out.println("Original number is decimal " + n + ", and binary  " + nBinary);
        char[] result = new char[nBinary.length()];
        char[] nBinaryChars = nBinary.toCharArray();
        for (int i = 0; i < nBinaryChars.length; i++) {
            result[i] = nBinaryChars[i] == ONE_CHAR ? ZERO_CHAR : ONE_CHAR;
        }
        int resultDecimal = Integer.parseInt(String.valueOf(result), 2);
        System.out.println("Flipped number in decimal is " + resultDecimal
                + ", and in binary is " + String.valueOf(result));
        return resultDecimal;
    }

    public static void main(String[] args) {
        int input = 21;
        int flippedInteger = flipBits(input);
        System.out.println(input + " becomes " + flippedInteger + " after flipping the bits.");
    }

}

Beispielausgabe:

Die ursprüngliche Nummer ist die Dezimalzahl 21 und die Binärzahl 10101
Die umgedrehte Zahl in Dezimalzahlen ist 10 und in binär 01010
21 wird nach dem Umdrehen der Bits zu 10. 

0
Vahid
public static int findComplement(int num) {
    return (~num & (Integer.highestOneBit(num) - 1));
}
0
prashant

Die Implementierung von openJDK, Integer.reverse ():

public static int More ...reverse(int i) {
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

Basierend auf meinen Experimenten auf meinem Laptop war die Implementierung unten schneller:

public static int reverse2(int i) {
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i & 0x00ff00ff) << 8 | (i >>> 8) & 0x00ff00ff;
    i = (i & 0x0000ffff) << 16 | (i >>> 16) & 0x0000ffff;

    return i;
}

Nicht sicher, was der Grund dafür ist - es kann davon abhängen, wie der Java-Code in Maschinencode interpretiert wird ...

0
user3438301