mascaras - operadores de bits en c

Máscara de bits en C

Question

¿Cuál es la mejor manera de construir una máscara de bits en C con m conjuntos de bits precedidos por k bits no configurados, y seguidos por n bits no configurados?

00..0 11..1 00..0
  k     m     n

Por ejemplo, k = 1, m = 4, n = 3 daría como resultado la máscara de bits:

01111000

Answer 1

Entonces, ¿está pidiendo m set bits con el prefijo k reset bits y seguido de n reset bits? Podemos ignorar k ya que en gran medida estará restringido por la elección del tipo de entero.

mask = ((1 << m) - 1) << n;

Answer 2

~ (~ 0 << m) << n

Answer 3

Me gustan ambas soluciones. Aquí hay otra forma en que se me ocurre (probablemente no mejor).

((~((unsigned int)0) << k) >> (k + n)) << n

EDITAR: Hubo un error en mi versión anterior (sin el int sin signo). El problema era que ~0 >> n agrega 1s al frente y no 0s.

Y sí, este enfoque tiene una gran desventaja; supone que usted conoce el número de bits del tipo entero predeterminado o, en otras palabras, asume que realmente conoce k, mientras que las otras soluciones son independientes de k. Esto hace que mi versión sea menos portátil, o al menos más difícil de transportar. (También usa 3 turnos, y suma y un operador de negación a nivel de bit, que son dos operaciones adicionales.)

Entonces, sería mejor utilizar uno de los otros ejemplos.

Aquí hay una pequeña aplicación de prueba, hecha por Jonathan Leffler, para comparar y verificar el resultado de las diferentes soluciones:

#include <stdio.h>
#include <limits.h>

enum { ULONG_BITS = (sizeof(unsigned long) * CHAR_BIT) };

static unsigned long set_mask_1(int k, int m, int n)
{
    return ~(~0 << m) << n;
}

static unsigned long set_mask_2(int k, int m, int n)
{
    return ((1 << m) - 1) << n;
}

static unsigned long set_mask_3(int k, int m, int n)
{
    return ((~((unsigned long)0) << k) >> (k + n)) << n;
}

static int test_cases[][2] =
{
    { 1, 0 },
    { 1, 1 },
    { 1, 2 },
    { 1, 3 },
    { 2, 1 },
    { 2, 2 },
    { 2, 3 },
    { 3, 4 },
    { 3, 5 },
};

int main(void)
{
    size_t i;
    for (i = 0; i < 9; i++)
    {
        int m = test_cases[i][0];
        int n = test_cases[i][1];
        int k = ULONG_BITS - (m + n);
        printf("%d/%d/%d = 0x%08lX = 0x%08lX = 0x%08lX/n", k, m, n,
               set_mask_1(k, m, n),
               set_mask_2(k, m, n),
               set_mask_3(k, m, n));
    }
    return 0;
}

Answer 4

Si bien las respuestas principales son simples y efectivas, no configuran el MSB para el caso cuando n=0 y m=31 :

~(~0 << 31) << 0 = 0111 0111 1111 1111 1111 1111 1111 1111 1111‬

((1 << 31)-1) << 0 = 0111 0111 1111 1111 1111 1111 1111 1111 1111‬

Mi sugerencia para una palabra sin firmar de 32 bits (que es fea y tiene una rama) es así:

unsigned int create_mask(unsigned int n,unsigned int m) {
  // 0 <= start_bit, end_bit <= 31
  return (m - n == 31 ? 0xFFFFFFFF : ((1 << (m-n)+1)-1) << n);
}

Esto realmente obtiene los bits en el rango [m,n] (intervalo cerrado) así que create_mask(0,0) devolverá una máscara para el primer bit (bit 0) y create_mask(4,6) devuelve una máscara para los bits 4 a 6 ie ... 00111 0000 .

Answer 5

(Solo) Para aquellos que estén interesados ​​en una solución un poco más eficiente en sistemas x86 con soporte BMI2 (Intel Haswell o más reciente, AMD Excavator o más reciente):

mask = _bzhi_u32(-1,m)<<n;

La instrucción bzhi cero los bits altos comenzando con la posición de bit especificada. El _bzhi_u32 compila intrínsecamente a esta instrucción. Código de prueba:

#include <stdio.h>
#include <x86intrin.h>
/*  gcc -O3 -Wall -m64 -march=haswell bitmsk_mn.c   */

unsigned int bitmsk(unsigned int m, unsigned int n)
{
    return _bzhi_u32(-1,m)<<n;
}

int main() {
    int k = bitmsk(7,13);
    printf("k= %08X/n",k);
    return 0;
}

Salida:

$./a.out
k= 000FE000

El fragmento de código _bzhi_u32(-1,m)<<n compila a tres instrucciones

movl    $-1, %edx
bzhi    %edi, %edx, %edi
shlx    %esi, %edi, %eax

Que es una instrucción menos que los códigos de @Jonathan Leffler y @Darius Bacon . En los procesadores Intel Haswell o más nuevos, tanto bzhi como shlx tienen una latencia de 1 ciclo y un rendimiento de 2 por ciclo. En AMD Ryzen estas dos instrucciones incluso tienen un rendimiento de 4 por ciclo.