Algoritmo para generar la máscara de bits

Question

Estaba enfrentando este problema único de generar una máscara de bits basada en el parámetro de entrada. Por ejemplo,

si PARAM = 2, entonces la máscara será 0x3 (11b) si PARAM = 5, entonces la máscara será 0x1F (1 1111b)

Esta He implementado usando un para-loop en C, algo así como

int nMask = 0; 
for (int i = 0; i < param; i ++) { 

    nMask |= (1 << i); 
} 

me gustaría saber si hay un mejor algoritmo ~~~

Answer 1

una cosa a notar acerca de máscaras de bits así es que son siempre uno menos que una potencia de dos.

La expresión "1 < < n" es la manera fácil de obtener la potencia n-ésima de dos.

No desea que Zero proporcione una máscara de bits de "00000001", quiere que proporcione cero. Entonces necesitas restar uno.

mask = (1 << param) - 1; 

Editar:

Si quieres un caso especial para param> 32:

int sizeInBits = sizeof(mask) * BITS_PER_BYTE; // BITS_PER_BYTE = 8; 
mask = (param >= sizeInBits ? -1 : (1 << param) - 1); 

Este método debería funcionar para 16, 32 ó 64 bits enteros, pero puede tiene que escribir explícitamente el '1'.

Answer 2

Para los interesados, esta es la alternativa de la tabla de búsqueda discutida en los comentarios a la otra respuesta, la diferencia es que funciona correctamente para un param de 32. Es bastante fácil extenderse a la versión de unsigned long long de 64 bits, si necesita eso, y no debe ser significativamente diferente en velocidad (si se llama en un bucle interno cerrado entonces la tabla estática permanecerá en al menos caché L2, y si es no llamado en un bucle interno cerrado entonces la diferencia de rendimiento ganó no sea importante).

unsigned long mask2(unsigned param) 
{ 
    static const unsigned long masks[] = { 
     0x00000000UL, 0x00000001UL, 0x00000003UL, 0x00000007UL, 
     0x0000000fUL, 0x0000001fUL, 0x0000003fUL, 0x0000007fUL, 
     0x000000ffUL, 0x000001ffUL, 0x000003ffUL, 0x000007ffUL, 
     0x00000fffUL, 0x00001fffUL, 0x00003fffUL, 0x00007fffUL, 
     0x0000ffffUL, 0x0001ffffUL, 0x0003ffffUL, 0x0007ffffUL, 
     0x000fffffUL, 0x001fffffUL, 0x003fffffUL, 0x007fffffUL, 
     0x00ffffffUL, 0x01ffffffUL, 0x03ffffffUL, 0x07ffffffUL, 
     0x0fffffffUL, 0x1fffffffUL, 0x3fffffffUL, 0x7fffffffUL, 
     0xffffffffUL }; 

    if (param < (sizeof masks/sizeof masks[0])) 
     return masks[param]; 
    else 
     return 0xffffffffUL; /* Or whatever else you want to do in this error case */ 
} 

Vale la pena señalar que si necesita la declaración if() (porque están preocupados de que alguien podría llamar con param > 32), entonces esto no se gana nada sobre la alternativa de la otra respuesta:

unsigned long mask(unsigned param) 
{ 
    if (param < 32) 
     return (1UL << param) - 1; 
    else 
     return -1; 
} 

La única diferencia es que esta última versión tiene un caso especial param >= 32, mientras que la primera solo tiene que ser un caso especial param > 32.

Answer 3

Como alternativa, puede usar un cambio a la derecha para evitar el problema mencionado en la solución (1 << param) - 1.

unsigned long const mask = 0xffffffffUL >> (32 - param); 

suponiendo que param <= 32, por supuesto.

Answer 4

eficiente, Rama-Libre, portátil y genérico (pero feo) Implementación

C:

#include <limits.h>  /* CHAR_BIT */ 

#define BIT_MASK(__TYPE__, __ONE_COUNT__) \ 
    ((__TYPE__) (-((__ONE_COUNT__) != 0))) \ 
    & (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__))) 

C++:

#include <climits> 

template <typename R> 
static constexpr R bitmask(unsigned int const onecount) 
{ 
// return (onecount != 0) 
//  ? (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount)) 
//  : 0; 
    return static_cast<R>(-(onecount != 0)) 
     & (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount)); 
} 

Uso (produciendo Tiempo de Compilación Constantes)

BIT_MASK(unsigned int, 4) /* = 0x0000000f */ 

BIT_MASK(uint64_t, 26) /* = 0x0000000003ffffffULL */ 

Ejemplo

#include <stdio.h> 

int main() 
{ 
    unsigned int param; 
    for (param = 0; param <= 32; ++param) 
    { 
     printf("%u => 0x%08x\n", param, BIT_MASK(unsigned int, param)); 
    } 
    return 0; 
} 

salida

