Пример наложения текста, формируемого средствами LaTeX, поверх изображения

Довольно типичной является ситуация, когда требуется вставить в текст на LaTeX изображение в векторном формате, содержащее надписи, причём эти надписи содержат формулы, и очень желательно обеспечить одинаковость шрифта в надписях в изображении со шрифтом в основном тексте. Добиться этого только средствами редактора изображений затруднительно. Обычным методом в таких случаях является использование текстовых меток («тегов») в изображении, которые, например, с помощью пакета psfrag подменяются текстом, сформированным LaTeX, уже во время компиляции tex-файла.

Однако в некоторых ситуациях psfrag не подходит. Одной из проблем с psfrag, рассчитанным на eps/dvi, является сложная схема работы с компиляцией в pdf, в процессе исполнения которой могут возникать непреодолимые ошибки. Заменить psfrag можно разными средствами. В данном посте я хочу продемонстрировать простейшее такое средство — команду \put.

Пусть есть следующее изображение (в формате pdf).

Пример векторного изображения

Пример векторного изображения

Замечание. Изображение, использованное здесь в качестве примера, было создано в векторном редакторе Inkscape. Данный редактор позволяет экспортировать изображение командами теха или генерировать вспомогательный тех-файл, использующий команду \put для вставки текстовых боксов поверх изображения, которые затем можно поправить по своему усмотрению. Однако, я не могу сказать, что это значимо упрощает работу по сравнению с «ручным методом», изложенным ниже, так как размеры текстовых надписей всё равно в итоге будут другими, а значит, всё равно придётся подгонять координаты. При этом генерируемый Inkscape’ом исходник теха содержит кучу вспомогательного кода со всякими там \makeatletter и \providecommand, что может быть непозволительной роскошью, например, при подготовке статьи в журнал.

Итак, всё что требуется — это пакет graphicx и окружение picture. Следующий пример LaTeX-кода

\documentclass[11pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}

\usepackage{graphicx} %

\usepackage{amssymb}
\usepackage[english,russian]{babel}

\begin{document}
\selectlanguage{russian}

\author{Кувшинов~Д.~Р.}
\title{Пример наложения текста, формируемого средствами
 \LaTeX, поверх изображения}

\maketitle

Какой-то текст над картинкой. Просто, чтобы занять место.
Ну должен же здесь быть какой-нибудь текст?
Хотя бы на пару строчек?

\bigskip

\begin{figure}[h]
\begin{center}
\begin{picture}(320,192)(0,0)
 \put(16,16){
  \includegraphics[width=288\unitlength]{image}}
    
 \put(53,106){
  \makebox(0,0)[lb]{$u$}}
 \put(125,109){
  \makebox(0,0)[lb]{$f$}}
 \put(106,186){
  \makebox(0,0)[lb]{$f$}}
 \put(107,56){
  \makebox(0,0)[lb]{$f$}}
 \put(226,102){
  \makebox(0,0)[lb]{$f(t,x,u)$}}
 \put(0,45){
  \makebox(0,0)[lb]{$\mathbb B^r(u; \delta(\rho))$}}
 \put(106,3){
  \makebox(0,0)[lb]{$\mathbb B^n(f(t, x, u); \rho)$}}
 \put(316,189){
  \makebox(0,0)[lb]{$\mathbb R^n$}}
 \put(224,6){
  \makebox(0,0)[lb]{$f(t, x, \mathbb B^r(u; \delta(\rho)))$}}
 \put(0,189){
  \makebox(0,0)[lb]{$\mathbb R^r$}}
\end{picture}
\end{center}
\caption{Отображение $f$.}\label{pict:P1}
\end{figure}

Ну и немного текста под картинкой. Никакого \verb!\bigskip!
или \verb!\vspace! здесь уже не требуется.

\end{document}

даёт

Результат наложения текста на картинку

Результат наложения текста на картинку

Битовые операции III: подсчёт бит

Часть I

Часть II

Чётность количества установленных бит

