Как узнать, являются ли два числа последовательными числами в последовательности кода Грея

Мне тоже пришлось решать этот вопрос в интервью. Одним из условий для того, чтобы два значения были последовательностью кода Грея, является то, что их значения отличаются только на 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) --> Истина

Ссылки: использованный выше метод gTob() принадлежит Родриго в этом сообщении соседи по коду Грея

Если два числа находятся в последовательности кода Грея, они отличаются на одну двоичную цифру. то есть исключающее ИЛИ для двух чисел возвращает степень 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) будет возвращен как истина. Кроме того, это не решает второй критерий смежности кода Грея. Но если вы хотите проверить, отличаются ли числа только на один бит, код ниже поможет.

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")