condicionales - operadores de bits java

¿Operador bit a bit para simplemente voltear todos los bits en un entero?

Question

Tengo que voltear todos los bits en una representación binaria de un entero. Dado:

10101

La salida debe ser

01010

¿Cuál es el operador bitwise para lograr esto cuando se usa con un número entero? Por ejemplo, si estuviera escribiendo un método como int flipBits(int n); , que iria en el cuerpo? Necesito voltear solo lo que ya está presente en el número, no todos los 32 bits en el entero.

Answer 1

Bueno, hasta ahora solo hay una solución que da el resultado "correcto" y esa ... realmente no es una buena solución (¿usar una cadena para contar los ceros a la izquierda? Eso me perseguirá en mis sueños;))

Así que aquí vamos con una buena solución limpia que debería funcionar, aunque no la hemos probado a fondo, pero entiendes lo esencial. Realmente, java no tener un tipo sin signo es extremadamente molesto para este tipo de problemas, pero debería ser bastante eficiente (y si puedo decirlo MUCHO más elegante que crear una cadena a partir del número)

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

Answer 2

Código simple para implementar los bits de volteo:

#include<stdio.h>

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

Answer 3

Como solo estamos obligados a cambiar los bits mínimos requeridos para el entero (por ejemplo, 50 es 110010 y cuando se invierte, se convierte en 001101, que es 13), podemos invertir bits individuales de uno en uno desde el LSB al MSB, y seguir cambiando el bits a la derecha y, en consecuencia, aplican la potencia de 2. El siguiente código realiza el trabajo requerido:

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

Answer 4

El operador unario es la negación a nivel de bit. Si necesita menos bits de los que caben en un int , deberá enmascararlo con & después del hecho.

Answer 5

Hay varias formas de voltear todo el bit usando operaciones

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

Answer 6

La implementación de 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;
}

Basándome en mis experimentos en mi computadora portátil, la implementación a continuación fue más rápida:

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

No estoy seguro de cuál es la razón detrás de esto, ya que puede depender de cómo se interpreta el código Java en el código de máquina ...

Answer 7

Puedes probar esto:

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

}

Salida de muestra:

El número original es el decimal 21, y el binario 10101
El número invertido en decimal es 10 y en binario es 01010
21 se convierte en 10 después de voltear los bits.

Answer 8

Si solo desea voltear los bits que se "utilizan" en el entero, intente esto:

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

Answer 9

Simplemente use el operador bitwise no.

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

Para usar los k bits menos significativos, conviértalos a la máscara correcta.
(Supongo que quieres al menos 1 bit por supuesto, por eso la máscara comienza en 1)

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

    return ~n & mask;
}

Como lo sugiere Lưu Vĩnh Phúc , uno puede crear la máscara como (1 << k) - 1 lugar de usar un bucle.

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

Answer 10

Solución más rápida y sencilla:

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

Answer 11

Tendría que ver algunos ejemplos para estar seguro, pero es posible que esté obteniendo valores inesperados debido a la aritmética del complemento de dos. Si el número tiene ceros iniciales (como lo haría en el caso de 26), el operador ~ los volteará para convertirlos en los primeros, lo que dará como resultado un número negativo.

Una posible solución sería utilizar la clase 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;
}

No tengo un entorno Java configurado ahora para probarlo, pero esa es la idea general. Básicamente, simplemente convierta el número en una cadena, corte los ceros iniciales, invierta los bits y vuelva a convertirlo en un número. La clase Integer puede incluso tener alguna forma de analizar una cadena en un número binario. No sé si así es como debe hacerse el problema, y ​​probablemente no sea la forma más eficiente de hacerlo, pero produciría el resultado correcto.

Edición: la respuesta de los poligénicos a esta pregunta también puede ser útil

Answer 12

Tengo otra forma de resolver este caso,

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

Está utilizando XOR para obtener el bit de complemento, para complementarlo necesitamos XOR los datos con 1, por ejemplo:

101 XOR 111 = 010

(111 es la ''clave'', que se genera al buscar la ''n'' raíz cuadrada de los datos)

Si está utilizando ~ (complemento), el resultado dependerá de su tipo de variable, si está utilizando int, entonces se procesará como 32 bits.

Answer 13

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

Answer 14

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