Conar 4: больше SFINAE

Начало

Предыдущая часть

Займёмся функциями, обеспечивающими чтение последовательностей. Первой такой функцией у меня будет не seq, а вариант value, который записывает каждое распознанное значение по итератору вывода.

template <class T, class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    std::is_base_of<
      std::output_iterator_tag,
    typename std::iterator_traits<OutIt>::iterator_category>
      ::value, int> = 0)
{
  using std::move;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

Мелкая неприятность: пользователь должен явно указывать тип считываемых значений T. В принципе, можно сделать два варианта: аналогичный приведённому выше и выводящий тип значения с помощью iterator_traits::value_type. К сожалению, стандартные итераторы вывода, реализующие вставку в контейнеры, определяют value_type как void, делая тип элементов контейнера невыводимым для функции value. Кроме того, заметим, что forward_iterator_tag наследует от input_iterator_tag, но не от output_iterator_tag.

Введём простенькие вспомогательные определения.

/// Check if iterator It is compatible with category Cat.
template <class It, class Cat>
using Has_iterator_category =
  is_base_of<Cat,
    typename iterator_traits<It>::iterator_category>;

/// Check if iterator It is an output iterator.
template <class It>
using Is_output_iterator =
  Has_iterator_category<It,
    output_iterator_tag>;

/// Check if iterator It is a forward iterator.
template <class It>
using Is_forward_iterator =
  Has_iterator_category<It,
    forward_iterator_tag>;

/// Check if iterator It declares void as its value type.
template <class It>
using Has_void_value =
  is_same<void,
    typename iterator_traits<It>::value_type>;

Теперь два варианта value, пишущих через итераторы можно определить следующим образом:

/// Construct a value option, which writes values through an iterator.
/// Explicitly typed variant when the type is not derivable from OutIt.
template <class T, class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_output_iterator<OutIt>::value &&
    impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

/// Construct a value option, which writes values through an iterator.
template <class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    (impl::Is_output_iterator<OutIt>::value ||
     impl::Is_forward_iterator<OutIt>::value) &&
    !impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  using T = typename std::iterator_traits<OutIt>::value_type;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

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

Теперь можно перейти к seq.

Вариант seq, заполняющий условно бесконечную последовательность по итератору, написать не составит большого труда. Полная аналогия с вариантами value, указанными выше. Как и в случае с value, предполагается, что «места хватит» (интересно, сколько параметров командной строки можно скормить в распространённых ОС/интерпретаторах?).

Приведу одну из них. Вторая абсолютно аналогична.

template <class T, class OutIt> inline
auto seq(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_output_iterator<OutIt>::value &&
    impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  return seq_parser<T>(
    [dest](T *from, T *to) mutable
    {
      while (from != to)
        *dest++ = std::move(*from++);
    },
    move(keys), move(info));
}

Для удобства пользователя можно добавить ещё три варианта seq, которые принимают непосредственно контейнеры, извлекают тип элементов через вложенное объявление value_type и выбирают способ вставки (push_back, insert или push) в зависимости от того, какой подходит. Для различения между push_back и insert (линейными и ассоциативными контейнерами) нам в качестве заготовки пригодится SFINAE-костыль Is_incrementable. Последний вариант seq подразумевает вставку в адаптер вроде std::stack с помощью вызова push.

/// Check if container C supports push_back(T&&).
template <class C, class T>
struct Supports_push_back
{
  template <class Y>
  static true_type check(decltype((void)(
    declval<Y>().push_back(declval<T>())
  ), 1));

  template <class Y>
  static false_type check(unsigned);

  using type = decltype(check<C&>(1));
  static constexpr bool value = type::value;
};

Два других детектора (Supports_insert и Supports_push) полностью аналогичны (да, макрос сюда так и просится). Вспомогательные определения для краткости записи сигнатур функций seq:

template <class C>
using Use_push_back =
  Supports_push_back<C, typename C::value_type>;

template <class C>
using Use_insert = bool_constant<
  Supports_insert<C, typename C::value_type>::value &&
  !Use_push_back<C>::value>;

template <class C>
using Use_push = bool_constant<
  Supports_push<C, typename C::value_type>::value &&
  !Use_push_back<C>::value &&
  !Use_insert<C>::value>;

Теперь вариант seq, который заполняет контейнер, предоставляющий функцию push_back, может быть записан следующим образом:

/// Construct a seq option,
/// which appends a "push_back" container.
template <class Container> inline
auto seq(Container &cont,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Use_push_back<Container>::value,
    int> = 0)
{
  using std::move;
  using T = typename Container::value_type;
  return seq_parser<T>(
    [&cont](T *from, T *to) mutable
    {
      while (from != to)
        cont.push_back(std::move(*from++));
    },
    move(keys), move(info));
}

Ещё два варианта seq полностью аналогичны.

Код данного варианта целиком.

Продолжение следует.

Conar 3: перегрузка функций и SFINAE

Часть 1

Часть 2

Написанный к данному моменту код всё ещё ничего не делает. Попробуем сделать функции-«упаковщики», создающие опции на основе заданных обработчиков и значений Possible_keys и Option_info. Роль DTO будет выполнять std::tuple<Обработчик, Possible_keys, Option_info>. Всего предполагается три семейства функций, отвечающих трём видам опций (ранее трём классам): flag, value и seq.

Предполагается, что данные функции будут перегружены. Для «выключения» ненужных шаблонов, вызывающих проблемы с неединственностью возможного варианта вызова перегруженной функции, C++11 и новее предлагает std::enable_if. Однако здесь нам неудобно ставить enable_if «впереди» (в возвращаемом типе), т.к. функции возвращают кортеж, включающий член анонимного типа. Впрочем, enable_if всегда можно поставить последним параметром.

Базовые функции имеют следующий вид:

/// Create a flag option with a custom handler.
template <class FlagHandler> inline
auto flag(FlagHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_flag_handler<FlagHandler>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      f();
      return from;
    },
    move(keys), move(info));
}

