Bit twiddling para comprobar si un número está en el rango particular

Encontré un poco interesante jugando en el archivo "source\common\unicode\utf.h" de la biblioteca de ICU (Componentes internacionales para Unicode). El bit twiddling estaba destinado a verificar si un número se encuentra en un rango particular.Bit twiddling para comprobar si un número está en el rango particular

// Is a code point in a range of U+d800..U+dbff? 
#define U_IS_LEAD(c) (((c)&0xfffffc00)==0xd800)

he descubierto el número mágico (0xfffffc00) provienen de:

MagicNumber = 0xffffffff - (HighBound - LowBound)

Sin embargo, también me encontré con que la fórmula no se aplica a cada rango arbitrario. ¿Alguien sabe aquí en qué circunstancias funciona la fórmula?

¿Hay algún otro truco para comprobar si un número está en un rango determinado?

Fuente

2011-01-01 Astaroth

Para que se apliquen estos trucos, los números deben tener algunas características comunes en su representación binaria.

0xD800 == 0b1101_1000_0000_0000 
0xDBFF == 0b1101_1011_1111_1111

Lo que realmente hace esta prueba es enmascarar los diez bits más bajos. Esto generalmente se escribe como

onlyHighBits = x & ~0x03FF

Después de esta operación ("y no") los más bajos diez bits de onlyHighBits se garantiza que sea cero. Eso significa que si este número es igual al rango inferior del intervalo ahora, ha estado en algún lugar en el intervalo anterior.

Este truco funciona en todos los casos donde el límite inferior y superior del intervalo comienzan con los mismos dígitos en binario, y en algún punto el límite inferior tiene solo ceros mientras que el límite superior tiene solo unos. En su ejemplo, esta es la décima posición desde la derecha.

Fuente

2011-01-01 10:34:33

¿Puede proporcionar alguna referencia para "usualmente escrito como"?Personalmente encuentro 'a & ~ b' en lugar de' a & ~ b' menos intuitivo y 'a & b == c' más intuitivo que' a & ~ d == e' porque hay menos operaciones, incluso si es solo mi preferencia personal –

Tenga en cuenta que 'a & b == c' no significa lo que probablemente crea que significa (significa' a & (b == c) '). 'a & ~ b' es léxicamente idéntica a' a & ~ b', y estoy de acuerdo en que la última es una mejor transcripción de la misma, aunque solo sea porque así se hace habitualmente. –

La fórmula funciona siempre que el rango que está buscando comienza en un múltiplo de una potencia de 2 (es decir, 1 o más bits en el extremo inferior de la forma binaria del número termina en 0) y el tamaño de el rango es 2^n-1 (es decir, bajo & alto == bajo y bajo | alto == alto).

Fuente

2011-01-01 10:36:16 Vatine

lo has probado? Suponiendo que el número es '9' y el rango es' 8..8 + (2^14-1) ', la fórmula no se aplica a este caso. – Astaroth

Bueno ... El N no debe ser mayor que el número de 0 al final del número de base (entonces para 8, N podría estar en el rango de 1-3). Pensé que era demasiado obvio para mencionar. – Vatine

Si usted no tiene 2^x límites tipo podría utilizar el siguiente truco:

si x >= 0 y x < N se puede comprobar tanto por:

if Longword(x) < Longword(N) then ...

Esto funciona debido al hecho de que los números negativos en números con signo corresponden a los números más grandes en tipos de datos sin signo.

Se podría extender este (cuando la verificación del rango está desactivado) a:

if Longword(x - A) < Longword ((B - A)) then ...

Ahora se han ambas pruebas (rango [ A, B >) en un SUB y una CMP más una sola Jcc, suponiendo que (B - A) es precalculado

Solo uso este tipo de optimizaciones cuando realmente es necesario; por ejemplo, tienden a hacer que su código sea menos legible y solo reduce algunos ciclos de reloj por prueba.

Nota para los lectores de lenguaje similar a C: Longword es el tipo de datos de 32 bits sin signo de Delphi.

Fuente

2011-01-01 16:30:37

Gracias @Ritsaert, +1 de mí. – Astaroth

Bit twiddling para comprobar si un número está en el rango particular

Respuesta

Cuestiones relacionadas