Cómo encontrar si dos números son números consecutivos en secuencia de código gris

Estoy tratando de encontrar una solución al problema que, dado dos números, busque si son números consecutivos en la secuencia del código gris, es decir, si son vecinos del código gris, suponiendo que no se menciona la secuencia del código gris.

Busqué en varios foros pero no pude obtener la respuesta correcta. Sería genial si puede proporcionar una solución para esto.

Mi bash de resolver el problema: convierta dos enteros a binarios y agregue los dígitos en ambos números por separado y encuentre la diferencia entre la sum de los dígitos en dos números. Si la diferencia es una, entonces son vecinos de código gris.

Pero siento que esto no funcionará para todos los casos. Cualquier ayuda es muy apreciada. ¡¡¡Muchas gracias por adelantado!!!

También tuve que resolver esta pregunta en una entrevista. Una de las condiciones para que los dos valores sean una secuencia de código gris es que sus valores solo difieren en 1 bit. Aquí hay una solución a este problema:

def isGrayCode(num1, num2): differences = 0 while (num1 > 0 or num2 > 0): if ((num1 & 1) != (num2 & 1)): differences++ num1 >>= 1 num2 >>= 1 return differences == 1 

En realidad, varias de las otras respuestas parecen estar equivocadas: es cierto que dos vecinos del código Grey reflejado binario difieren solo en un bit (supongo que por «la» secuencia del Código Grey, se refiere a la secuencia del código Grey reflejado binario original, como lo describe Frank Gray ). Sin embargo, eso no significa que dos códigos de Gray que difieran en un bit sean vecinos ( a => b no significa que b => a ). Por ejemplo, los códigos Gray 1000 y 1010 difieren solo en un bit pero no son vecinos (1000 y 1010 son respectivamente 15 y 12 en decimal).

Si desea saber si dos códigos de Gray a y b son vecinos, debe verificar si el previous(a) = b OR next(a) = b . Para un código Gray dado, se obtiene un vecino al voltear el bit de la derecha y el otro bit del vecino al voltear el bit a la izquierda del bit de ajuste de la derecha. Para el código gris 1010, los vecinos son 1011 y 1110 (1000 no es uno de ellos).

Si obtiene el vecino anterior o el siguiente al voltear uno de estos bits, en realidad depende de la paridad del código Gray. Sin embargo, dado que queremos a los dos vecinos, no tenemos que verificar la paridad. El siguiente pseudocódigo debería indicarle si dos códigos de Gray son vecinos (utilizando operaciones bitwise como C):

 function are_gray_neighbours(a: gray, b: gray) -> boolean return b = a ^ 1 OR b = a ^ ((a & -a) << 1) end 

Truco de bits anterior: a & -a aísla el bit de conjunto más preciso en un número. Desplazamos ese bit una posición hacia la izquierda para obtener el bit que necesitamos para voltear.

Suposiciones: Las entradas ayb son secuencias de código gris en código gris reflejado binario. es decir, la encoding de bits de a y b es representaciones de código gris binario.

 #convert from greycode bits into regular binary bits def gTob(num): #num is binary graycode mask = num >> 1 while mask!=0: num = num^mask mask >>= 1 return num; #num is converted #check if a and b are consecutive gray code encodings def areGrayNeighbors(a,b): return abs(gTob(a) - gTob(b)) == 1 

Pocos casos de prueba:

  • areGrayNeighbors (9,11) -> Verdadero (ya que (1001, 1011) se diferencian en un solo bit y son números consecutivos en representación decimal)
  • areGrayNeighbors (9,10) -> False
  • areGrayNeighbors (14,10) -> Verdadero

Referencias: el método gTob () utilizado anteriormente es de rodrigo en este post Los vecinos en código Gray

 public int checkConsecutive2(int b1, int b2){ int x = (b1 ^ b2); if((x & (x - 1)) !=0){ return 0; }else{ return 1; } } 

Si dos números están en secuencia de código gris, difieren en un dígito binario. es decir, el OR exclusivo en los dos números devuelve una potencia de 2. Entonces, encuentre XOR y verifique si el resultado es una potencia de dos.

Esta solución funciona bien para todos los casos de prueba escritos por CodeKaichu arriba. Me encantaría saber si falla en algún caso.

 public boolean grayCheck(int x, int y) { int z = x^y; return (z&z-1)==0; } 

Una respuesta obvia, pero funciona. Convierta cada código gris a su respectivo formato binario, reste los dos. Si su respuesta es un equivalente binario de +1 o -1, entonces los dos códigos grises son adyacentes.

Esto parece ser una matanza excesiva, pero cuando te encuentras en una entrevista y no conoces el método correcto, esto funciona. También para optimizar, uno puede verificar el filtro de diferencia de bit único, para que no perdamos el tiempo convirtiendo y restando números que sabemos que no son adyacentes.

Si solo desea comprobar si los números de entrada difieren en un solo bit:

 public boolean checkIfDifferByOneBit(int a, int b){ int diff = 0; while(a > 0 && b > 0){ if(a & 1 != b & 1) diff++; a = a >> 1; b = b >> 1; } if (a > 0 || b > 0) // a correction in the solution provided by David Jones return diff == 0 // In the case when a or b become zero before the other return diff == 1; } 

Puede verificar si dos números difieren en un bit o no de la siguiente manera. En este método, se cuida la diferencia en la longitud de los números binarios. Por ejemplo, la salida para 11 (1011) y 3 (11) se devolverá como verdadera. Además, esto no resuelve el segundo criterio para la adyacencia del código gris. Pero si solo quiere comprobar si los números difieren en un bit, el código a continuación le ayudará.

 class Graycode{ public static boolean graycheck(int one, int two){ int differences = 0; while (one > 0 || two > 0){ // Checking if the rightmost bit is same if ((one & 1) != (two & 1)){ differences++; } one >>= 1; two >>= 1; } return differences == 1; } public static void main(String[] args){ int one = Integer.parseInt(args[0]); int two = Integer.parseInt(args[1]); System.out.println(graycheck(one,two)); } }