/// Create a value option with a custom handler.
template <class T, class ValueHandler> inline
auto value(ValueHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
impl::Is_value_handler_for<ValueHandler, T>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      if (from == to)
        return from;

      std::istringstream reader(*from);
      T val {};
      if (reader >> val)
      {
        f(std::move(val));
        ++from;
      }

      return from;
    },
    move(keys), move(info));
}

/// Create a value sequence option with a custom handler.
template <class T, class SeqHandler> inline
auto seq(SeqHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_seq_handler_for<SeqHandler, T>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      std::vector<T> values;
      for (std::istringstream reader; from != to; ++from)
      {
        reader.str(*from);
        T val {};
        if (!(reader >> val))
          break;

        values.emplace_back(std::move(val));
        reader.clear();
      }

      f(values.data(), values.data() + values.size());
      return from;
    },
    move(keys), move(info));
}

Теперь определим их перегруженные варианты для конкретных простых случаев.

Простейший случай — установка булевской переменной в соответствии с присутствием заданного флага в опциях.

/// Construct a flag option, which sets a Boolean variable.
inline auto flag(bool &flag_var,
  Possible_keys keys, Option_info info = {})
{
  using std::move;
  return flag(
    [&flag_var]() { flag_var = true; },
    move(keys), move(info));
}

Более хитрый случай — подсчёт количества повторения заданного флага среди набора аргументов командной строки. Для этого будем передавать объект, для которого определён инкремент. Чтобы определить, доступна ли операция инкремента, воспользуемся стандартным костылём: SFINAE (принцип действия std::enable_if тоже основан на SFINAE). Вид этого костыля вызывает стойкое желание оформить соответствующий макрос…

template <class C>
struct Is_incrementable
{
  template <class Y>
  static true_type check(decltype(
    (void)(++declval<add_lvalue_reference_t<Y>>()), 1));

  template <class Y>
  static false_type check(unsigned);

  using type = decltype(check<C>(1));
  static constexpr bool value = type::value;
};

Собственно, код-«детектор» это ++declval<add_lvalue_reference_t<Y>>(), всё остальное — «boilerplate code». std::declval<Y> по умолчанию возвращает rvalue-ссылку, для которой ++ не определён, поэтому здесь следует предварительно сформировать «обычную» (lvalue) ссылку.

