Determinar qué bit único en el byte está establecido

9 minutos de lectura

Determinar que bit unico en el byte esta establecido
recursion.ninja

tengo un byte Estoy usando para banderas de bits. Yo sé eso uno y solo uno poco en el byte se establece en cualquier momento dado.

Ex: unsigned char b = 0x20; //(00100000) 6th most bit set

Actualmente uso el siguiente bucle para determinar qué bit está configurado:

int getSetBitLocation(unsigned char b) {
  int i=0;
  while( !((b >> i++) & 0x01) ) { ; }
  return i;
}

¿Cómo determino más eficientemente la posición del bit establecido? ¿Puedo hacer esto sin iteración?

  • Suponiendo un byte de 8 bits, el uso de una tabla de búsqueda podría ayudar, a menos que pueda utilizar una instrucción / primitiva de ‘contar ceros iniciales’.

    – Brett Hale

    20 de enero de 2013 a las 21:42


  • “¿Puedo hacer esto sin iteración?” Use una tabla de búsqueda o una declaración de cambio.

    –David Heffernan

    20 de enero de 2013 a las 21:44

  • Esperaba un pequeño truco, no un obvio switch declaración

    – recursion.ninja

    20 de enero de 2013 a las 21:46

  • Puedes llegar a tres comparaciones y algunas matemáticas. ¿Será realmente más rápido que este ciclo? Difícil de decir.

    – John Dvorak

    20 de enero de 2013 a las 21:48


  • Si este es su cuello de botella, entonces no superará la tabla de búsqueda. Supongo que en realidad no ha creado ningún perfil y está optimizando sin el beneficio de eso.

    –David Heffernan

    20 de enero de 2013 a las 21:57

1647704592 757 Determinar que bit unico en el byte esta establecido
Juan Dvorak

¿Puedo hacer esto sin iteración?

De hecho, es posible.

¿Cómo determino más eficientemente la posición del bit establecido?

Puedes probar este algoritmo. Divide el carácter por la mitad para buscar el bit superior, cambiando a la mitad inferior cada vez:

int getTopSetBit(unsigned char b) {
  int res = 0;
  if(b>15){
    b = b >> 4;
    res = res + 4;
  }
  if(b>3){
    b = b >> 2;
    res = res + 2;
  }

  //thanks @JasonD
  return res + (b>>1);
}

Utiliza dos comparaciones (tres para uint16s, cuatro para uint32s…). y podría ser más rápido que su bucle. Definitivamente no es más corto.


Basado en la idea de Anton Kovalenko (búsqueda hash) y el comentario de 6502 (la división es lenta), también sugiero esta implementación (8 bits => hash de 3 bits usando un de-Bruijn secuencia)

int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2};

int getBitPosition(unsigned char b) {
  // return lookup[(b | (b>>1) | (b>>2) | (b>>4)) & 0x7];
  return lookup[((b * 0x1D) >> 4) & 0x7];
}

o (LUT más grande, pero usa solo tres términos en lugar de cuatro)

int[] lookup = {0xFF, 0, 1, 4, 2, 0xFF, 5, 0xFF, 7, 3, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF};

int getBitPosition(unsigned char b) {
  return lookup[(b | (b>>3) | (b>>4)) & 0xF];
}

  • Puede eliminar el último if () y simplemente agregar b-1

    – JasonD

    20 de enero de 2013 a las 21:57

  • @JasonD no b-1pero b>>1. b podría ser 2 o 3.

    – John Dvorak

    20 de enero de 2013 a las 21:59

  • @JanDvorak inteligente, esto puede que ser más eficiente

    – recursion.ninja

    20/01/2013 a las 22:00

  • @JanDvorak Dijo que solo se configuró 1 bit, por lo que solo debería ser 1 o 2. Sin embargo, su alternativa es más general.

    – JasonD

    20 de enero de 2013 a las 22:01

  • @JanDvorak Su tabla de búsqueda hash lookup[((b * 0x1D) >> 4) & 0x7]; pasé mis 8 casos de prueba por bytes { 0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80 } al verificar la ubicación del único bit establecido. ¡Muy elegante! ¿Puedo preguntar de dónde sacaste el hachís? ¿Podría vincular a las secuencias de De-Brujin?

    – recursion.ninja

    20 de enero de 2013 a las 23:51


Determinar que bit unico en el byte esta establecido
Antón Kovalenko

La tabla de búsqueda es lo suficientemente simple y puede reducir su tamaño si el conjunto de valores es escaso. Probemos con 11 elementos en lugar de 128:

