¿Cómo determinar el número de bits similares?

Question

Necesito comparar dos números y buscar similitudes en bits más significativos. Estoy tratando de determinar la cantidad de bits menos significativos que difieren.

10111000 
10111011 

184 y 187 requieren un desplazamiento de dos, porque solo dos bits menos significativos difieren.

10111011 
11111011 

187 y 251 requieren un desplazamiento de siete, porque el séptimo bit menos significativo es diferente.

Mi primera idea fue XOR los números juntos, luego el bit-shift a la derecha hasta que el número fue igual a cero. Siento que hay una mejor solución bit-wise para esto que no involucra bucles, pero no he hecho suficiente mi propio truco para llegar a eso.

La solución necesita funcionar para cualquier 64 bits, ya que mis números se almacenan como UInt64. Esto se está escribiendo en C#, pero la solución probablemente sea una que no se corresponde con el idioma.

---

11101101 
11010101 

necesitaría un desplazamiento de 6 bits. Estoy tratando de encontrar cuántos bits similares puedo quitar de la parte superior.

Answer 1

#include <stdio.h> 
#include <stdlib.h> 

#define TO_L(s) (strtol((s), NULL, 16)) 

int tsb(unsigned long xa, unsigned long xb) { 
    unsigned long v = xa^xb; 
    static const unsigned long b[] = { 
    0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000L, 0xFFFFffff00000000L 
    }; 
    static const unsigned int S[] = { 1, 2, 4, 8, 16, 32 }; 
    unsigned int r = 0; 

#define STEP(i) \ 
    if(v & b[i]) { \ 
    int t = S[i]; \ 
    v >>= t;  \ 
    r |= t;  \ 
    } 
    STEP(5) 
    STEP(4) 
    STEP(3) 
    STEP(2) 
    STEP(1) 
    STEP(0) 
    return r; 
} 

int main(int ac, char **av) { 
    return printf("%d\n", tsb(TO_L(av[1]), TO_L(av[2]))), 0; 
} 

Creo que esto implementa su algoritmo y es muy rápido, solo necesita 6 pasos. Consulte esto great source of bit twiddling hacks.

so ross$ ./a.out 1f f 
4 
so ross$ ./a.out 471234abcdabcd 981234abcdabcd 
55 
so ross$ ./a.out 1deadbeef 7feedface 
34 

Answer 2

Algo así como

floor(log(184^187)/log(2)) + 1 

Sin bucle, pero podría no haber sido más rápido, porque de registro en una operación costosa. Debería probarlo y compararlo con un simple bucle con cambio de bit.

En ocasiones, un bucle (bien codificado) es más rápido que el cero, especialmente si tiene como máximo 64 iteraciones y, a menudo, menos.

---

versión más eficiente de mi código:

Pre-cálculo

double Ilog2 = 1/log(2); 

y luego cada vez que lo necesitan

floor(log(184^187) * ILog2) + 1 

Answer 3

Suena como ya se ha manchado el truco principal; r = x XOR y, luego encuentra el bit más alto en r. Hay un montón de maneras diferentes de resolver that problem here. Lo más rápido lo hace en O (n) operaciones dividiendo r por la mitad y verificando si la parte superior es cero. Si usted está haciendo esto en un número fijo de bits (que dijiste 64) y luego desenrollar los bucles para obtener una serie de pruebas:

pos = 0 
r = x XOR y 
if r>>32 == 0 : 
    r = r & 2^32-1 
else 
    pos += 32 
    r = r>>32 
if r>>16 == 0 : 
    r = r & 2^16-1 
else 
    pos += 16 
    r = r>16 
... etc 

Answer 4

Puede escribir un O (log (n)) de bucle para encontrar la más alta establecer bit muy fácilmente:

int findHighestSetBit(unsigned long long x) { 
    int rv = 0; 
    if (x == 0) 
     return -1; // no set bits 
    for (int shift = 32; shift > 0; shift >>= 1) { 
     if (x >> shift) { 
      rv += shift; 
      x >>= shift; 
     } 
    } 
    return rv+1; // number least significant bit as '1' rather than '0' 
} 

si esto es demasiado lento, puede desenrollar manualmente el bucle 5 veces.

Answer 5

Supongamos primero que tiene que hacerlo para números de 8 bits. la manera más rápida es una tabla de búsqueda 256 bytes con los valores precompilados:

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed 

unsigned diff = (unsigned)a^(unsigned)b; // sure you need XOR and not MINUS? 
unsigned highest_bit_num = highest_bit_num_LUT[diff & 0xff]; 

ahora extendiéndola para el recuento de bits más altas:

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed 
unsigned diff = (unsigned)a^(unsigned)b; // sure you need XOR and not MINUS? 
unsigned highest_bit_num = 0; 
for (int i = 7; i >= 0; i--)  
    if (diff >> (i*8)){ // found most significant non-zero byte 
     highest_bit_num = i*8 + highest_bit_num_LUT[diff >> (i*8)]; 
     break; 
    } 

así que ahora tenemos en la mayoría de 8 iteraciones.

EDITAR: sería más rápido utilizar la idea de DigitalRoss para las primeras 3 iteraciones, y luego usar la LUT.