/// Construct a flag option, which increments a variable.
template <class C> inline
auto flag(C &counter,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_incrementable<C>::value &&
    !impl::Is_flag_handler<C>::value, int> = 0)
{
  return flag(
    [&counter]() { ++counter; },
    move(keys), move(info));
}

С Concepts этих корявеньких enable_if бы не было, да и прочие SFINAE-обороты можно было бы привести к менее костыльному виду. Но Concepts всё никак не принимают в стандарт…

Теперь займёмся value.
Запись прочитанного значения в заданную переменную могла бы иметь примерно такой вид:

/// Construct a value option, which sets a variable.
template <class T> inline
auto value(T &var,
  Possible_keys keys, Option_info info = {})
{
  return value<T>(/* что-то */);
}

Но данная сигнатура недостаточно хорошо «отличима» от сигнатуры базовой версии функции value… Я вижу три варианта решения проблемы: а) заставить пользователя указывать тип считываемого значения явно и проверять приводимость к T; б) ввести специальную функцию var, порождающую объект-обёртку переменной; в) проверять «читабельность» значений T из потока ввода (написать SFINAE-детектор аналогичный Is_incrementable и воспользоваться enable_if).

Вариант (б) менее интуитивен и вообще не очень мне нравится. Вариант (в) технически менее изящен, но более удобен для пользователя — не надо указывать тип явно.

Наконец, можно просто дать особые имена базовым функциям flag, value и seq, удалив их из набора перегруженных «удобных» функций прямого использования. Именно так я и поступлю. Теперь базовые версии flag, value и seq носят имена flag_parser, value_parser и seq_parser.

/// Construct a value option, which sets a variable.
template <class T> inline
auto value(T &var,
  Possible_keys keys, Option_info info = {})
{
  using std::move;
  return value_parser<T>(
    [&var](T val) { var = std::move(val); },
    move(keys), move(info));
}

В принципе, сейчас уже можно написать простенькие тесты на введённые выше «удобные» функции. Тесты добавлены в namespace test заголовочного файла conar.hpp. Тесты возвращают 0 в случае успеха. Объём кода тихонечко перевалил за 300 строчек. Интересно, в 1000 строк полная версия влезет?

Код данного варианта целиком.

Продолжение следует.

Conar 2: классы за борт!

Начало

Вторая «серия» планировалась через два дня после первой. Получилось — через две недели. Лень-матушка вперёд нас родилась…

Синтаксис вызова парсера

Предложенный ранее синтаксис для Parser несколько избыточен по части скобок :)

Новый синтаксис:

auto parser = parse(опция_1, опция_2, ...);
auto unparsed = parser(argc, argv);
cout << parser.help(...) << endl;

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

namespace impl
{
  /// A stub for parse with more parameters.
  inline void parse(Parser&) {}

  /// Add all options to the parser in one recursive call.
  template <class Opt1, class... Other> inline
  void parse(Parser &parser, Opt1 &&option_1,
               Other&&... other_options)
  {
    parser(forward<Opt1>(option_1));
    parse(parser, forward<Other>(other_options)...);
  }
}

/// Make a parser with all options in one call.
template <class... Options>
Parser parse(Options&&... options)
{
  Parser parser;
  impl::parse(parser, forward<Options>(options)...);
  return parser;
}

Представление опций

Объединение общего описания possible_keys и info (фактически, это DTO) с типозависимым поведением (handler) не есть хорошо. Можно было бы сделать из Option чисто абстрактный класс («интерфейс»), наследники которого определяли бы вызов обработчика (handler) и, вероятно, распознавание текста (собственно параметров) — пара виртуальных функций.

Но зачем парсеру знать эти подробности? Фактически, с точки зрения парсера всё поведение «опции» сконцентрировано в одном действии — распознавании текста. Какие там в процессе значения получаются, и как они затем обрабатываются, парсеру всё равно. Поэтому соблазнительно определить это одним замыканием (функциональным объектом), который «скармливается» парсеру. Надо только придумать интерфейс вызова…

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

