Битовая маска в C

Question

Каков наилучший способ создать битовую маску в C с m установленными битами, перед которыми стоит k неустановленные биты, а затем n неустановленные биты:

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

Например, k = 1, m = 4, n = 3 приведут к битовой маске:

01111000

Answer 1

~ (~ 0 << м) << n </p>

Answer 2

Итак, вы запрашиваете m установленных битов с префиксом k битов сброса, а затем n битов сброса? Мы можем игнорировать k, так как он будет в значительной степени ограничен выбором целочисленного типа.

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

Answer 3

Мне нравятся оба решения. Вот еще один способ, который приходит мне в голову (вероятно, не лучше).

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

EDIT: В моей предыдущей версии была ошибка (она была без неподписанного типа int). Проблема заключалась в том, что ~0 >> n добавляет 1 с перед, а не 0.

И да, у этого подхода есть один большой недостаток; он предполагает, что вы знаете число бит целочисленного типа по умолчанию, или другими словами, он предполагает, что вы действительно знаете k, тогда как другие решения не зависят от k. Это делает мою версию менее переносимой или, по крайней мере, труднее переносить. (Также используются 3 смены, оператор сложения и побитового отрицания, что является двумя дополнительными операциями.)

Так что вам лучше использовать один из других примеров.

Вот небольшое тестовое приложение, созданное Джонатаном Леффлером для сравнения и проверки результатов различных решений:

#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

(только) Для тех, кто заинтересован в чуть более эффективном решении для систем x86 с поддержкой BMI2 (Intel Haswell или новее, AMD Excavator или новее):

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

Инструкция bzhi обнуляет старшие биты, начиная с указанной битовой позиции. Встроенный _bzhi_u32 компилируется в эту инструкцию. Тестовый код:

#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;
}

Выход:

$./a.out
k= 000FE000

Фрагмент кода _bzhi_u32(-1,m)<<n компилируется в три инструкции

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

Что на одну инструкцию меньше, чем коды @ Джонатан Леффлер и @ Дарий Бэкон . На процессорах Intel Haswell или более новых версиях bzhi и shlx имеют задержку 1 цикл и пропускная способность 2 за цикл. На AMD Ryzen эти две инструкции даже имеют пропускную способность 4 за цикл.

Answer 5

Хотя верхние ответы просты и эффективны, они не устанавливают MSB для случая, когда n=0 и m=31:

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

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

Мое предложение для 32-битного беззнакового слова (которое некрасиво и имеет ветку) выглядит так:

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);
}

Это фактически получает биты в диапазоне [m,n] (закрытый интервал), поэтому create_mask(0,0) возвращает маску для первого бита (бит 0), а create_mask(4,6) возвращает маску для битов 4-6, т.е. .