unsigned char expt2mod11_bits[11]={0xFF,0,1,0xFF,2,4,0xFF,7,3,6,5};
unsigned char pos = expt2mod11_bits[b%11];
assert(pos < 8);
assert(1<<pos == b);

Por supuesto, no es necesariamente más efectivo, especialmente para 8 bits, pero el mismo truco se puede usar para tamaños más grandes, donde la tabla de búsqueda completa sería terriblemente grande. Vamos a ver:

unsigned int w; 
....
unsigned char expt2mod19_bits[19]={0xFF,0,1,13,2,0xFF,14,6,3,8,0xFF,12,15,5,7,11,4,10,9};
unsigned char pos = expt2mod19_bits[w%19];
assert(pos < 16);
assert(1<<pos == w);

  • Buena idea para tamaños más grandes… pero para 8 bits supongo que la operación del módulo será un problema.

    – 6502

    20 de enero de 2013 a las 22:08

  • En x86, probaría el ensamblaje en línea con BSF.

    – Antón Kovalenko

    20 de enero de 2013 a las 22:15

  • @AntonKovalenko, excepto que mod-11 es independiente de la plataforma, mientras que BSF no lo es.

    – John Dvorak

    20 de enero de 2013 a las 22:19

  • @JanDvorak: eres demasiado optimista. La división siempre ha sido molestamente lenta… tan lenta que cuando diseñaron el primer procesador Pentium incluso intentaron recortar algunos atajos ;-). Si necesitas el cociente, la división se puede cambiar por una multiplicación en muchos casos, pero si necesitas el resto, ese truco no funciona. Y ni siquiera la multiplicación de enteros IIRC es de 2 ciclos en cualquier procesador que usé.

    – 6502

    20 de enero de 2013 a las 22:22

  • @JanDvorak No cabe en el área de comentarios, pero comienza con una multiplicación por 780903145. Tenga en cuenta que ese número es exactamente 0x200000003 / 11.

    usuario743382

    20 de enero de 2013 a las 22:33


1647704594 228 Determinar que bit unico en el byte esta establecido
6502

Este es un problema bastante común para los programas de ajedrez que usan 64 bits para representar posiciones (es decir, un número de 64 bits para almacenar dónde están todos los peones blancos, otro para dónde están todos los peones negros, etc.).

Con esta representación, a veces es necesario encontrar el índice 0…63 del primer o último bit establecido y existen varios enfoques posibles:

  1. Solo haciendo un bucle como lo hiciste
  2. Utilizando una búsqueda dicotómica (es decir, si x & 0x00000000ffffffffULL es cero, no hay necesidad de verificar los 32 bits bajos)
  3. Usar instrucciones especiales si están disponibles en el procesador (p. ej. bsf y bsr en x86)
  4. Usar tablas de búsqueda (por supuesto, no para el valor completo de 64 bits, sino para 8 o 16 bits)

Sin embargo, lo que es más rápido realmente depende de su hardware y de los casos de uso reales. Solo para 8 bits y un procesador moderno creo que probablemente una tabla de búsqueda con 256 entradas es la mejor opción…

Pero, ¿está realmente seguro de que este es el cuello de botella de su algoritmo?

  • ...FULL significa “largo largo sin firmar”?

    – John Dvorak

    20 de enero de 2013 a las 22:06

  • ULL es el sufijo, el F es solo el último dígito hexadecimal, lo editaré para que quede más claro

    – 6502

    20 de enero de 2013 a las 22:11

  • Quise decir, ¿es realmente compilable, o solo un marcador de posición/puntos suspensivos 🙂

    – John Dvorak

    20 de enero de 2013 a las 22:13

1647704595 625 Determinar que bit unico en el byte esta establecido
salvaje

unsigned getSetBitLocation(unsigned char b) {
  unsigned pos=0;
  pos = (b & 0xf0) ? 4 : 0; b |= b >>4;
  pos += (b & 0xc) ? 2 : 0; b |= b >>2;
  pos += (b & 0x2) ? 1 : 0; 
  return pos; 
}

Sería difícil hacerlo jumpfree. ¿Quizás con las secuencias de Bruin?

Basado en el cálculo de log2 en Encuentre el logaritmo en base 2 de un entero de N bits en operaciones O(lg(N)):