Вариант ключа 1, ключ t, time

-t5, --time=5 — только одно значение может быть параметром — то, что идёт сразу за ключом или после знака =. Это часть («хвост») аргумента командной строки. Все прочие аргументы к делу не относятся.

Вариант ключа 2, ключ times

--times 10 start 20 finish — произвольное число параметров — аргументы командной строки за аргументом, содержащим ключ, и до конца или следующего аргумента, содержащего ключ.

Вариант ключа 1 можно рассматривать как частный случай варианта ключа 2. Для разбора в какой-то форме можно передавать массив строк. А возвращать, например, количество успешно распознанных строк. Но как сообщать другие ошибки: неверный формат, недостаточное количество параметров? В конце концов, этот вопрос можно отдать на откуп обработчику, а не решать его на уровне парсера.

Итого, получаем STL-подобный интерфейс:

template <class FwdIt>
FwdIt option_parse(FwdIt from, FwdIt to);
// iterator_traits<FwdIt>::value_type = string

Статическая проверка на соответствие сигнатуры вызова предполагаемого обработчика распознанных значений ключа может выполняться с помощью следующих определений (упакованы в namespace impl):

template <class FlagHandler>
using Is_flag_handler = std::is_convertible<
	FlagHandler, std::function<void()>>;

template <class ValueHandler, class T>
using Is_value_handler_for = std::is_convertible<
	ValueHandler, std::function<void(T)>>;

template <class SeqHandler, class T>
using Is_seq_handler_for = std::is_convertible<
	SeqHandler, std::function<void(T*, T*)>>;

Код данного варианта целиком.

Продолжение следует.

Пример функциональной декомпозиции

Задача вроде тех, что решают студенты на нашем экзамене после первого семестра.

«Дана прямоугольная матрица. Найти в ней первую строку, не содержащую нулей, или определить, что таких строк нет.»

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

Решение в стиле C подразумевает прототип функции вроде (матрицу можно оформить по-разному, но предпочтём пока простейший вариант):

float* find_row_without_zero
  (float **a, size_t rows, size_t cols);

— вернуть указатель на соответствующую строку, либо nullptr, если такой нет.

Итак, студент видит слово «матрица», из чего делает вывод, что здесь явно двойной цикл, и пишет что-то такое:

float* find_row_without_zero
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
        // ???
      else
        // ???

Почему-то многим очень хочется поставить else-секцию с возвратом результата. Т.е. ошибочно подменить квантор «все» (не нули) на «существует». Под if в этом случае идёт break. Положим, стало ясно, что else здесь никак не нужен. Что же делать? Типичное неказистое решение имеет следующий вид:

// Bad structured programming (using a flag variable).
float* find_row_without_zero_1
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    bool found = true;
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
      {
        found = false;
        break;
      }
    }

    if (found)
      return a[i];
  }

  return nullptr;
}

В принципе, кто-то может решиться на использование goto, что даёт избавление от лишней переменной. Но это маловероятно: в примерах goto почти не встречается, а в книгах последних десятилетий его использование традиционно порицается.

// I'm not afraid of GOTO!
float* find_row_without_zero_2
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
      if (a[i][j] == 0)
        goto next_row;

    return a[i];
  next_row:;
  }

  return nullptr;
}

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

// Good structured programming:
// applying functional decomposition.
float* find_value
  (float *a, size_t size, float val)
{
  for (size_t i = 0; i < size; ++i)
    if (a[i] == val)
      return a + i;
  return nullptr;
}

float* find_row_without_zero_3
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (!find_value(a[i], cols, 0))
      return a[i];
  return nullptr;
}

Если предполагается использование STL (после первого семестра это ещё не предполагается), то явный цикл можно заменить на вызов std::find, так:

// Ah, std::find does the work in C++.
float* find_row_without_zero_4
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (std::find(a[i], a[i] + cols, 0.f) == a[i] + cols)
      return a[i];
  return nullptr;
}

или даже так (ещё std::find_if, шаблон по типу данных и значение по умолчанию вместо явного нуля):

