Monthly Archives: Февраль 2016

Битовые операции 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.

Реклама