Конечный / ведущий нулевой счет для байта

Question

Я использую Java и кодирую шахматный движок.

Я пытаюсь найти индекс первого 1 бита и индекс последнего 1 бита в байте.

В настоящее время я использую Long.numberOfTrailingZeros () (или что-то подобное) в Java и хотел бы эмулировать эту функциональность, за исключением байтов.

Было бы что-то вроде:

byte b = 0b011000101;
int firstOneBit = bitCount ((b & -b) - 1);

Если так, как бы я реализовал bitCount относительно эффективно. Я не возражаю против хороших объяснений, пожалуйста, не просто дайте мне код.

Answer 1

использовать таблицу поиска с 256 записями. создать его:

unsigned int bitcount ( unsigned int i ) {
unsigned int r = 0;
while ( i ) { r+=i&1; i>>=1; } /* bit shift is >>> in java afair */
return r; 
}

это, конечно, не обязательно должно быть быстро, так как вы делаете это не более 256 раз, чтобы инициировать вашу таблицу.

Answer 2

/* Count Leading Zeroes */

static uint8_t clzlut[256] = {
  8,7,6,6,5,5,5,5,
  4,4,4,4,4,4,4,4,
  3,3,3,3,3,3,3,3,
  3,3,3,3,3,3,3,3,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0
};

uint32_t clz(uint32_t val)
{
  uint32_t accum = 0;

  accum += clzlut[val >> 24];
  accum += (accum == 8 ) ? clzlut[(val >> 16) & 0xFF] : 0;
  accum += (accum == 16) ? clzlut[(val >>  8) & 0xFF] : 0;
  accum += (accum == 24) ? clzlut[ val        & 0xFF] : 0;

  return accum;     
}

Пояснение:

Это работает путем сохранения числа начальных нулей для каждой перестановки байта в качестве справочной таблицы. Вы используете значение байта, чтобы найти количество ведущих нулей для этого значения. Поскольку в примере это делается для целого без знака, вы сдвигаете и маскируете четыре отдельных байта и соответственно накапливаете результаты поиска. Тернарный оператор используется для остановки накопления, как только мы находим бит, который установлен. То, что накопленное значение равно 8, 16 или 24, означает, что пока не найдено ни одного установленного бита.

Кроме того, некоторые архитектуры имеют аппаратную поддержку для этого (как инструкция). Мнемоника сборки часто называется «CLZ» или «BSR». Они являются аббревиатурами для «Подсчета лидирующих нулей» и «Обратного сканирования битов» соответственно.

Answer 3

Правильный ответ заключается в том, что большинство всех процессоров имеют специальные инструкции для выполнения подобных действий (начальные нули, конечные нули, количество единиц и т. Д.). В x86 есть bsf / bsr, в powerpc есть clz и так далее. Надеемся, что Integer.numberOfTrailingZeros достаточно умен, чтобы использовать их, но это, вероятно, единственный способ, позволяющий использовать подобную платформо-зависимую функцию в Java (если она даже использует их).

Совокупные магические алгоритмы - это еще одно место с некоторыми подходами к решению этой проблемы, начиная от очевидных (справочные таблицы) до некоторых довольно умных подходов SWAR. Но я подозреваю, что все они проигрывают Integer (x) .numberOfTrailingZeros (), если среда выполнения Java умна в отношении последнего; должна быть возможность оптимизировать бокс и использовать платформенно-зависимую технику для numberOfTrailingZeros, и если она сделает это, то выиграет.

Просто для полноты, другим классическим архивом блестящих битов является старая коллекция MIT HAKMEM (есть также полу-модернизированная C версия , если ваш PDP-6/10 навыки ассемблера стали ржавыми).

Answer 4

Если вы предполагаете, что Long.numberOfTrailingZeros - это быстро (т.е. JIT скомпилирован / оптимизирован для использования одной инструкции ASM, когда она доступна), то почему вы не можете просто сделать что-то вроде этого:

max(8,Long.numberOfTrailingZeros(val))

где val - значение вашего байта, преобразованное в Long. Это также предполагает, что max() доступно и снова оптимизируется для использования инструкций asm select или max.

Теоретически, на машине, которая его поддерживает, эти операции могут быть скомпилированы в JIT с двумя инструкциями на ассемблере.