// It's not beautiful, I guess...
template <class NT>
NT* find_row_without_zero_5
  (NT **a, size_t rows, size_t cols)
{
  const auto p = std::find_if(a, a + rows,
    [cols](NT *a)
    {
      return std::find(a, a + cols, NT{}) == a + cols;
    });
  return p == a + rows? nullptr: *p;
}

Последний вариант, впрочем, наверно, избыточно «навороченный».

Ну и наконец, можно поразвлекаться в функциональном стиле (требуется C++14), отказавшись от указателей и рассматривая матрицу как диапазон диапазонов. Будем возвращать итератор в стиле STL.

using std::forward;

template <class Item>
auto equals(Item &&item)
{
  return [it = forward<Item>(item)]
  (auto &&other)
  {
    return other == it;
  };
}

template <class Pred>
auto find(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::begin;
    using std::end;

    const auto e = end(rng);
    auto p = begin(rng);
    while (p != e && !pr(*p))
      ++p;

    return p;
  };
}

template <class Pred>
auto none(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::end;
    return find(pr)(rng) == end(rng);
  };
}

Вышеприведённые определения позволяют в итоге записать решение в виде композиции:

template <class Rng2>
auto find_row_without_zero_6(Rng2 &&rows)
{
  return find(none(equals(0)))(rows);
}

Забавно, что такая конструкция применима не только, например, к вектору векторов, но и к статическому двумерному массиву:

float m[3][4]
{
  { 1, 1, 1, 0 },
  { 0, 1, 1, 1 },
  { 1, 0, 1, 1 },
};

assert(find_row_without_zero_6(m) == std::end(m));

Conar: минипарсер параметров командной строки

Как известно, задача распознавания параметров командной строки давно и неоднократно решена. Примеры (список далеко не полон): Boost.Program_options (навороченная, и, увы, требует сборки), TCLAP, ezOptionParser, AnyOption, The Lean Mean C++ Option Parser. Обзора я делать не буду, напишу лишь, что ознакомление с данными библиотеками не отбило у меня желание сделать свою :)

Я хочу библиотеку: header-only (вообще полностью определённую в одном заголовочном файле), C++ (поддержка STL-контейнеров, анонимных функций), никакого (L)GPL (Boost-лицензия лучшая же), использование только Стандартной библиотеки C++ (пусть с элементами ещё не принятого C++17), действительно простая схема использования, не требующая писать каскады if-else или switch-case и явно использовать механизмы type-erasure (void*, any и т.п.). Производительность же не играет особого значения. Особая универсальность также мне не нужна.

Такая библиотека может быть достаточно маленькой для ad hoc программирования (без проектирования). Однако это не самое простое упражнение в программировании. Попробую описать её разработку (начата на момент написания этих строк) «в ходе процесса» в нескольких постах.

Итак, с чего начать? Начнём с названия :) У меня это будет conar.hpp («console arguments»).

#ifndef CONAR_HPP_INCLUDED_N98K2U
#define CONAR_HPP_INCLUDED_N98K2U

namespace conar
{
  // ...
}

#endif//CONAR_HPP_INCLUDED_N98K2U

Далее весь код размещается внутри пространства имён conar. Необходимые #include подразумеваются и в тексте не упоминаются.

Ключ — имя опции (параметра командной строки). Опции может соответствовать несколько ключей. Если ключ состоит из одной буквы, то предполагается, что перед ним ставится один дефис («минус»). Если ключ состоит из нескольких букв (и, возможно, цифр), то перед ним ставится два дефиса (предполагаемое автоматическое дополнение пользовательских ключей). Если хочется иной формулировки, например, на дробь / как принято в Windows, то достаточно будет явно указать этот знак. Предполагается, что ключи чувствительны к регистру (в Windows принято иначе, да…). При поиске соответствия будем пытаться подобрать наиболее длинное возможное совпадение. Навскидку наивный алгоритм даёт в худшем случае время разбора O(N L log K + S), где N — количество параметров, L — длина наиболее длинного ключа, K — общее количество ключей, S — суммарное количество символов во всех параметрах.

