Wie zu finden, wenn zwei Zahlen fortlaufende Nummern in Gray-Code-Sequenz sind

Question

Ich versuche, eine Lösung für das Problem, das bei zwei Zahlen, finden Sie, wenn sie die fortlaufenden Nummern in der Gray-Code-Sequenz, dh wenn sie sind Gray-Code-Nachbarn vorausgesetzt, dass die Gray-Code-Sequenz nicht erwähnt wird.

Ich suchte in verschiedenen Foren, konnte aber nicht die richtige Antwort bekommen. Es wäre großartig, wenn Sie dafür eine Lösung bereitstellen könnten.

Mein Versuch, das Problem - Konvertieren Sie zwei Ganzzahlen in Binär und fügen Sie die Ziffern in beiden Zahlen getrennt hinzu und finden Sie den Unterschied zwischen der Summe der Ziffern in zwei Zahlen. Wenn der Unterschied eins ist, dann sind sie Gray-Code-Nachbarn.

Aber ich fühle, dass dies nicht für alle Fälle funktioniert. Jede Hilfe wird sehr geschätzt. Vielen Dank im Voraus!!!

Answer 1

Ich musste diese Frage in einem Interview auch lösen. Eine der Bedingungen für die zwei Werte als eine Gray-Code-Sequenz ist, dass ihre Werte sich nur um 1 Bit unterscheiden. Hier ist eine Lösung für dieses Problem:

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 

Answer 2

Eigentlich einige der anderen Antworten scheinen falsch: Es ist wahr, dass zwei binären Gray-Code reflektiert Nachbarn von nur einem Bit unterscheiden (Ich gehe davon aus, dass durch «die» Grau Codefolge, du meinst die ursprüngliche binär reflektierte Gray-Code-Sequenz wie von Frank Grey beschrieben). Das bedeutet jedoch nicht, dass zwei Gray-Codes, die sich um ein Bit unterscheiden, Nachbarn sind (a => b bedeutet nicht, dass b => a). Zum Beispiel unterscheiden sich die Gray-Codes 1000 und 1010 nur um ein Bit, sind aber keine Nachbarn (1000 und 1010 sind jeweils 15 und 12 in Dezimal).

Wenn Sie wissen möchten, ob zwei Gray-Codes a und b Nachbarn sind, müssen Sie überprüfen, ob 10. Für einen gegebenen Gray-Code erhalten Sie einen Nachbarn, indem Sie das äußerste rechte Bit und das andere benachbarte Bit spiegeln, indem Sie das Bit links vom am weitesten rechts gesetzten Bit umdrehen. Für den Gray-Code 1010 sind die Nachbarn 1011 und 1110 (1000 ist keiner von ihnen).

Ob der vorherige oder der nächste Nachbar durch das Spiegeln eines dieser Bits erreicht wird, hängt von der Parität des Gray-Codes ab. Da wir jedoch beide Nachbarn haben wollen, müssen wir nicht auf Parität prüfen. Der folgende Pseudo-Code sollte Ihnen sagen, ob zwei Gray-Codes sind Nachbarn (C-ähnliche Bit-Operationen verwendet wird):

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

Bit Trick oben: a & -a isoliert die rigthmost gesetzte Bit in einer Zahl. Wir verschieben dieses Bit um eine Position nach links, um das Bit zu erhalten, das wir umkehren müssen.

Answer 3

Wenn Sie wollen einfach nur prüfen, ob die Eingabe von Zahlen nur durch ein Bit unterscheiden:

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

Answer 4

Annahmen: Eingänge a und b sind Gray-Code-Sequenzen in binären Gray-Code reflektiert. , d. H. Die Bitkodierung von a und b ist eine Binärgraukodendarstellung.

#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 

paar Testfälle:

• areGrayNeighbors (9,11) -> True (seit (1001, 1011) unterscheiden sich nur in einem Bit und sind aufeinanderfolgende Zahlen in Dezimaldarstellung)
• areGrayNeighbors (9,10) -> false
• areGrayNeighbors (14,10) -> True

Referenzen: Methode GTOB() verwendet wird, ist von oben in diesem Beitrag rodrigo The neighbors in Gray code

Answer 5

Sie können prüfen, ob zwei Zahlen, die durch ein Bit oder nicht, unterscheiden sich wie folgt. Bei dieser Methode wird auf Unterschiede in der Länge der Binärzahlen geachtet. ZB wird die Ausgabe für 11 (1011) und 3 (11) als wahr zurückgegeben. Dies löst auch nicht das zweite Kriterium für Gray-Code-Nachbarschaft. Aber wenn Sie nur überprüfen möchten, ob sich die Zahlen um ein Bit unterscheiden, hilft der folgende Code.

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

Answer 6

public int checkConsecutive2(int b1, int b2){ 
    int x = (b1^b2); 

    if((x & (x - 1)) !=0){ 
     return 0; 
    }else{ 
     return 1; 
    } 

} 

Answer 7

Wenn zwei Zahlen in Gray-Code-Sequenz sind, unterscheiden sie sich durch eine Binärziffer. d. h. das Exklusiv-ODER der beiden Zahlen ergibt eine Potenz von 2. Suchen Sie also XOR und prüfen Sie, ob das Ergebnis eine Zweierpotenz ist.

Diese Lösung funktioniert gut für alle oben beschriebenen Testfälle von CodeKaichu. Ich würde gerne wissen, ob es in jedem Fall scheitert.

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

Answer 8

Eine offensichtliche Antwort, aber es funktioniert. Konvertieren Sie jeden grauen Code in seine jeweilige binäre Form, subtrahieren Sie die beiden. Wenn Sie eine binäre Entsprechung von +1 oder -1 annehmen, sind die zwei grauen Codes nebeneinander.

Dies scheint wie eine Übertötung, aber wenn Sie in einem Interview Standort und nicht die richtige Methode kennen, funktioniert das. Auch zur Optimierung kann man den Einbit-Differenzfilter überprüfen, so dass wir keine Zeit damit verschwenden, Zahlen zu konvertieren und zu subtrahieren, von denen wir wissen, dass sie nicht benachbart sind.