Функция прироста серого кода

Ответ 1

Простой алгоритм для увеличения серого кода:

gray_inc(x):
  if parity of x is even:
    return x xor 1
  if parity of x is odd:
    let y be the rightmost 1 bit in x
    return x xor (y leftshift 1)

Поиск четности x принимает O (log (k)), где k - длина бит x. Однако каждый шаг в этом алгоритме изменяет четность, поэтому в цикле вы можете просто чередовать четные и нечетные операции контроля четности. (Конечно, это не соответствует требованию OP, что никакое состояние не сохраняется, оно требует одного бита состояния. Также см. Ниже.)

Поиск y - это O (1) с использованием стандартного бит-хака: y = x&-x, где - - оператор с 2-мя отрицаниями; вы также можете записать его как y = x and not (x - 1).

Вы также можете использовать серый код с четностью, который представляет собой серый код, суффикс которого имеет обратный бит четности (так что четность расширенного кода всегда нечетна). В этом случае вы можете использовать следующий алгоритм O (1):

parity_gray_increment(x):
  let y be the rightmost bit in x
  return x xor ((y leftshift 1) or 1)

В обоих вышеперечисленных алгоритмах я не учитывал проверку переполнения для ясности. Чтобы сделать цикл кода при переполнении, замените y leftshift 1 на y leftshift 1 if y is not the high-order bit, else y. (В большинстве архитектур тест может быть if y leftshift 1 is not 0.) В качестве альтернативы вы можете выбросить исключение или вернуть ошибку в случае, если y слишком велико, чтобы сдвинуть влево.

Ответ 2

Есть три способа, с которыми я мог бы пойти, в зависимости от того, что вы после.

1) одна общая функция: Напишите одну функцию, которая обрабатывает максимально возможное значение graycode, которое необходимо поддерживать. Следуйте методу, который @harold предложил использовать все большие сдвиги и xors:

inline UInt16 graycodeToBinary( UInt16 value )
{
    value ^= (value >> 1);
    value ^= (value >> 2);
    value ^= (value >> 4);
    value ^= (value >> 8);
    return value;
}

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

2) функция на мощность двух То же, что и выше, но с версиями graycodeToBinary_8, _16, _32. Может быть полезно, если вы делаете много небольших конверсий и иногда очень больших. Если использование перегрузки С++ может автоматически выбрать для вас подходящую версию (и вы можете превратить ее в смешное с некоторым метапрограммированием шаблонов).

3) таблица поиска: Это кажется хорошей идеей, если вы не рассматриваете поведение кэша. Если вы не используете таблицу поиска очень часто, то она бесполезно сложна в сравнении с вышеуказанным методом. Если вы часто используете таблицу поиска, это, скорее всего, повредит ваше поведение в кеше (много разбросанных считываний в большую область памяти). Существует небольшой кусочек приложений, где это будет очень немного быстрее. Кроме того, вам нужно создать таблицу поиска, так что вы, вероятно, будете иметь уже доступную функцию для graycode_to_binary.

В конце концов, я редко нашел применение для чего-либо, кроме варианта 1). Я видел одно встроенное приложение, которое жестко закодировало таблицу поиска в нем ПЗУ. Это было прекрасно, так как процессор не имел кеша в любом случае.

Ответ 3

Я реализовал алгоритм в С#, который, кажется, работает:

Сначала вам нужна четность целого. Я реализовал его для ulong (64-разрядной), но вы можете легко изменить его на любой желаемый вывод:

public static ulong GetParity (ulong value) {
    value ^= value >> 0x20;
    value ^= value >> 0x10;
    value ^= value >> 0x08;
    value ^= value >> 0x04;
    value &= 0x0f;
    return (0x6996UL >> (int)value) & 0x01;
}

Затем вам нужно проверить, четность четности (количество бит установлено четным, если это так, вы просто меняете последний бит). Если четность нечетна, вы обычно меняете бит слева от младшего значащего бита. Это можно вычислить следующим способом:

public static ulong LeastSignificantBit (ulong value) {
    return value&((~value)+0x01);
}

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

Подводя итог, вы можете использовать следующий код:

public static ulong GrayIncrement (ulong original, int bits = 0x40) {
    ulong last = 0x01UL << (bits - 0x01);
    if (GetParity (original) == 0x00) {
        return original ^ 0x01UL;//even parity: swap least significant bit
    } else {
        ulong lbm = LeastSignificantBit(original);
        if (lbm < last) {
            return original ^ (lbm << 0x01);//otherwise swap the bit left to the least significant set bit
        } else {
            return 0x00;//wrap around
        }
    }
}

Ответ 4

Из wiki (http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code)

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