Битовые операции 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));
}
Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: