Monthly Archives: Январь 2016

Битовые операции II: изменение порядка бит

Часть I

Циклический сдвиг

Циклический сдвиг бит представляет собой операцию, напоминающую прокручивание содержимого бит-строки на месте: при сдвиге влево биты, «выпадающие» с левого конца, вставляются с правого конца (сохраняя исходный относительный порядок следования), при сдвиге вправо, наоборот, биты, «выпадающие» с правого конца, вставляются с левого.

Реализовать циклический сдвиг на заданное число бит достаточно просто. Например, сдвиг влево:

inline uint32_t rotate_left(uint32_t word, unsigned bits)
{
  return (word << bits) | (word >> (32 - bits));
}

Замечание. Если bits больше 31, то результат может быть различным (зависит от компилятора и процессора). При необходимости корректно обрабатывать случай bits > 31 на любом процессоре следует в качестве bits использовать остаток от деления bits на 32 (применить маску: bits &= 31).

Ассемблерные аналоги x86: ROL, ROR.

Поменять местами половинки слова

Частный случай циклического сдвига: сдвинуть циклически (хоть влево, хоть вправо) на половину разрядности.

inline uint32_t swap_halves(uint32_t word)
{
  return (word << 16) | (word >> 16);
}

Обратить порядок байт

Необходимость обращения порядка байт иногда возникает из-за требования передачи двоичных данных между компьютерами с разными архитектурами. Современные процессоры имеют встроенные команды для быстрого обращения порядка байт (x86) и/или способны работать в разных режимах и быстро переключаться между ними (PowerPC, ARM). Но если требуется реализовать процессорно-независимую функцию, то это можно сделать, например так (метод «в лоб», эффективен на конвейерных процессорах с большим набором регистров):