0 => 0x00000000 
1 => 0x00000001 
2 => 0x00000003 
3 => 0x00000007 
4 => 0x0000000f 
5 => 0x0000001f 
6 => 0x0000003f 
7 => 0x0000007f 
8 => 0x000000ff 
9 => 0x000001ff 
10 => 0x000003ff 
11 => 0x000007ff 
12 => 0x00000fff 
13 => 0x00001fff 
14 => 0x00003fff 
15 => 0x00007fff 
16 => 0x0000ffff 
17 => 0x0001ffff 
18 => 0x0003ffff 
19 => 0x0007ffff 
20 => 0x000fffff 
21 => 0x001fffff 
22 => 0x003fffff 
23 => 0x007fffff 
24 => 0x00ffffff 
25 => 0x01ffffff 
26 => 0x03ffffff 
27 => 0x07ffffff 
28 => 0x0fffffff 
29 => 0x1fffffff 
30 => 0x3fffffff 
31 => 0x7fffffff 
32 => 0xffffffff 

Explicación

En primer lugar, como ya se ha discutido en otras respuestas, >> se utiliza en lugar de << el fin de evitar el problema cuando el valor de desplazamiento es igual a la cantidad de bits del tipo de almacenamiento del valor. (Gracias Julien's answer above de la idea)

Para facilitar la discusión, vamos a "instanciar" la macro con unsigned int como __TYPE__ y ver qué pasa (suponiendo 32 bits por el momento):

((unsigned int) (-((__ONE_COUNT__) != 0))) \ 
& (((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__))) 

enfoque de Let en:

((sizeof(unsigned int) * CHAR_BIT) 

primero. sizeof(unsigned int) es conocido en tiempo de compilación. Es igual a 4 de acuerdo con nuestra suposición. CHAR_BIT representa el número de bits por char, a.k.a. por byte. También es conocido en tiempo de compilación. Es igual a 8 en la mayoría de las máquinas en la Tierra. Como esta expresión se conoce en un tiempo de compilación, el compilador probablemente haga la multiplicación en tiempo de compilación y la trate como una constante, que es igual a 32 en este caso. movimiento

Vamos a:

((unsigned int) -1) 

Es igual a 0xFFFFFFFF. Casting -1 a cualquier tipo sin signo produce un valor de "all-1s" en ese tipo. Esta parte también es una constante de tiempo de compilación.

Hasta ahora, la expresión:

(((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__))) 

es, de hecho, lo mismo que:

0xffffffffUL >> (32 - param) 

que es la misma que la respuesta de Julien anteriormente. Un problema con su respuesta es que si param es igual a 0, produciendo la expresión 0xffffffffUL >> 32, el resultado de la expresión sería 0xffffffffUL, en lugar del 0 esperado.(Es por eso que el nombre de mi parámetro como __ONE_COUNT__ hacer hincapié en su intención)

Para resolver este problema, podríamos agregar simplemente un caso especial para __ONE_COUNT es igual a 0 usando if-else o ?:, así:

#define BIT_MASK(__TYPE__, __ONE_COUNT__) \ 
    (((__ONE_COUNT__) != 0) \ 
    ? (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__))) 
    : 0) 

Pero el código sin sucursales es más genial, ¿no? Pasemos a la siguiente parte:

((unsigned int) (-((__ONE_COUNT__) != 0))) 

Comencemos desde la expresión más interna hasta la más externa. ((__ONE_COUNT__) != 0) produce 0 cuando el parámetro es 0, o 1 de lo contrario. (-((__ONE_COUNT__) != 0)) produce 0 cuando el parámetro es 0, o -1 en caso contrario. Para ((unsigned int) (-((__ONE_COUNT__) != 0))), el truco de conversión de tipo ((unsigned int) -1) ya se explicó anteriormente. ¿Notaste el truco ahora? La expresión:

((__TYPE__) (-((__ONE_COUNT__) != 0))) 

es igual a "todos 0" si __ONE_COUNT__ es cero, y "todos 1" en caso contrario. Actúa como una máscara de bits para el valor que calculamos en el primer paso. Por lo tanto, si __ONE_COUNT__ es distinto de cero, la máscara no tiene efecto y es igual a la respuesta de Julien. Si __ONE_COUNT__ es 0, enmascara todos los bits de la respuesta de Julien, produciendo un cero constante. Para visualizar, ver esto:

__ONE_COUNT__ :       0    Other 
              ------------- -------------- 
(__ONE_COUNT__)       0 = 0x000...0 (itself) 
((__ONE_COUNT__) != 0)     0 = 0x000...0  1 = 0x000...1 
((__TYPE__) (-((__ONE_COUNT__) != 0))) 0 = 0x000...0 -1 = 0xFFF...F 

Answer 5

¿Qué tal esto (en Java):

int mask = -1; 
mask = mask << param; 
mask = ~mask; 

De esta manera se pueden evitar las tablas de búsqueda y dura de codificación de la longitud de un número entero.

Explicación: Un entero con signo con un valor de -1 se representa en binario como todos. Shift se fue la cantidad de veces dada para agregar tantos 0's al lado derecho. Esto dará como resultado una "máscara inversa" de géneros. Luego niegue el resultado desplazado para crear su máscara.

Esto podría reducirse a:

int mask = ~(-1<<param); 

Un ejemplo:

int param = 5; 
int mask = -1;  // 11111111 (shortened for example) 
mask = mask << param; // 11100000 
mask = ~mask;   // 00011111