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

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 (если она даже использует их).

Алгоритмы Aggregate Magic - это еще одно место с некоторыми подходами к решению этой проблемы, начиная от очевидных (справочные таблицы) и заканчивая довольно умными подходами 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 с двумя инструкциями на ассемблере.