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

Question

Я пытаюсь найти решение проблемы, которая задана двумя числами, найти, являются ли они последовательными числами в серой последовательности кода, то есть, если они серого кода, предполагая, что серая кодовая последовательность не упоминается.

Я искал на различных форумах, но не смог получить правильный ответ. Было бы здорово, если бы вы могли предоставить решение для этого.

Моя попытка проблемы - Преобразование двух целых чисел в двоичные и добавление цифр в оба числа отдельно и поиск разницы между суммой цифр в двух числах. Если разница одна, тогда они являются соседями серого кода.

Но я чувствую, что это не будет работать для всех случаев. Любая помощь высоко ценится. Заранее большое спасибо!!!

Answer 1

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

Answer 2

На самом деле, некоторые из других ответов, кажется, не так: это правда, что два двоичной отражение коды Грея соседей отличаются только один бит (я предполагаю, что «на» Грея кодовая последовательность, вы имеете в виду исходную двоичную отраженную последовательность кода Серый, как описано Фрэнком Грей). Однако это не означает, что два кода Grey, отличающиеся одним битом, являются соседями (a => b не означает, что b => a). Например, коды Grey 1000 и 1010 отличаются только одним битом, но не являются соседями (1000 и 1010 соответственно равны 15 и 12 в десятичной форме).

Если вы хотите узнать, являются ли два серых кода a и b соседями, вы должны проверить, previous(a) = b OR next(a) = b. Для данного кода Grey вы получаете одного соседа, переворачивая самый правый бит и другой соседский бит, переворачивая бит слева от самого правого установленного бита. Для кода серого 1010 соседями являются 1011 и 1110 (1000 не является одним из них).

Получите ли вы предыдущий или следующий сосед, перевернув один из этих битов, фактически зависит от четности кода Gray. Однако, поскольку мы хотим обоих соседей, нам не нужно проверять четность. Следующий псевдокод должен вам сказать, являются ли два коды Серые соседи (с использованием C-как битовые операции):

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

Bit Хитрость выше: a & -a изолирует rigthmost набор бит в ряде. Мы сдвигаем этот бит на одну позицию влево, чтобы получить бит, который нам нужно перевернуть.

Answer 3

Если вы просто хотите проверить, если входные номера отличаются только один бит:

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

Предположения: Входы а ​​и б серые кодовые последовательности в двоичном отражается код Грея. . Битовая кодировка 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) -> Истинные (так как (1001, 1011) отличаются только один бит и являются последовательные числа в десятичном представлении)
• areGrayNeighbors (9,10) -> Ложные
• areGrayNeighbors (14,10) -> Истинные

Ссылки: метод gTob(), используемый выше, составляет от Rodrigo на этом посту The neighbors in Gray code

Answer 5

Вы можете проверить, если два числа отличаются на один бит или нет следующим образом. В этом методе заботятся о разнице в длине двоичных чисел. Например, вывод для 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)); 
    } 
} 

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

Если два числа в серой кодовой последовательности, они отличаются друг от одной двоичной цифры. т. е. исключительное ИЛИ на двух числах возвращает силу 2. Таким образом, найдите XOR и проверьте, является ли результат мощностью двух.

Это решение хорошо подходит для всех тестовых случаев, написанных CodeKaichu выше. Я хотел бы знать, если это не удастся в любом случае.

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

Answer 8

Очевидный ответ, но он работает. Преобразуйте каждый серый код в соответствующую двоичную форму, вычтите два. Если вы отвечаете на двоичный эквивалент +1 или -1, то два серых кода смежны.

Это похоже на убийство, но когда вы сидите в интервью и не знаете правильный метод, это работает. Также для оптимизации можно проверить фильтр с разностной разницей бит, поэтому мы не тратим время на преобразование и вычитание чисел, которые, как мы знаем, не смежны.