Рассмотрим 8-битное число, составленное из бит с b0 по b7. Число установленных бит можно получить, сложив все разряды числа: b0 + b1 + … + b7. Чётность равна остатку от деления этой суммы на 2. Иными словами, вместо сложения отдельных бит можно использовать операцию исключающее или, выполняющую сложение по модулю 2.

Благодаря ассоциативности и коммутативности сложения можно складывать биты в произвольном порядке, например, так: ((b7 + b6) + (b5 + b4)) + ((b3 + b2) + (b1 + b0)), то есть сложить пары соседних бит, потом соседние пары бит результата (из которых важен только младший бит), потом соседние четверки бит и т.д. Данный метод применим к произвольному числу бит и позволяет ускорить вычисление с помощью применения поразрядных операций, одновременно задействующих группы бит, уложенные в одном машинном слове.

Вариант для 32-битного числа (с каждым удвоением разрядности достаточно добавлять лишь одну строчку-комбинацию ^= и >>, их относительный порядок не играет роли):

inline unsigned parity(uint32_t bits)
{
  bits ^= bits >> 1;  // соседние биты
  bits ^= bits >> 2;  // соседние пары бит
  bits ^= bits >> 4;  // соседние четверки бит
  bits ^= bits >> 8;  // соседние байты
  bits ^= bits >> 16; // соседние пары байт
  return bits & 1; // чётность в младшем бите  
}

Получить сумму младших бит во всех четвёрках бит числа можно одной операцией умножения на число, составленное из четвёрок бит 00012, длиной в машинное слово, при этом результат будет находиться в четырёх старших битах. Таким образом, вышеприведённый код можно заменить на следующий код. Этот код эффективнее, если целевой процессор умеет быстро умножать (что, в частности, справедливо для современных процессоров семейства x86).