int getSetBitLocation(unsigned char c) {
  // c is in {1, 2, 4, 8, 16, 32, 64, 128}, returned values are {0, 1, ..., 7}
  return (((c & 0xAA) != 0) |
          (((c & 0xCC) != 0) << 1) |
          (((c & 0xF0) != 0) << 2));
}

  • Esto se basa en el hecho de que != devoluciones 0 o 1. ¿Está garantizado por la especificación? También supongo que realmente no evita la ramificación debido a cómo != está implementado.

    – John Dvorak

    20 de enero de 2013 a las 22:49


  • @JanDvorak: sí, se agregó en c99. (Usé el ternario para ser compatible hacia abajo con c89/c90) Y, de hecho, parece que no se salta. (pero hay algunas instrucciones extrañas hoy en día)

    – salvaje

    20 de enero de 2013 a las 22:54


  • @JanDvorak: sí, está garantizado incluso antes de c99. Además, no veo ninguna bifurcación en el código. Tú podrías ver su montaje online. ¿Podría señalar las instrucciones de bifurcación?

    – jfs

    22 de enero de 2013 a las 2:52

  • @JFSebastian Sin optimización, envuelto en int main(char c)el tres !=s vuelta a set if not equal en línea 0x14 (impresionante), 0x25: je 0x2E / 0x2C: jmp 0x33 (ay, una instrucción de bifurcación), y el mismo combo aparece en 0x40. Con las optimizaciones activadas, el jes vuelta a subtract with borrows (impresionante) ARM usa un move if not equal / move if equals combo (buenas instrucciones). Gracias por el enlace al compilador.

    – John Dvorak

    22 de enero de 2013 a las 8:15


  • Tenga en cuenta que la solución basada en deBrujin se convierte en solo cinco operaciones: MOVZB, IMUL, SAR, AND, MOV

    – John Dvorak

    22 de enero de 2013 a las 8:35

1647704595 534 Determinar que bit unico en el byte esta establecido
Comunidad

Lo más fácil es crear una tabla de búsqueda. El más simple será escaso (con 256 elementos) pero técnicamente evitaría la iteración.

Este comentario técnicamente evita la iteración, pero a quién engañamos, sigue haciendo la misma cantidad de comprobaciones: Cómo escribir log base(2) en c/c++

Forma cerrada sería registro2()a la, log2() + 1 Pero no estoy seguro de cuán eficiente es eso, ¿posiblemente la CPU tiene una instrucción para tomar logaritmos de base 2?

  • Esto se basa en el hecho de que != devoluciones 0 o 1. ¿Está garantizado por la especificación? También supongo que realmente no evita la ramificación debido a cómo != está implementado.

    – John Dvorak

    20 de enero de 2013 a las 22:49


  • @JanDvorak: sí, se agregó en c99. (Usé el ternario para ser compatible hacia abajo con c89/c90) Y, de hecho, parece que no se salta. (pero hay algunas instrucciones extrañas hoy en día)

    – salvaje

    20 de enero de 2013 a las 22:54


  • @JanDvorak: sí, está garantizado incluso antes de c99. Además, no veo ninguna bifurcación en el código. Tú podrías ver su montaje online. ¿Podría señalar las instrucciones de bifurcación?

    – jfs

    22 de enero de 2013 a las 2:52

  • @JFSebastian Sin optimización, envuelto en int main(char c)el tres !=s vuelta a set if not equal en línea 0x14 (impresionante), 0x25: je 0x2E / 0x2C: jmp 0x33 (ay, una instrucción de bifurcación), y el mismo combo aparece en 0x40. Con las optimizaciones activadas, el jes vuelta a subtract with borrows (impresionante) ARM usa un move if not equal / move if equals combo (buenas instrucciones). Gracias por el enlace al compilador.

    – John Dvorak

    22 de enero de 2013 a las 8:15


  • Tenga en cuenta que la solución basada en deBrujin se convierte en solo cinco operaciones: MOVZB, IMUL, SAR, AND, MOV

    – John Dvorak

    22 de enero de 2013 a las 8:35

si defines

const char bytes[]={1,2,4,8,16,32,64,128}

y use

struct byte{
char data;
int pos;
}
void assign(struct byte b,int i){

b.data=bytes[i];
b.pos=i
}

no necesita determinar la posición del bit establecido

  • you don't need to determine the position of the set bit — Me gustaría disputar

    – John Dvorak

    20 de enero de 2013 a las 21:56

  • Está luchando contra el problema OPUESTO… dado el valor de encontrar el índice. Escanear su tabla es más o menos como simplemente verificar los bits.

    – 6502

    20 de enero de 2013 a las 22:04

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad