Как да разберете дали две числа са последователни числа в сива кодова последователност

Трябваше да разрешавам и този въпрос на интервю. Едно от условията двете стойности да бъдат сива кодова последователност е стойностите им да се различават само с 1 бит. Ето решение на този проблем:

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

Всъщност няколко от другите отговори изглеждат грешни: вярно е, че два съседни двоично отразен код на Грей се различават само с един бит (предполагам, че под « » последователността от код на Грей имате предвид оригиналния двоично отразен код на Грей кодова последователност, както е описано от Франк Грей). Това обаче не означава, че два кода на Грей, които се различават с един бит, са съседни (a => b не означава, че b => a). Например кодовете на Грей 1000 и 1010 се различават само с един бит, но не са съседни (1000 и 1010 са съответно 15 и 12 в десетичен знак).

Ако искате да знаете дали два кода на Грей a и b са съседи, трябва да проверите дали previous(a) = b OR next(a) = b. За даден код на Грей получавате един съсед чрез обръщане на най-десния бит, а другият съседен бит чрез обръщане на бита отляво на най-десния зададен бит. За кода на Грей 1010 съседите са 1011 и 1110 (1000 не е един от тях).

Дали получавате предишния или следващия съсед чрез обръщане на един от тези битове всъщност зависи от паритета на кода на Грей. Въпреки това, тъй като искаме и двата съседа, не е нужно да проверяваме за паритет. Следният псевдокод трябва да ви каже дали два кода на Грей са съседни (използвайки C-подобни побитови операции):

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

Битов трик по-горе: a & -a изолира най-десния зададен бит в число. Преместваме този бит с една позиция наляво, за да получим бита, който трябва да обърнем.

Предположения: Входове a и b са последователности от код на сиво в двоичен отразен код на сиво. т.е. битовото кодиране на a и b е представяне на двоичен сив код.

#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

Няколко тестови случая:

• areGrayNeighbors(9,11) --> True (тъй като (1001, 1011) се различават само с един бит и са последователни числа в десетично представяне)
• areGrayNeighbors(9,10) --> False
• areGrayNeighbors(14,10) --> True

Препратки: методът gTob(), използван по-горе, е от rodrigo в тази публикация The съседи в кода на Грей

Ако две числа са в сива кодова последователност, те се различават с една двоична цифра. т.е. изключителното ИЛИ за двете числа връща степен на 2. Така че, намерете XOR и проверете дали резултатът е степен на две.

Това решение работи добре за всички тестови случаи, написани от CodeKaichu по-горе. Бих искал да знам дали не успява в някои случаи.

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

Очевиден отговор, но работи. Преобразувайте всеки сив код в съответната му двоична форма, извадете двете. Ако отговорът ви е двоичен еквивалент на +1 или -1, тогава двата сиви кода са съседни.

Това изглежда като прекалено убийство, но когато участвате в интервю и не знаете правилния метод, това работи. Освен това за оптимизиране може да се провери филтърът за единични битови разлики, така че да не губим време в преобразуване и изваждане на числа, за които със сигурност знаем, че не са съседни.

Ако просто искате да проверите дали въведените числа се различават само с един бит:

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

Можете да проверите дали две числа се различават с един бит или не, както следва. При този метод се вземат предвид разликите в дължината на двоичните числа. Например изходът за 11 (1011) и 3 (11) ще бъде върнат като true. Също така, това не разрешава втория критерий за съседство на кода на Грей. Но ако искате само да проверите дали числата се различават с един бит, кодът по-долу ще ви помогне.

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

Ако две числа са в сива кодова последователност, те се различават с една двоична цифра. т.е. изключителното ИЛИ за двете числа връща степен на 2. Така че, намерете XOR и проверете дали резултатът е степен на две.

питон 3.8

a=int(input())
b=int(input())
x=a^b 
if((x and (not(x & (x - 1))) )):
    print("True")
else:
    print("False")