Бит-маска в C

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

 00..0 11..1 00..0 kmn 

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

 01111000 

~ (~ 0 << m) << n

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

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

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

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

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

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

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

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

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

Хотя верхние ответы просты и эффективны, они не устанавливают MSB для случая, когда n=0 и 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‬

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

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

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

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

 mask = _bzhi_u32(-1,m)< 

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

 #include  #include  /* gcc -O3 -Wall -m64 -march=haswell bitmsk_mn.c */ unsigned int bitmsk(unsigned int m, unsigned int n) { return _bzhi_u32(-1,m)< 

Выход:

 $./a.out k= 000FE000 

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

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

Это одна инструкция меньше, чем коды @Jonathan Leffler и @Darius Bacon . На процессорах Intel Haswell или новее, как bzhi и shlx имеют латентность 1 цикл и пропускную способность 2 за цикл. На AMD Ryzen эти две инструкции имеют пропускную способность 4 за цикл.