Опция вида -abc интерпретируется как последовательность трёх опций -a -b -c, если не заданы явно ключи -abc или -ab. В последнем случае возможна попытка прочитать это как -ab c, успешность которой зависит от того, принимает ли -ab строку или символ.

Итак, базовый класс Option для различных классов опций. Нужно ли здесь вообще наследование с виртуальными функциями? Не уверен, посмотрим.

  /// Basic description of a command line option.
  struct Option
  {
    using Possible_keys = std::vector<std::string>;
    using Info = std::string;

    /// Keys corresponding to this option.
    Possible_keys possible_keys;
    /// Information about this option (for help).
    Info info;

    virtual ~Option() {}
    // This class may be extended later.
  };

Классы опций. Наследники класса Option. Объекты этих классов хранят обработчики (handler) распознанных параметров.

Флаг — опция без параметров, соответственно, обработчик имеет сигнатуру void().

  struct Flag_option: Option
  {
    using Handler = std::function<void()>;
    Handler handler;
  };

Значение — опция с одним параметром заданного типа T. Посему это шаблон. Обработчик имеет сигнатуру void(T) и будет вызываться для каждого удачно распознанного ключа с параметром.

Пример (-t, --time, T = int)

-t1 --time=2 -t 3 6 7 --time 4 8 9 даст четыре вызова обработчика с параметрами 1, 2, 3 и 4.

  template <class T>
  struct Value_option: Option
  {
    using Handler = std::function<void(T)>;
    Handler handler;
  };

Последовательность — опция, предполагающая передачу последовательности значений заданного типа (T) после ключа. Обработчик имеет сигнатуру void(T*, T*) и принимает диапазон массива с очередной успешно считанной последовательностью значений (их может быть несколько — для каждого упоминания ключа).

Пример (-i, --input, T = string)

-i "a b c" d e --input "next time" do this даст два вызова с массивами { «a b c», «d», «e» } и { «next time», «do», «this» }.

  template <class T>
  struct Seq_option: Option
  {
    using Handler = std::function<void(T*, T*)>;
    Handler handler;
  };

Парсер. Главный компонент библиотеки. Опции будем регистрировать, передавая объекты классов-наследников Option с помощью оператора (), который возвращает ссылку на объект парсера. Параметры функции main для распознавания (после регистрации всех опций) также передадим оператором (). Т.е. предполагается использование вроде

Parser{}(опция 1)(опция 2)(опция 3)(argc, argv);

результат вызова — список (вектор) нераспознанных параметров (в текстовой форме «как есть»).

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

Итак, заготовка Parser.

  class Parser
  {
  public:
    /// Construct a help message part that describes all the options known to the parser.
    std::string help(int key_column_width = 20, int line_width = 80, const char *line_sep = "\n") const
    {
      std::string result;
      // TODO
      return result;
    }

    /// Add an option description. Use functions flag and value for this.
    template <class Opt>
    Parser& operator()(Opt option)
    {
      static_assert(std::is_base_of<Option, Opt>::value);
      // TODO
      return *this;
    }

    /// A list of unparsed parameters.
    using Unparsed_parameters = std::vector<std::string>;

    /// Finally parse the command-line parameters given by an iterator range (of strings).
    template <class InIt>
    Unparsed_parameters operator()(InIt from, InIt to)
    {
      static_assert(std::is_convertible<
        typename std::iterator_traits<InIt>::iterator_category,
        std::input_iterator_tag>::value);

      Unparsed_parameters unparsed;
      // TODO
      return unparsed;
    }

    /// Parse arguments as they are passed to main, argv[0] is ignored.
    Unparsed_parameters operator()(int argc, char *argv[])
    {
      return (*this)(argv + 1, argv + argc);
    }
  };

Вот так, раз-два и готов файлик в сотню строк. Которые, впрочем, пока абсолютно бесполезны…

Продолжение следует.

О реализации целочисленного аналога функции sqrt

Год назад я написал пост по обращению матриц определённого вида. Он возник не на пустом месте. Исходной посылкой послужило желание сконструировать способ качественного определения быстродействия маленьких быстро выполняющихся функций в условиях, «приближенных к реальности». На тот момент я пытался сравнивать быстродействие различных вариантов реализации функции вычисления целочисленного квадратного корня.

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

