Как сравнить два числа в коде Грея?

Question

[Undefined Null]

Например у нас есть два числа X и Y закодированных в коде Грея. Каким образом мы можем эффективно их сравнить?

Например:
X(10) = 12 X(2) = 1100 X(Grey) = 1010
Y(10) = 15 Y(2) = 1111 Y(Grey) = 1000

Answer 1

[Undefined Null]

Чтобы сравнить два числа грея без перевода в бинарную систему мы используем его рефлективность. Числа будем сравнивать побитово. Если у нас первый бит у X равен 0 а у Y равен 1, то Y больше X. Если у нас два числа начинаются одинаково, то все равно смотрим на первый бит. Допустим он у нас 0 в таком случае сравниваем два следующих бита как обычно (т.е. 1 больше 0). Если же у нас первый бит 1, то нужно сделать инвертирование сравнения следующего 2-го бита (т.е. 0 больше 1)

Например имеем числа 4 (десятичное) и 6 (десятичное), после перевода их в числа Грея будем иметь соотвественно 110 и 101. Как мы видим первый бит 1 значит следующий надо сравнить инвертируя логику (101 больше чем 110). Если единица в качестве первого бита будет два раза подряд то инвертируем два раза. Возьмем числа 8 и 9 и представим в виде кода Грея 1100 и 1101. 1й бит одинаковый и единица - инвертируем логику сравнивания, 2й бит снова единица снова инвертируем обратно, 3й бит одинаковый это 0 то ничего не инвертируем и сравниваем нормально последний 4й бит. В 9ке он равен единице а в 8ке нулю. То есть (1100 меньше чем 1101)

Answer 2

[jcmvbkbc]

Смысл младших битов кода Грея зависит от значения старших битов, поэтому вряд ли можно избежать перевода значения из кода Грея в обычный двоичный. Если битность кода фиксированная и небольшая, скорее всего оптимальный вариант -- перевести в двоичный код и сравнить. Если битность большая или переменная, то можно переводить и одновременно сравнивать уже переведённые биты и останавливаться на первом неравенстве. См.

Comments

[Undefined Null]

Требуется именно решение без перевода в двоичный код.
Я пока только придумал измерить количество битов записанных в коде Грея и разделить пополам число сравнить его части. В коде Грея ведь изменения рефлекторны и различаются первым битом на каждой половине

1. 0 00
   
2. 0 01
   
3. 0 11
   
4. 0 10
   
   
5. 1 10
   
6. 1 11
   
7. 1 01
   
8. 1 00
   

[jcmvbkbc]

Каким образом мы можем эффективно их сравнить?

Требуется именно решение без перевода в двоичный код.

freelion, ты уж определись

[Undefined Null]

jcmvbkbc, эффективно без перевода обратно в двоичный код. Если числа различаются по первому биту скажем у X первый бит 0 а у Y первый бит 1, то тут очевидно что X меньше Y.
А что есть у нас есть большие числа в коде Грея с одинаковым первым битом:
X = 11000110100
Y = 11010010010
То как их эффективно сравнить не переводя в обычное бинарное

[jcmvbkbc]

freelion, я тебе такой вариант предложил, если ты внимательно прочитал мой ответ. И там же написал, что не всегда это имеет смысл. Ну, если тебя практическая эффективность интересует, типа, "какого размера массивы чисел сможем сравнить за единицу времени на данном железе".

[jcmvbkbc]

freelion, типа того:

// -1 <=> a < b, 0 <=> a == b, 1 <=> a > b
int cmp(T a, T b)
{
    T top;

    if (a == b)
        return 0;

    top = ((T)1) << (sizeof(T) * 8 - 1 - clz(a ^ b));
    n = popcnt(a & (-top << 1));

    if (n & 1)
        return (a & top) ? -1 : 1;
    else
        return (a & top) ? 1 : -1;
}

где clz определяет число старших нулевых битов, а popcnt -- число установленных в единицу битов.

[Undefined Null]

jcmvbkbc, спасибо большое за помощь, я нашел способ сравнивать без перевода