algorithm - operadores - Algoritmo para generar máscara de bits
operadores de bits en c (6)
Me enfrentaba a 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)
Esto lo implementé usando un for-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 algoritmo mejor ~~~
Implementación eficiente, sin sucursales, portátil y genérica (pero fea)
DO:
#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 (producir constantes de tiempo de compilación)
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 explicó en otras respuestas, se usa << en lugar de << para evitar el problema cuando el conteo de turnos es igual al número de bits del tipo de almacenamiento del valor. (Gracias a la respuesta de Julien por la idea)
Para facilitar la discusión, vamos a "crear una instancia" de la macro con unsigned int como __TYPE__ y ver qué sucede (asumiendo 32 bits por el momento):
((unsigned int) (-((__ONE_COUNT__) != 0))) /
& (((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))
Centrémonos en:
((sizeof(unsigned int) * CHAR_BIT)
primero. Se conoce sizeof(unsigned int) en tiempo de compilación. Es igual a 4 según nuestro supuesto. CHAR_BIT representa el número de bits por char , también conocido 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. Dado que esta expresión se conoce en tiempo de compilación, el compilador probablemente haría la multiplicación en tiempo de compilación y la trataría como una constante, lo que equivale a 32 en este caso.
Vayamos a:
((unsigned int) -1)
Es igual a 0xFFFFFFFF . La conversión de -1 a cualquier tipo sin signo produce un valor de "all-1s" en ese tipo. Esta parte es también 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 lo mismo que la respuesta de Julien arriba. 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. (Por eso __ONE_COUNT__ mi parámetro como __ONE_COUNT__ para enfatizar su intención)
Para resolver este problema, simplemente podríamos agregar un caso especial para __ONE_COUNT igual a 0 usando if-else o ?: , Como esto:
#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 mejor, ¿no? Vayamos 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 contrario. (-((__ONE_COUNT__) != 0)) produce 0 cuando el parámetro es 0 , o -1 contrario. Para ((unsigned int) (-((__ONE_COUNT__) != 0))) , el truco de ((unsigned int) (-((__ONE_COUNT__) != 0))) tipos ((unsigned int) -1) ya se explicó anteriormente. ¿Te das cuenta el truco ahora? La expresion:
((__TYPE__) (-((__ONE_COUNT__) != 0)))
es igual a "all-0s" si __ONE_COUNT__ es cero, y "all-1s" en caso contrario. Actúa como una máscara de bits para el valor que calculamos en el primer paso. Entonces, si __ONE_COUNT__ no es cero, la máscara no tiene efecto y es la misma que la respuesta de Julien. Si __ONE_COUNT__ es 0 , __ONE_COUNT__ todos los bits de la respuesta de Julien, produciendo un cero constante. Para visualizar, mira 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
¿Qué tal esto (en Java):
int mask = -1;
mask = mask << param;
mask = ~mask;
De esta manera, puede evitar las tablas de búsqueda y la codificación de la longitud de un entero.
Explicación: Un entero con signo con un valor de -1 se representa en binario como todos. Mueve a la izquierda el número dado de veces para agregar tantos 0 al lado derecho. Esto dará lugar a una especie de "máscara inversa". Luego niega el resultado cambiado para crear tu 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
Alternativamente, 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);
asumiendo que param <= 32 , por supuesto.
Para aquellos interesados, esta es la alternativa de la tabla de consulta que se comenta en los comentarios a la otra respuesta, la diferencia es que funciona correctamente para un parámetro de 32. Es bastante fácil extenderse a la versión unsigned long long 64 bits, si lo necesita. , y no debería ser significativamente diferente en velocidad (si se llama en un bucle interno estrecho, la tabla estática permanecerá en al menos el caché L2, y si no se llama en un bucle interno estrecho, la diferencia de rendimiento no será 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 instrucción if() (porque le preocupa que alguien pueda llamarla con param > 32 ), esto no le hace ganar 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 la última versión tiene un caso especial param >= 32 , mientras que la primera solo tiene un caso especial param > 32 .
Si está preocupado por el desbordamiento en un lenguaje similar a C con (1 << param) - 1 (cuando param es 32 o 64 en el tamaño de tamaño máximo, la máscara se convierte en 0 debido a que BitShift supera los límites del tipo), una solución Acabo de pensar en:
const uint32_t mask = ( 1ul << ( maxBits - 1ul ) ) | ( ( 1ul << ( maxBits - 1ul ) ) - 1ul );
U otro ejemplo
const uint64_t mask = ( 1ull << ( maxBits - 1ull ) ) | ( ( 1ull << ( maxBits - 1ull ) ) - 1ull );
Aquí hay una versión con plantilla, tenga en cuenta que debe usar esto con un tipo R sin firma:
#include <limits.h> /* CHAR_BIT */
// bits cannot be 0
template <typename R>
static constexpr R bitmask1( const R bits )
{
const R one = 1;
assert( bits >= one );
assert( bits <= sizeof( R ) * CHAR_BIT );
const R bitShift = one << ( bits - one );
return bitShift | ( bitShift - one );
}
Digamos que max bits es 8 con un byte, con la primera función de desbordamiento tendríamos 1 << 8 == 256 , que cuando se convierte en byte se convierte en 0. Con mi función tenemos 1 << 7 == 128 , que El byte puede contener, por lo que se convierte en 1<<7 | 1<<7 - 1 1<<7 | 1<<7 - 1 .
No he compilado la función, por lo que puede contener errores tipográficos.
Y por diversión aquí está la carne de Julien Royer :
// bits can be 0
template <typename R>
static constexpr R bitmask2( const R bits )
{
const R zero = 0;
const R mask = ~zero;
const R maxBits = sizeof( R ) * CHAR_BIT;
assert( bits <= maxBits );
return mask >> ( maxBits - bits );
}
Una cosa a tener en cuenta acerca de las máscaras de bits es que siempre son una menos de una potencia de dos.
La expresión "1 << n" es la manera fácil de obtener el n-ésimo poder de dos.
No desea que Zero proporcione una máscara de bits de "00000001", desea que proporcione cero. Así que 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 enteros de 16, 32 o 64 bits, pero es posible que tenga que escribir explícitamente el ''1''.