Но даже двоичный поиск можно реализовать по-разному. И естественно хочется уметь сравнивать быстродействие разных вариантов в разных условиях.

Неожиданным открытием при первом простом тестировании стала зависимость скорости выполнения функции от её положения в asm-файле (для ассемблерных вариантов). Директива align перед циклами, напротив, не продемонстрировала устойчивого эффекта. Наиболее вероятным «виновником» в данном случае является предсказатель ветвлений и особенности его работы для конкретного CPU. Также может сказываться работа L1I и TLB (здесь, в частности, может удачно или неудачно подействовать директива align).

В случае «простого» тестирования вроде многократного вызова одной функции в цикле есть немалый шанс натолкнуться на проявление таких особенностей во всей их красе. Поэтому я решил поступить несколько хитрее: выполнить псевдослучайное перемешивание разных вызовов. В каждом прогоне — разное количество вызовов разных функций. Выполнив столько же прогонов, сколько у нас есть функций, получим вектор суммарных времён и матрицу количеств вызовов. Решив линейное уравнение, получим оценки времени вызова каждой функции. Можно сделать и больше прогонов и получить решение с помощью МНК (здесь не реализовано). В итоге я всё же не стал использовать аналитически обращаемую матрицу, а задействовал библиотеку uBLAS из состава Boost. См. также о влиянии фрагментации кучи на результаты тестирования.

Использовалась среда Microsoft Visual C++ 2015, компиляция под x86-64 с O2. Причёсывать код однолетней давности я уже поленился — там есть, что выкинуть, но если бы я этим занялся, то… В общем, год уже и так прошёл.

Замечание. В MSVC все исходники .c, .cpp, .asm должны иметь разные имена, так как при компиляции каждого из них порождается одноимённый .obj файл, которые сваливаются в одну общую папку и могут затирать друг друга с печальным результатом во время компоновки.

Итак, исследуемые варианты:

  1. cpp1, asm1 — цикл + ветвление;
  2. cpp2, asm2 — цикл + cmov;
  3. cpp3, asm3 — цикл + ветвление + ilog2 (целочисленный логарифм позволяет выбрать хорошее начальное приближение, для его реализации на x86 используется команда bsr или lzcnt);
  4. cpp4, asm4 — цикл + cmov + ilog2;
  5. asm5 — развёрнутый вариант asm3;
  6. asm6 — развёрнутый вариант asm4 (computed goto);
  7. fpu — использует команды SSE для вычисления isqrt (стандартный метод);
  8. null — ничего не делает, используется для оценки времени вызова.

Итак, результаты тестирования представлены на графике ниже. Числа получены следующим образом: в каждом прогоне использовалось 100’000 псевдослучайных чисел-аргументов, равномерно распределённых от нуля до числа, указанного по оси 0x (1k — 1024, 32k — 32’768, 1M — 220, 1G — 230), выполнялось 1100 повторений, из которых верхние и нижние 5% полученных оценок времён отбрасывались, а от оставшихся 1000 бралось арифметическое среднее. Всего выполнялось по 10 таких прогонов, из результатов которых для каждой функции выбиралось минимальное значение и затем вычиталось соответствующее минимальное значение функции null. В конце все результаты нормировались по функции fpu, так что по оси 0y графиков мы видим, во сколько раз все варианты медленнее вычисления isqrt на fpu.

Процессор, на котором производился тест — AMD K10. Итак, мы видим, что «бодаться» с FPU на «больших» процессорах (пусть даже старых) бессмысленно. Пиррова победа в режиме 1k у asm4/cpp4. Применение ilog2 в комбинации с cmov даёт весьма неплохой эффект, который может оказаться ещё выше на простых процессорах без хорошего предсказателя переходов. А вот разворачивание цикла здесь не помогает (впрочем, опять же на «простом» процессоре ситуация может быть другой).

Простые годы

18 век

1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789

19 век

1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889

20 век

1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999

21 век

2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099

Пример наложения текста, формируемого средствами 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.