Devuelve y entero con los sentidos de los mismos bits que X & Tener | X - y | valor mínimo -- java campo con algorithm campo con bitwise camp codereview Relacionados El problema

Return Y integer with same bit sets as X & having | X - Y | minimum value


7
vote

problema

Español

pasé con una pregunta:

Dado un entero 'X' (solo positivo), escriba un algoritmo que vuelva INTEGER 'Y' tal que tenga el mismo número de bits establecidos como 'X' y es no es igual a 'x' y la distancia | x-y | se minimiza.

Ejemplo:

  x: 01 y: 10   

Ahora escribí un poco de manipulación de la siguiente manera y funciona correctamente. Pero quería saber si hay un algoritmo más compacto (no se nos permite usar ninguna función incorporada).

algoritmo

  1. Si el Zeroth Bit '0':

    1. encontrar la primera ocurrencia de '1'
    2. encuentra la última ocurrencia de '0' antes de primero '1'
    3. revertirlos (utilicé o y y función para hacerlo)
  2. Si el Zeroth bit '1':

    1. encontrar la primera ocurrencia de '0'
    2. encuentra la última aparición de '1' antes de primero '0'
    3. revertirlos (utilicé o y y función para hacerlo)

Entrada:

  x = 324095 <1001111000111111111>   

Salida:

  _fetchTokens0  

Entrada:

  _fetchTokens1  

Salida:

  _fetchTokens2  

  _fetchTokens3  
Original en ingles

I happened to come across one question:

Given an integer 'x' (Only positive), write an algorithm that returns integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance |x-y| is minimized.

Example:

x: 01 y: 10 

Now I wrote some bit manipulation as follows and it's working correctly. But I wanted to know if there is a more compact algorithm (we are not allowed to use any built-in functions).

Algorithm

  1. If the Zeroth bit '0':

    1. find first occurrence of '1'
    2. find last occurrence of '0' before first '1'
    3. reverse them (I used OR and AND function to do that)
  2. If the Zeroth bit '1':

    1. find first occurrence of '0'
    2. find last occurrence of '1' before first '0'
    3. reverse them (I used OR and AND function to do that)

Input:

x = 324095 <1001111000111111111> 

Output:

324351 <1001111001011111111> 

Input:

x = 12 <1100> 

Output:

10 <1010> 

private static int MinDiff(int x)  {     int y=0,a=0,b=0,countOne=0, countZero=0;     if(x == 0)         return -1;      if( (x&1)!=1)     {         y=x;         while( (y & 1) !=1  )         {             countOne++;             y=y>>1;         }         y=x;         while( (y&3) != 2 )         {             countZero++;             y=y>>1;         }         a=1;         while(countZero != 0)         {             a = a<<1;             countZero--;         }         b=1;         while(countOne != 0)         {             b = b<<1;             countOne--;         }     }     else     {         y=x;         while( (y&1) != 0  )         {             countOne++;             countZero++;             y=y>>1;         }         countOne--;         y=x;          a=1;         while(countZero != 0)         {             a = a<<1;             countZero--;         }         b=1;         while(countOne != 0)         {             b = b<<1;             countOne--;         }     }      b = ~b;     y = (x | a) & b;     return y; } 
        
   
   

Lista de respuestas

3
 
vote

Su algoritmo es lógico, pero un poco de truco también puede hacerlo mucho más simple. Debido a que aplicar el truco hace que el código sea mucho más corto, parece mejor señalar algunos problemas más pequeños en su código, y luego mostrar el algoritmo mejorado más tarde ...

Entonces, primero arriba .... El nombre del método: MinDiff .... REALMENTE? La convención de Java es tener nombres de métodos de camellos, no Pascalcase. La primera letra debe ser una minúscula.

Los nombres de sus variables también son horribles ... y1 , x2 , 99887776655443333 y 9988776655544334 . Con x y y Variables Siempre estoy buscando coordenadas cartesianas o algo así. Elige nombres más significativos.

Su manejo de 0 y -1 también se rompe. Dado que no hay bits establecidos en 0, y no hay bits NOTET en -1, son imposibles de proporcionar una solución, por lo que lo mejor sería manejarlos como excepciones. El regreso -1 para una entrada de 0 está roto, y se desbordará en la entrada de -1 también es inconsistente.

