Код Грея
В обычной двоичной записи при счёте от 7 (0111) к 8 (1000) одновременно меняются четыре бита. Если эти биты считывает механический энкодер или они выбираются по тактовому сигналу в момент изменения, может появиться любая смесь старых и новых битов, а мгновенное 1111 (15) — это большая ошибка. Код Грея (отражённый двоичный код) упорядочивает числа так, что соседние значения различаются ровно одним битом. Его используют поворотные энкодеры, карты Карно, некоторые АЦП и схемы коррекции ошибок.
Перевод в каждую сторону занимает одну строку:
gray = n ^ (n >> 1)
binary = g; while (g >>= 1) binary ^= g; // XOR со всеми сдвигами вправоBCD
Двоично-десятичный код хранит каждую десятичную цифру в отдельном 4-битном полубайте: 1234 превращается в 0001 0010 0011 0100, что как hex-число равно 0x1234. Он тратит немного места впустую (полубайты A–F никогда не используются), зато делает десятичный вывод и точную десятичную арифметику тривиальными, поэтому его используют часы, калькуляторы, финансовый COBOL и микросхема часов реального времени в каждом ПК. Чтение BCD-байта как обычного двоичного числа даёт бессмыслицу — это и есть типичная ошибка.
Popcount и чётность
Вес Хэмминга (popcount) — это количество единичных битов. На современных CPU это одна инструкция (POPCNT), и на нём основаны расстояние Хэмминга, мощность битовых множеств и некоторые трюки хеширования. Чётность — это popcount mod 2; бит чётности — простейший код обнаружения ошибок, который ловит любой одиночный инвертированный бит.
// Трюк Кернигана: каждый шаг сбрасывает младший установленный бит
int count = 0; while (n) { n &= n - 1; count++; }Вопросы
Почему поворотные энкодеры используют код Грея?
Между двумя соседними положениями меняется только один контакт, поэтому показание, снятое посреди перехода, всегда равно одному из двух соседних значений и никогда — случайному. Двоичные энкодеры во время многобитного перехода могут показать что угодно.
Код Грея единственный?
Отражённый двоичный код — стандартный, но любое упорядочение, в котором соседи различаются одним битом, — это «какой-то» код Грея. Для особых применений существуют сбалансированные и n-ичные коды Грея.
Как перевести BCD в двоичное число в коде?
Берите каждый полубайт как цифру: value = value*10 + nibble, от старшего полубайта к младшему. Или для двузначных байтов: ((b >> 4) * 10) + (b & 0x0F). Многим микросхемам RTC нужно именно это.
Как быстрее всего посчитать биты?
Используйте встроенную функцию: __builtin_popcount (C), bits.OnesCount (Go), int.bit_count() (Python 3.10+), u32::count_ones (Rust). Там, где это возможно, они компилируются в одну инструкцию.