inline unsigned parity(uint32_t bits)
{
  bits ^= bits >> 1; // соседние биты
  bits ^= bits >> 2; // соседние пары бит
  bits = (bits & 0x1111'1111) * 0x1111'1111;
  return (bits >> 28) & 1;
}

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

inline unsigned parity(uint32_t bits)
{
  bits ^= bits >> 16;
  bits ^= bits >> 8;
  bits ^= bits >> 4;
  return (0x6996u >> (bits & 0xF)) & 1;
}

Наконец, если доступна быстрая функция определения числа установленных бит (например, реализованная через команду процессора), обозначенная здесь как bit_count, то достаточно взять младший бит её результата.

inline unsigned parity(uint32_t bits)
{
  return bit_count(bits) & 1;
}

Определить число установленных бит

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

unsigned bit_count(unsigned bits)
{
  unsigned counter = 0;
  for (; bits != 0; ++counter)
    bits &= bits - 1;
  return counter;
}

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

unsigned bit_count(unsigned bits)
{
  static const unsigned nibble_count[] =
  {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
  };

  unsigned counter = 0;
  while (bits != 0)
  {
    // взять младшую тетраду
    counter += nibble_count[bits & 0xF];
    bits >>= 4; // отбросить младшую тетраду
  }

  return counter;
}

«Параллельный» вариант, манипулирующий парами, четвёрками и т.д. бит (сразу немного оптимизированный):

inline unsigned bit_count(uint32_t bits)
{
  unsigned counter = 0;
  counter = bits - ((bits >> 1) & 0x5555'5555);
  counter = ((counter >> 2) & 0x3333'3333)
           + (counter & 0x3333'3333);
  counter = ((counter >> 4)  + counter) & 0x0F0F'0F0F;
  counter = ((counter >> 8)  + counter) & 0x00FF'00FF;
  counter = ((counter >> 16) + counter) & 0x0000'FFFF;
  return counter;
}

Его можно ещё слегка оптимизировать, если заметить, что по крайней мере одно наложение маски избыточно, так как переносы не пересекают последовательности нулевых бит:

inline unsigned bit_count(uint32_t bits)
{
  unsigned counter = 0;
  counter = bits - ((bits >> 1) & 0x5555'5555);
  counter = ((counter >> 2) & 0x3333'3333) 
           + (counter & 0x3333'3333);
  counter = ((counter >> 4) + counter) & 0x0F0F'0F0F;
  counter += counter >> 8;
  return (counter + (counter >> 16)) & 0x3F;
}

Наконец, для процессоров, способных быстро умножать, может использоваться следующая версия:

inline unsigned bit_count(uint32_t bits)
{
  bits = bits - ((bits >> 1) & 0x5555'5555);
  bits = (bits & 0x3333'3333)
       + ((bits >> 2) & 0x3333'3333);
  return ((bits + (bits >> 4)
       & 0x0F0F'0F0F) * 0x0101'0101) >> 24;
}

Два последних варианта позаимствованы отсюда.

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

Расстояние по Хэммингу

Вес строки бит по Хэммингу (норма) — количество единичных бит (см. предыдущий пример).

Расстояние между строками бит по Хэммингу (метрика) — количество различающихся бит в одинаковых позициях.

При наличии функции bit_count реализовать функцию, вычисляющую расстояние по Хэммингу между бит-строками, не представляет труда.

inline unsigned hamming_distance(uint32_t a, uint32_t b)
{
  return bit_count(a ^ b);
}

Определить номер самого правого установленного бита

Будем считать, что эта задача эквивалентна задаче вычисления количества идущих подряд младших нулевых бит (trailing zeroes), т.е. для нулевого аргумента ответ равен числу разрядов.

Простой и достаточно эффективный (из реализуемых стандартными операциями) способ на основе двоичного поиска, применённый к 32-битным числам.

inline unsigned trailing_zero_bits(uint32_t word)
{
  if (word & 0x1) // половина чисел -- нечётные
    return 0;

  const auto old_word = word;
  unsigned bits = 1;
  if ((word & 0xFFFF) == 0)
  {
    word >>= 16;
    bits += 16;
  }

  if ((word & 0xFF) == 0)
  {
    word >>= 8;
    bits += 8;
  }

  if ((word & 0xF) == 0)
  {
    word >>= 4;
    bits += 4;
  }

  if ((word & 0x3) == 0)
  {
    word >>= 2;
    bits += 2;
  }

  return old_word? bits - (word & 0x1) : 32;
}

Если же доступна эффективная реализация (командой процессора) операции вычисления числа установленных бит bit_count или операции leading_zero_bits, описанной в следующем разделе, то можно воспользоваться ими. Заметим, что изолировать младший ненулевой бит в числе x можно, вычислив (0 - x) & x. Если вычесть из этого числа единицу, то количество установленных бит будет равно искомому значению. Впрочем, то же самое можно получить более простым выражением (x - 1) & ~x.

inline unsigned trailing_zero_bits(unsigned word)
{
  return bit_count((word - 1) & ~word);
}

Вариант на основе leading_zero_bits потенциально менее эффективен, поскольку надо особым образом обрабатывать значение 0.

inline unsigned trailing_zero_bits(unsigned word)
{
  return word? 31 - leading_zero_bits((0 - word) & word): 32;
}

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

Определить номер самого левого установленного бита

Данная задача по сути эквивалентна задаче вычисления округлённого вниз двоичного логарифма числа и родственна задаче подсчёта количества идущих подряд нулевых старших бит (leading zeroes). Обе эти задачи могут решаться с помощью команд процессора (см. например: Википедия).

Обратив порядок поиска в примере с реализацией trailing_zero_bits через двоичный поиск, получим следующий код.

inline unsigned leading_zero_bits(uint32_t word)
{
  const auto old_word = word;
  unsigned bits = 0;
  if ((word & 0xFFFF'0000) == 0)
  {
    word <<= 16;
    bits += 16;
  }

  if ((word & 0xFF00'0000) == 0)
  {
    word <<= 8;
    bits += 8;
  }

  if ((word & 0xF000'0000) == 0)
  {
    word <<= 4;
    bits += 4;
  }

  if ((word & 0xC000'0000) == 0)
  {
    word <<= 2;
    bits += 2;
  }

  const auto non_zero_bits = bits + ((word >> 31) == 0);
  return old_word? non_zero_bits: 32;
}

Тот же метод для получения номера самого старшего установленного бита (ненулевой аргумент).

inline unsigned find_first_set(uint32_t word)
{
  assert(word != 0);
  unsigned bit = 31;
  if ((word & 0xFFFF'0000) == 0)
  {
    word <<= 16;
    bit -= 16;
  }

  if ((word & 0xFF00'0000) == 0)
  {
    word <<= 8;
    bit -= 8;
  }

  if ((word & 0xF000'0000) == 0)
  {
    word <<= 4;
    bit -= 4;
  }

  if ((word & 0xC000'0000) == 0)
  {
    word <<= 2;
    bit -= 2;
  }

  return bit - (~word >> 31);
}

При наличии эффективной реализации функции leading_zero_bits реализация find_first_set тривиальна.

inline unsigned find_first_set(uint32_t word)
{
  assert(word != 0);
  return 31 - leading_zero_bits(word);
}

Наконец, при наличии эффективной реализации функции bit_count, можно реализовать leading_zero_bits следующим образом (применив тот же приём, что и для вычисления ближайшей сверху степени двойки):

inline unsigned leading_zero_bits(uint32_t word)
{
  word |= (word >> 1);
  word |= (word >> 2);
  word |= (word >> 4);
  word |= (word >> 8);
  word |= (word >> 16);
  return 32 - bit_count(word);
}

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

Битовые операции 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 — для всех прочих перестановок.

Сравнение скорости некоторых способов организации простейших циклов по std::vector

На написание данного поста меня сподвигла статья Есть ли практический смысл использовать для итераторов префиксный оператор инкремента ++it, вместо постфиксного it++. У меня появилось желание посмотреть поведение большего числа вариантов и на современном компиляторе — в моём случае это Microsoft Visual C++ 2015 (платформа: Windows 7 x64, компиляция под x64).

Методика тестирования: заполнение массива (vector) псевдослучайными числами на основе случайного зерна размером в 10 миллионов элементов типа double, замер времени выполнения каждого варианта с помощью стандартного high_resolution_clock (имеет микросекундную точность в MSVC2015). Повторы выполнялись вручную для оценки погрешности теста «на глаз», так как высокая точность здесь не требуется, а аномалии не ожидаются (и не были обнаружены). Полученная таким образом погрешность оказалась меньше 4%.

Результаты приведены в таблице ниже. Числа соответствуют debug-сборке, запущенной из Visual Studio под отладчиком. Запуск непосредственно exe-файла без отладчика демонстрирует увеличение скорости примерно на 5% — на грани погрешности. Числа получены делением времени работы debug-сборки на время работы release-сборки. Release-сборка демонстрирует одинаковое время работы для всех вариантов (в том числе, при запуске из-под Visual Studio и запуске непосредственно exe-файла).

Вариант Замедление к release
v1, it++ 1210
v2, ++it 610
v3, it != e; ++it 230
v4, for(:) 230
v5, accumulate 18
v6, items[i] 184
v7, p[i] 3

Ниже приведён исходный код всех вариантов.

Вариант 1. Постфиксный инкремент итератора.

  for (auto it = begin(items); it != end(items); it++)
    s += *it;

Вариант 2. Префиксный инкремент итератора (быстрее варианта 1 вдвое).

  for (auto it = begin(items); it != end(items); ++it)
    s += *it;

Вариант 3. Сохранение конца диапазона в переменную (быстрее варианта 2 втрое).

  for (auto it = begin(items), e = end(items); it != e; ++it)
    s += *it;

Вариант 4. Цикл for по диапазону (эквивалентен по скорости варианту 3).

  for (auto &&item : items)
    s += item;

Вариант 5. Стандартный алгоритм accumulate (быстрее вариантов 3 и 4 более, чем в 12 раз).

  return accumulate(begin(items), end(items), Item{ 0 });

Вариант 6. Целочисленный индекс вместо итератора (незначительно быстрее вариантов 3 и 4).

  for (size_t i = 0, sz = items.size(); i < sz; ++i)
    s += items[i];

Вариант 7. Целочисленный индекс, обращение по указателю (убирает проверки диапазона при отладке, в шесть раз быстрее варианта 5).

  const auto p = items.data();
  const auto sz = items.size();
  for (size_t i = 0; i < sz; ++i)
    s += p[i];

Код теста целиком.

Итак, влияние на скорость отладки может быть очень значительным.

На мой взгляд, разумно использовать вариант 4 во всех случаях, когда нет дополнительных обстоятельств. Сделать ошибку при использовании for(:) цикла сложнее всего. Варианты 1 и 2 использовать не следует никогда. Если вариант 5 подходит к конкретной ситуации (вроде рассмотренной здесь суммы), то, наверное, следует предпочесть его, хотя и не совсем ясно, почему он оказался быстрее варианта 4. Вариант 7 я использую при написании узких циклов на векторах: опыт показывает, что на таком коде оптимизирующий компилятор обычно способен достичь большего, чем на других вариантах (правда, на такой простой задаче как сумма, это не сказалось). Данный вариант является условно-опасным: в нём даже в отладочной сборке в цикле не выполняются проверки на выход за пределы диапазона (в отличие от варианта 6).

Алгоритм построения траектории при наличии фазовых ограничений II

Трубка внутри множества достижимости в обход препятствий

Трубка внутри множества достижимости в обход препятствий

Подчищенная и сокращённая версия (март 2015) предыдущего варианта.

Презентация (PDF)

К тому моменту я сделал тестовую реализацию алгоритма в двумерном пространстве (с визуализацией в 3D). К сожалению, запустить её на конференции не получилось, так как оказалось, что на Windows XP SP3 exe, скомпилированные Visual Studio 2013, не запускаются. На случай подобных проблем у меня, естественно, были заготовлены скриншоты:

Иллюстрации к слайдам 10–14

Иллюстрации к слайдам 20–22

Perfect Hashing of Very Short Strings

This post is a (bit modified) translation of my older post in Russian.

Let a small set of very short strings (1—4 bytes here) is given and we want to construct a dictionary with strings from this set being used as keys. A simple solution is to use a universal hash table with a generic hash function (usually the one provided by the library implementing the hash table, e.g. C++ Standard library provides some std::hash implementation for strings) such as Murmur or FNV hashes.

However such a solution is a heavyweight one in some cases, for example when keys are known in advance and are short enough. This is the case when a generic array may handle the job. For this to be true we have to find a hash function that suffers no collisions for inputs from the set of our keys, so called perfect hash function.

Another feature I want is high hash computation speed, so I am not going to use complex and costly hash functions. For example Pearson hashing is too complex for me (plus I am considering CPUs capable of fast integer hardware multiplication). Finally, I am not going to use division or remainder operations. Instead I will use an array having size equal to some power of 2 (I am OK with some cells left unused).

For strings no longer than four bytes I can use 32-bit words as keys, «NUL» character is not used in texts so one-character strings have only the least significant byte being non-zero and the other three bytes being zero, two-character strings have the least significant half non-zero and the other half zero and so on. The function casting strings to integers that way may be written in C++ as follows.

inline uint32_t to_number(const std::string &word)
{
  register uint32_t result = 0;
  switch (word.size())
  {
  case 4: result  = (uint32_t)word[3] << 24;
  case 3: result |= (uint32_t)word[2] << 16;
  case 2: result |= (uint32_t)word[1] << 8;
  case 1: result |= word[0];
  default: return result;
  }
}

The hash function I am going to construct belongs to the family defined by the following template (one has to find N and b for the given set of keys).

template <uint32_t N, unsigned b>
uint32_t ssphash(uint32_t word)
{
  return (word * N) >> b;
}

Of course, there is no guarantee that for the given set of keys this family of functions contains a perfect hash function. But due to its simplicity and small combinatorial size of the problem (for modern computers) we can try to brute-force N and b (the software was written for MSVC and uses _alloca from malloc.h and intrinsic __lzcnt from intrin.h, some CPUs do not support the latter). The size of the array (our hash table) is taken as the smallest power of 2 not less than quantity of keys.

For examples for the following set of keys (operator and punctuation lexemes of C++)

+ - ! ~ # % ^ & * ( ) / // /* */ [ ] { } | ? : ; , . && || ++ -- < > " ' <= >= = == -> .* ->* << >>

I have got N == 242653, b == 17.