chess - Recuento de cero inicial/principal para un byte

bitcount

Question

Estoy usando Java y estoy codificando un motor de ajedrez.

Estoy tratando de encontrar el índice del primer 1 bit y el índice del último 1 bit en un byte.

Actualmente estoy usando Long.numberOfTrailingZeros () (o algo así) en Java, y me gustaría emular esa funcionalidad, excepto con bytes.

¿Sería algo así como:

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

De ser así, ¿cómo implementaría bitCount de manera relativamente eficiente? No me importan las buenas explicaciones, por favor no solo denme el código.

Answer 1

La respuesta correcta es que la mayoría de los procesadores tienen algunas instrucciones especiales para hacer este tipo de cosas (ceros a la izquierda, ceros al final, número de unidades, etc.). x86 tiene bsf / bsr, powerpc tiene clz, y así sucesivamente. Esperemos que Integer.numberOfTrailingZeros sea lo suficientemente inteligente como para usarlos, pero esa es probablemente la única forma que tiene la oportunidad de usar este tipo de función específica de la plataforma en Java (si es que incluso los usa).

Los algoritmos de magia global son otro lugar con algunos enfoques para este tipo de problema, que van desde lo obvio (tablas de búsqueda) hasta algunos enfoques SWAR bastante ingeniosos. Pero sospecho que todos pierden a Integer (x) .numberOfTrailingZeros () si el tiempo de ejecución de java es inteligente con respecto a este último; debería ser posible optimizar el boxeo y usar una técnica específica de plataforma para numberOfTrailingZeros, y si gana, ambos ganarán.

Solo para completarlo, el otro archivo clásico de brillante bit whacking es la antigua colección MIT HAKMEM (también hay una versión C semi-modernizada si sus habilidades de ensamblador PDP-6/10 se han oxidado).

Answer 2

usa una tabla de búsqueda con 256 entradas. para crearlo:

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; 
}

esto, por supuesto, no necesita ser rápido ya que lo haces 256 veces como máximo para iniciar tu tabla.

Answer 3

/* 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;     
}

Explicación:

Esto funciona almacenando el número de ceros a la izquierda para cada permutación de un byte como una tabla de búsqueda. Utiliza el valor de bytes para buscar el recuento de ceros a la izquierda para ese valor. Como el ejemplo hace esto para un int sin signo, cambia y enmascara los cuatro bytes individuales, y acumula las búsquedas en consecuencia. La declaración ternaria se utiliza para detener la acumulación tan pronto como encontramos un bit que está configurado. Que el valor acumulado sea 8, 16 o 24 implica que no se ha encontrado ningún bit establecido hasta el momento.

Además, algunas arquitecturas tienen soporte de hardware para esto (como una instrucción). El símbolo de la asamblea a menudo se llama ''CLZ'' o ''BSR''. Son las abreviaturas de "Count leading Zeroes" y "Bit Scan Reverse", respectivamente.

Answer 4

Si supone que Long.numberOfTrailingZeros es rápido (es decir, JIT compilado / optimizado para usar una sola instrucción ASM cuando esté disponible), entonces ¿por qué no puede simplemente hacer algo como esto?

max(8,Long.numberOfTrailingZeros(val))

donde val es el valor de tu byte convertido a Long. Esto también supone que max() está disponible y se optimiza de nuevo para usar asm select o max instructions.

Teóricamente, en una máquina que lo admita, estas operaciones podrían compilarse en JIT en dos instrucciones de ensamblador.