Entonces, habiendo dicho que, el mejor algoritmo a usar es identificar el cambio más derecho en los valores de bits ... donde bit n y bit n-1 son diferentes. Luego, simplemente intercambiarlos. Un intercambio es fácil de hacer con y XOR:

  public static final int leastBitFlip(final int input) {     if (input == 0 || input == -1) {         throw new IllegalArgumentException("0 or -1 are not possible to compute as inputs");     }     int mask = 0b11;     while (sameBits(input, mask)) {         mask <<= 1;     }     // swap the bits.     return input ^ mask; }  private static boolean sameBits(final int input, final int mask) {     final int bits = input & mask;     final int swap = mask & ((bits << 1) | (bits >> 1));     return bits == swap; }   

Ahora, en cuanto a determinar si dos bits son iguales, o no, creo que la función 9988776655544338 puede ser mejorada, pero realmente no he ejecutado la tabla de verdad en ella. Sin embargo, el código es lo suficientemente simple como para entender, y la legibilidad es importante en estas cosas.

Uso de la pista de Erikr: este algoritmo sería más rápido, aunque también:

  public static final int leastBitFlip(int input) {     if (input == 0 || input == -1) {         throw new IllegalArgumentException("0 or -1 are not possible to compute as inputs");     }     // right-most one-bit.     int onebit = ((input ^ (input - 1)) + 1) >> 1;     // right most zero-bit.     int zerobit = ((input ^ (input + 1)) + 1) >> 1;     // where the change happens     int change = onebit > zerobit ? onebit : zerobit;     // create a mask of the two bits either side of the change.     int mask = change | (change >> 1);     // swap them     return input ^ mask; }   
 

Your algorithm is logical, but a little trick can make it much simpler too. Because applying the trick makes the code so much shorter, it seems better to just point out some smaller issues in your code, and then show the improved algorithm later....

So, first up.... the method name: MinDiff .... really? Java convention is to have camelCase method names, not PascalCase. The first letter should be a lower-case.

Your variable names also are horrible.... y, x, a, and b. With x and y variables I am always looking for cartesian coordinates or something. Choose more meaningful names.

Your handling of 0 and -1 is also broken. Since there are no bits set in 0, and no unset bits in -1, they are impossible to provide a solution for, so the best thing would be to handle them as exceptions. Returning -1 for an input of 0 is broken, and overflowing on the input of -1 is inconsistent too.

So, having said that, the best algorithm to use is to identify the right-most change in bit values... where bitn and bitn-1 are different. Then, just swap them. A swap is easy to do with and XOR:

public static final int leastBitFlip(final int input) {     if (input == 0 || input == -1) {         throw new IllegalArgumentException("0 or -1 are not possible to compute as inputs");     }     int mask = 0b11;     while (sameBits(input, mask)) {         mask <<= 1;     }     // swap the bits.     return input ^ mask; }  private static boolean sameBits(final int input, final int mask) {     final int bits = input & mask;     final int swap = mask & ((bits << 1) | (bits >> 1));     return bits == swap; } 

Now, as for determining whether two bits are the same, or not, I think that sameBits() function can be improved, but I have not really run the truth table on it. The code is simple enough to understand though, and readability is important in these things.

Using the hint from ErikR - this algorithm would be faster though too:

public static final int leastBitFlip(int input) {     if (input == 0 || input == -1) {         throw new IllegalArgumentException("0 or -1 are not possible to compute as inputs");     }     // right-most one-bit.     int onebit = ((input ^ (input - 1)) + 1) >> 1;     // right most zero-bit.     int zerobit = ((input ^ (input + 1)) + 1) >> 1;     // where the change happens     int change = onebit > zerobit ? onebit : zerobit;     // create a mask of the two bits either side of the change.     int mask = change | (change >> 1);     // swap them     return input ^ mask; } 
 
 
       
       

Relacionados problema

11  CODILIDAD SOLUCIÓN DE GAPO BINARIO CON REGEX  ( Codility binary gap solution using regex ) 
A continuación se muestra el código que implementé para resolver el problema de brecha binario : Encuentra la secuencia más larga de ceros, limitada por l...

4  Decodificación de datos binarios (AIS) del zócalo  ( Decoding of binary data ais from socket ) 
Actualmente estoy trabajando en una Mensaje AIS Decoder escrito en python puro. Es solo un pequeño proyecto para enseñarme algunas cosas sobre los datos bin...

7  Cálculo del permiso de archivo octal basado en Linux  ( Calculating linux based octal file permission ) 
Estoy solicitando una posición de devloper de nivel medio. Para avanzar a la 2ª entrevista, debe pasar una prueba técnica. Una de las preguntas fue escribir...

5  Cálculo de suma de comprobación de 16 bits [cerrado]  ( 16 bit checksum calculation ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

10  Suma más rápida de valores absolutos de 32 diferencias  ( Fastest sum of absolute values of 32 differences ) 
A long1 debe tratarse como una lista de 32 números sin firmar, cada uno de ellos a solo dos bits. Por lo que 0x1234F... representa {0, 1, 0, 2, 0, 3, 1...

0  Escritor BMP en C  ( Bmp writer in c ) 
Recientemente escribí un escritor BMP en C: bmpwriter.h #ifndef BMPWRITER_ #define BMPWRITER_ #include <stdint.h> int write24BitBMP(const char *outpu...

3  Pruebas de divisibilidad de números - Seguimiento  ( Testing for divisibility of numbers follow up ) 
( aquí es la pregunta de seguimiento) Tuve otra oportunidad de intentar acelerar mi programa descrito en mi Pregunta previa . La respuesta de JS1 fue...

2  Función de desvanecimiento de color [cerrado]  ( Color fading function ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

2  Simplifique el código de verificación de banderas de bits  ( Simplify bit flags checking code ) 
Por favor, ayuda a hacer que este código sea más limpio. Es parte del procedimiento de la ventana que notifica a mi renderizado antes de Área de cliente de ...

4  Calculadora binaria de Python  ( Python binary calculator ) 
Mi tarea fue construir una calculadora en la adición binaria de soporte de Python, etc. Para comenzar Definir un par de excepciones personalizadas: paper...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos