Соседи в коде Грея

Question

Есть ли алгоритм, который я могу использовать, чтобы найти соседей в коде Грея?

Для небольших чисел просто хорошо написать всю таблицу, но если у меня есть число, подобное 010 110, будет слишком много, чтобы написать всю таблицу серого кода с 6 числами.

Answer 1

Скопировано бесстыдно из Википедии:

/*
        The purpose of this function is to convert an unsigned
        binary number to reflected binary Gray code.

        The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
        return (num >> 1) ^ num;
}

/*
        The purpose of this function is to convert a reflected binary
        Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}

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

unsigned int nextGray(unsigned int num)
{
    return binaryToGray((grayToBinary(num) + 1) & 0x3F);
}

unsigned int prevGray(unsigned int num)
{
    return binaryToGray((grayToBinary(num) - 1) & 0x3F);
}

Answer 2

По определению, любое возмущение с изменением одного бита является допустимым смежным кодом Грея. Проблема состоит в том, что для шестибитового значения существует шесть возможных результатов, и только два из них могут быть правильными в любом отдельном кодировании.

Недетерминизм усугубляется, когда вы увеличиваете размер слова.

Answer 3

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

В противном случае вы можете использовать следующую операцию:

unsigned next_gray(unsigned gray)
{
    if (is_gray_odd(gray))
    {
        unsigned y = gray & -gray;
        return gray ^ (y << 1);
    }
    else
    {
        // Flip rightmost bit
        return gray ^ 1;
    }
}

Как видите, вы должны знать четность кода Грея, чтобы узнать, какое вычисление применить. Четность обычного кода Грея такая же, как и четность его количества установленных битов. Отсюда следующая формула для вычисления is_gray_odd:

bool is_gray_odd(unsigned gray)
{
    for (size_t i = CHAR_BIT * sizeof(int) / 2u ; i ; i >>= 1u)
    {
        gray ^= (gray >> i);
    }
    return (bool)(gray & 1u);
}

Функция previous_gray будет такой же, как функция next_grayза исключением того, что вы должны полностью изменить условие. В любом случае, обратное преобразование в обычный может в конечном итоге быть быстрее.

РЕДАКТИРОВАТЬ: если вы используете GCC или Clang, вы можете использовать встроенный компилятор __builtin_parity вычислить четность серого кода (и, возможно, проверить на наличие __GNUC__ а также __clang__ оставаться кроссплатформенным):

bool is_gray_odd(unsigned gray)
{
    return (bool) __builtin_parity(gray);
}

Если вы сделаете это, вычисление следующего / предыдущего серого кода может быть быстрее, чем преобразование серого кода назад и вперед в двоичный код на некоторых архитектурах. В любом случае, если вы хотите скорость, вам лучше ориентироваться.

РЕДАКТИРОВАТЬ 2: Если вам нужны только два соседа, и вас не волнует, какой из них предыдущий, а какой следующий, а они вас даже не интересуют, то вы можете получить их обоих следующим образом:

unsigned neighbour1 = gray ^ 1;
unsigned neighbour2 = gray ^ ((gray & -gray) << 1);