Operatore bit a bit per semplicemente capovolgere tutti i bit in un numero intero?

Devo capovolgere tutti i bit in una rappresentazione binaria di un intero. Dato:

10101 

L’output dovrebbe essere

 01010 

Qual è l’operatore bit a bit per farlo quando utilizzato con un numero intero? Ad esempio, se scrivessi un metodo come int flipBits(int n); , cosa andrebbe nel corpo? Ho bisogno di capovolgere solo ciò che è già presente nel numero, non tutti i 32 bit nel numero intero.

L’operatore ~ unary è la negazione bit per bit. Se hai bisogno di meno bit di quello che si adatta a un int , dovrai mascherarlo con & dopo il fatto.

Basta usare l’operatore bitwise non ~ .

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

Per usare i k bit meno significativi, convertilo nella maschera giusta.
(Suppongo che tu voglia almeno 1 bit, naturalmente, ecco perché la maschera parte da 1)

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

Come suggerisce Lưu Vĩnh Phúc , si può creare la maschera come (1 << k) - 1 invece di usare un ciclo.

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

C’è un certo numero di modi per capovolgere tutto usando le operazioni

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

Bene visto che finora c’è solo una soluzione che dà il risultato “corretto” e che … non è davvero una bella soluzione (usando una stringa per contare gli zeri iniziali? Che mi perseguiterà nei miei sogni;))

Quindi, eccoci qui con una soluzione pulita che dovrebbe funzionare, ma non l’ho testata approfonditamente, ma ottieni il succo. Davvero, java non avendo un tipo unsigned è estremamente fastidioso per questo tipo di problemi, ma dovrebbe essere comunque abbastanza efficiente (e se posso dire MOLTO più elegante di creare una stringa fuori dal numero)

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

soluzione più veloce e semplice:

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

Dovrei vedere alcuni esempi per essere sicuro, ma potresti ottenere valori inaspettati a causa dell’aritmetica del complemento a due. Se il numero ha zero iniziali (come nel caso di 26), l’operatore ~ ​​invertirà questi valori per renderli leader – risultando in un numero negativo.

Una soluzione ansible sarebbe utilizzare la class Integer:

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

Non ho un ambiente java impostato in questo momento per testarlo, ma questa è l’idea generale. Fondamentalmente basta convertire il numero in una stringa, tagliare gli zeri iniziali, capovolgere i bit e convertirli in un numero. La class Integer potrebbe anche avere un modo per analizzare una stringa in un numero binario. Non so se è così che deve essere fatto il problema, e probabilmente non è il modo più efficace per farlo, ma produrrebbe il risultato corretto.

Modifica: la risposta di poligenlubrificanti a questa domanda può anche essere utile

Ho un altro modo per risolvere questo caso,

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

Sta usando XOR per ottenere il bit del complemento, per completarlo abbiamo bisogno di XOR i dati con 1, ad esempio:

101 XOR 111 = 010

(111 è la ‘chiave’, generata dalla ricerca nella radice quadrata ‘n’ dei dati)

se stai usando ~ (complemento) il risultato dipenderà dal suo tipo di variabile, se stai usando int allora sarà elaborato come 32 bit.

Poiché è necessario solo capovolgere i bit minimi richiesti per il numero intero (ad esempio 50 è 110010 e quando è invertito, diventa 001101 che è 13), possiamo invertire singoli bit uno alla volta da LSB a MSB e continuare a spostare il bit i bit a destra e di conseguenza applicano la potenza di 2. Il codice seguente fa il lavoro richiesto:

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

L’implementazione da 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; } 

Basandosi sui miei esperimenti sul mio portatile, l’implementazione di seguito è stata più veloce:

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

Non sei sicuro di quale sia il motivo alla base, poiché può dipendere dal modo in cui il codice java viene interpretato in codice macchina …

Se vuoi semplicemente capovolgere i bit che sono “usati” nel numero intero, prova questo:

 public int flipBits(int n) { int mask = (Integer.highestOneBit(n) << 1) - 1; return n ^ mask; } 
 public static int findComplement(int num) { return (~num & (Integer.highestOneBit(num) - 1)); } 

Semplice codice per implementare i bit flipping:

 #include main() { unsigned x = 5; printf("%u",~x); }