inline uint32_t swap_bytes(uint32_t word)
{
  return ((word & 0x0000'00FF) << 24)
       | ((word & 0x0000'FF00) << 8)
       | ((word & 0x00FF'0000) >> 8)
       | ((word & 0xFF00'0000) >> 24);
}

Более сложный для понимания способ (см. также следующие примеры с обращением порядка бит) использует меньше операций:

inline uint32_t swap_bytes(uint32_t word)
{
  word = ((word & 0x00FF'00FF) << 8)
       | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

Ассемблерные аналоги x86: BSWAP.

Обратить порядок тетрад

Способ, применённый для обращения порядка байт, можно расширить для обращения порядка тетрад (половинок байт). Нужно поменять местами соседние тетрады и обратить порядок байт.

inline uint32_t swap_nibbles(uint32_t word)
{
  return swap_bytes(
    ((word & 0x0F0F'0F0F) << 4)
  | ((word >> 4) & 0x0F0F'0F0F);
}

Обратить порядок бит

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

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word << 1)  & 0xAAAA'AAAA)
       | ((word >> 1)  & 0x5555'5555);
  word = ((word << 2)  & 0xCCCC'CCCC)
       | ((word >> 2)  & 0x3333'3333);
  return swap_nibbles(word);
}

Впрочем, если базовый swap_bytes реализован стандартными операциями, а не с помощью специальной команды процессора, то лучше не использовать его, а просто распространить применённый метод «наверх» вплоть до половинок 32-битного слова.

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word << 1) & 0xAAAA'AAAA)
       | ((word >> 1) & 0x5555'5555);
  word = ((word << 2) & 0xCCCC'CCCC)
       | ((word >> 2) & 0x3333'3333);
  word = ((word << 4) & 0xF0F0'F0F0)
       | ((word >> 4) & 0x0F0F'0F0F);
  word = ((word << 8) & 0xFF00'FF00)
       | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

Или так (занести маски):

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word & 0x5555'5555) << 1)
       | ((word >> 1) & 0x5555'5555);
  word = ((word & 0x3333'3333) << 2)
       | ((word >> 2) & 0x3333'3333);
  word = ((word & 0x0F0F'0F0F) << 4)
       | ((word >> 4) & 0x0F0F'0F0F);
  word = ((word & 0x00FF'00FF) << 8)
       | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

Для расширения указанного метода на 64-битные слова надо будет добавить ещё одну строчку (уже для обмена 32-битных половин) и так далее при каждом удвоении разрядности.

Некоторые процессоры (например, семейства ARMv8) предоставляют встроенную команду для обращения порядка бит.

См. также: 0, 1, 2 и 3.

Реклама

Битовые операции I: битовые поля, степень двойки

Введение

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

Предполагается, что читатель осведомлён о том, что такое поразрядные операции, и какие из них доступны в стандартном C. Стандартные целочисленные типы заданной ширины определены в stdint.h (cstdint в C++, «int» в случае C++ можно заменить на bool). Тип «unsigned» используется, чтобы показать отсутствие конкретных требований по разрядности параметра.

Так как во многих случаях описанные операции поддерживаются современными процессорами непосредственно, компиляторы предоставляют реализующие их специальные нестандартные функции («intrinsics» или «builtins»). Если целевой процессор поддерживает нужные команды, то при использовании интринсиков компилятор будет транслировать код в эти команды. К сожалению, не всегда гарантируется автоматическая подмена неподдерживаемых команд программными реализациями, поэтому при написании кроссплатформенного кода могут понадобиться собственные «заменители» для общего случая. Да и не всегда хочется отягощать код использованием интринсиков.

Простейшие манипуляции

Проверить значение заданного бита

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

inline int test_bit(unsigned word, unsigned bit)
{
  return (word & (1u << bit)) != 0;
}

Ассемблерные аналоги x86: BT.

Изменить значение заданного бита

Следующие четыре функции возвращают новое значение слова (с изменённым битом в заданной позиции):

// Установить заданный бит
inline unsigned set_bit(unsigned word, unsigned bit)
{
  return word | (1u << bit);
}

// Сбросить заданный бит
inline unsigned reset_bit(unsigned word, unsigned bit)
{
  return word & ~(1u << bit);
}

// Поменять значение заданного бита на противоположное
inline unsigned toggle_bit(unsigned word, unsigned bit)
{
  return word ^ (1u << bit);
}

// Установить заданный бит в заданное значение
inline unsigned set_bit(
  unsigned word, unsigned bit, int value)
{
  unsigned mask = 1u << bit;
  return (word & ~mask) | (value? mask: 0);
}

Ассемблерные аналоги x86: BTS, BTR, BTC.

Извлечь битовое поле

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

unsigned mask = (1u << bits) - 1;

Теперь можно сдвинуть полученную таким образом маску влево, чтобы установленные биты совпали с битами, стоящими в желаемых позициях (битовым полем). Под «битовым полем» в данном примере понимается непрерывный фрагмент машинного слова (например, все биты с 5-го по 10-й включительно).

Пусть задан номер начального бита, принадлежащего битовому полю (start), и количество бит, входящих в битовое поле (length; соответственно, все биты с 5-го по 10-й включительно: start = 5, length = 6). Тогда извлечь значение битового поля в виде беззнакового целого можно следующей функцией:

inline unsigned get_bitfield(
  unsigned word, unsigned start, unsigned length)
{
  return (word >> start) & ((1u << length) - 1);
}

Ассемблерные аналоги x86: BEXTR (BMI).

Установить значение битового поля

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

inline unsigned set_bitfield
(
  unsigned word,   // Исходное значение
  unsigned start,  // Номер младшего бита поля
  unsigned length, // Длина поля
  unsigned value   // Новое значение поля
)
{
  unsigned mask = (1u << length) - 1;
  return (word & ~(mask << start)) 
       | ((value & mask) << start);
}

Наложение маски на value можно убрать, если гарантируется, что value не выходит за пределы диапазона значений битового поля (т.е. value ∈ [0, 2length-1]).

Совместить два значения

Изменение значения битового поля является частным случаем поразрядного совмещения (смешивания) значений. Пусть дана маска (mask), каждый бит которой равен 0, если значение соответствующего разряда результата следует взять из первой бит-строки (a), и 1, если значение разряда следует взять из второй бит-строки (b). Тогда выполнить операцию совмещения достаточно легко:

inline unsigned bit_blend(
  unsigned mask, unsigned a, unsigned b)
{
  return (a & ~mask) | (b & mask);
}

Степень двойки

Проверить, является ли число степенью двойки

Степень двойки в двоичной системе имеет вид 0..010…0 (только один бит установлен). Поэтому при вычитании единицы получаем 0..001…1, т.е. только в случае степени двойки выполняется условие нулевого пересечения числа с самим собой, уменьшенным на единицу. Итак,

inline int is_pow2(unsigned word)
{
  return word & (word - 1) == 0;
}

Ряд подобных простых комбинаций, которые могут использоваться как строительные кубики, был введён в систему команд x86 в составе набора BMI.

Вычислить ближайшее сверху кратное заданной степени двойки

Пусть заданы натуральные числа P = 2p и число X. Необходимо вычислить наименьшее число N такое, что N ≥ X и N = nP для некоторого натурального n.

Метод вычисления. В случае, если X mod P не ноль, то добавление к X максимального остатка (P – 1) даёт перенос бита в разряд p, а если X mod P — ноль, то не даёт. Таким образом, если обнулить младшие p бит суммы (X + (P – 1)), то получим искомое: N = (X + (P – 1)) & ~(P – 1).

inline unsigned round_up_to_pow2(unsigned x, unsigned pow2)
{
  unsigned pow2m1 = pow2 - 1;
  // pow2 обязано быть степенью двойки
  assert((pow2 & pow2m1) == 0);
  return (x + pow2m1) & ~pow2m1;
}

Вычислить ближайшую сверху степень двойки

Требуется вычислить число, равное степени двойки, не меньшей, чем заданное натуральное число. Данную операцию реализовать сложнее, чем предыдущие. Ниже приведена реализация для 32-битного числа (позаимствовано отсюда).

inline uint32_t round_up_to_pow2(uint32_t x)
{
  --x;
  x |= x >> 1;  // Группа наложений-сдвигов эффективно
  x |= x >> 2;  // заменяет линейную последовательность вида
  x |= x >> 4;  // x |= x >> 1; x |= x >> 2; x |= x >> 3; ...
  x |= x >> 8;  // x |= x >> 31;
  x |= x >> 16; // На каждое удвоение разрядности достаточно
  return x + 1; // добавлять одну такую строчку.
}

Впрочем, если имеется эффективная реализация функции leading_zero_bits, подсчитывающей количество идущих подряд старших нулей (можно реализовать её на основе команд x86 BSR или (ABM/BMI) LZCNT, в дальнейшем я планирую привести реализацию на основе стандартных операций), то можно использовать её:

inline unsigned round_up_to_pow2(unsigned x)
{
  unsigned not_pow2 = (x & (x - 1)) != 0;
  return 1u << (32 - (leading_zero_bits(x) + not_pow2));
}

Сознание: этюд

Данная запись является наброском, отчасти продолжающим предыдущую. Следующий абзац взят из некогда начатого мной текста (естественно, так и не дописанного).

В детстве меня удивляла мысль, что один и тот же «раздражитель» может представляться разным людям по-разному и сравнить эти представления невозможно. Например, почему красный именно красный, а зелёный — зелёный? Почему мы видим так, а слышим — иначе? Что было бы, если бы у нас было ещё и зрение-слух? Можно ли себе представить такое? И не связаны ли индивидуальные различия во вкусах людей с различным восприятием одних и тех же раздражителей в конце цепочки? Например, всем нравится «воспринимаемый цвет А». Часть людей видит красный цвет как цвет А, и говорят, что им нравится красный цвет. Другая часть видит синий цвет как цвет А, и говорят, что им нравится синий цвет. Может быть, кто-то видит синий так, как я вижу красный, а красный так, как я — зелёный? То, что глаз этого человека показал бы мне то же самое, что и мой глаз, ещё ни о чём не говорит. Аналогичные рассуждения имеют место для всех прочих ощущений.

(Оригинальная картинка взята с Wikipedia.)

Все видят это так

Все видят это так

Можем ли мы быть уверены, что другой человек не «воспринимает» цвета иначе, чем мы? Например, ему «зелёный» как нам «красный», а «голубой» — как «зелёный».

Но кто-то может воспринимать первую картинку например так

Но кто-то может воспринимать первую картинку например так

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

Tempus fugit, dies volant, anni pereunt

Время бежит, дни летят, годы уходят.

У меня сложилось впечатление, что перед наступлением нового года время как бы замедляется, становится более тягучим. А по наступлении оного резко ускоряется, и дни бегут. Бегут так, что не успеваешь их считать. Вроде только-только было тридцать первое, и вот, уже седьмое. Моргнёшь, и уже будет тринадцатое, а то и двадцатое. Может быть, это такой психологический эффект, обусловленный насыщенностью событиями соответствующих временных промежутков? Про то не ведаю.

И вот, кажется, есть некое свободное время. Можно многое сделать. Так кажется. Пока это время не наступило. А когда наступило, то результаты усилий достигаются в день по чайной ложке. Наверно, тоже психологический эффект. Но это мелочи. Есть сотни начинаний мелких и не совсем мелких, застрявших на разных стадиях осуществления. К примеру, хотел сделать статью. Написал за одну неделю, вторую неделю ноября. Потом аврал прошёл и, решив воспользоваться доступным временем, я начал её переписывать (а причины к тому, естественно, были). Думаю, очевидно, что оный процесс не завершён и по сей день. Иным из таких начинаний уже несколько лет.

Но и это ещё не самое плохое. А плохое, отвратительное, отвращающее — это осознание бессмысленности. Даже если всё взять и закончить в «лучшем виде» (как представляется или представлялось мне), то это всё равно никому не нужно. В лучшем случае — отчётность и показатели. Хорошо, но не вдохновляет от слова «никак». Вот взять содержимое учебных курсов, которое я делаю (а я считаю это лучшим, из того что делаю). Студенты его даже читают, сам видел. Но вот «выхлоп» несоизмерим с затраченными усилиями. Почему я так считаю? А никто из них не задаёт глубоких вопросов. Или этот блог — самая популярная запись каждый год одна и та же: Графы-4: максимальный поток, 2011 года, абсолютно периферийная для меня. Это некие несчастные студенты пытаются что-то там найти в интернетах, я так понимаю.

Я уже склонен считать, что то, что «застревает» в вечно недоделанном состоянии, застревает оттого что «всё равно не нужно» и тормозится на уровне «подсознания» (оно, скорее, не под-, а над-), как неоправданная трата сил. Осталось только понять, что же действительно нужно.

Аналитическое обращение матриц из одного узкого класса

Disclaimer: вполне вероятно, что данный результат давно был кем-то получен или выводится из каких-то более общих результатов для матриц подобного вида, но я не знаток матричной математики, а серьёзный поиск предпринимать было лень.

Пусть n ∈ ℕ, определим A(n) как n×n-матрицу следующего вида:

  1     2    3   ...  (n−2) (n−1)   n
  2     3    4   ...  (n−1)   n     1
  3     4    5   ...    n     1     2
                 ...
                 ...
                 ...
(n−2) (n−1)  n   ...  (n−5) (n−4) (n−3)
(n−1)   n    1   ...  (n−4) (n−3) (n−2)
  n     1    2   ...  (n−3) (n−2) (n−1)

Википедия сообщает, что данные матрицы являются подмножеством класса матриц, называемых «антициркулянтами».

Оказалось, что для любого n не составляет труда выписать матрицу A−1(n). Приведённая ниже конструкция была получена эмпирически, затем проверена аналитически «на бумажке».

Обозначим q = 1 + 2 + … + n = n(n + 1)/2, a = (1 − q), b = (1 + q), c = nq, тогда матрица cA−1(n) имеет следующий вид:

a  1  1  1  ...  1  b
1  1  1  ...  1  b  a
1  1  ...  1  b  a  1
...
...
...
1  1  b  a  1  ...  1
1  b  a  1  1  ...  1
b  a  1  1  1  ...  1

То есть также является «антициркулянтом», не содержащим нулевых элементов.
Доказать то, что указанная конструкция действительно даёт нам обратную к A(n) матрицу, не составляет большого труда. Для этого достаточно проверить, что:

  • (1, 2, 3, …, n)T(a, 1, 1, …, 1, b) = c;
  • при i = 1, 2, …, (n−1) имеем i(b + a) + a + q − 2i − 1 = 0 — для всех прочих перестановок.