Битовая маска в C
Как лучше всего построить битовую маску в C с установленными битами m, которым предшествуют неустановленные биты k, а за ними следуют неустановленные биты n:
00..0 11..1 00..0
k m n
Например, k = 1, m = 4, n = 3 приведет к битовой маске:
01111000
Обычно макросы битовой маски определяются на битовых индексах инклюзивный, что-то вроде #define BITS(p,q) ..., где p = m + n - 1 и q = n, p> = q
@grigy Я не совсем понимаю, зачем тебе здесь k. Просто проще указать диапазон битов для установки, используя только m и n.
Ответы 5
~ (~ 0 << м) << п
Это здорово. Однако было бы неплохо прокомментировать эту строку, чтобы программист -next- поработал над ней.
Если бы это было закодировано как функция (функции set_mask_n в ответе @quinmar), был бы однострочный комментарий, говорящий о том, что функция делает (без аргумента 'k'), и пользователи функции будут иметь имя как документация. В качестве случайного выражения в небольшом фрагменте кода это, несомненно, было бы ПЛОХО!
И я бы поспешил (очень медленно) добавить, что мое решение было бы столь же непостижимым, если бы оно появилось как раскомментированное выражение в небольшом фрагменте кода.
~(~0 << m) находится в параграфе 2.9 «Побитовые операторы» книги «Язык программирования C, второе издание» Брайана Кернигана и Денниса Ричи. Это также есть в параграфе 7.5 «Эффективное использование пространства» «Практики программирования» Брайана В. Кернигана и Роба Пайка.
Этот подход не могу создает маску, включающую самый верхний бит из самый длинный беззнаковый целочисленный тип, то есть обычно указывается предупреждением, подобным integer overflow in preprocessor expression.
@Barry, у меня проблемы с пониманием проблемы, несомненно, потому что прошло много лет с тех пор, как я смотрел на стандарт (и более старый при этом). С gcc -Wall --ansi --pedantic на "~ (~ 0 << 1) << 31" я не получаю такого предупреждения (и получаю другое при увеличении 31 до 32, так что это тест с 32 -битовые числа).
@DariusBacon Я обнаружил, что ответ ниже заставляет gcc жаловаться на переполнение целых чисел, т.е. printf("%u\n", ((1 << 31) - 1) << 0); генерирует warning: integer overflow in expression [-Woverflow]. Я также согласен с Барри в том, что битовая маска не устанавливает MSB целого числа без знака. Есть ли способ обойти это?
Это должен быть ~(~0u << m) << n.
Итак, вы просите установить m битов с префиксом k битов сброса и последующими n битами сброса? Мы можем игнорировать k, поскольку он будет в значительной степени ограничен выбором целочисленного типа.
mask = ((1 << m) - 1) << n;
Они оба работают, но я считаю, что ответ Джонатана проще и яснее. Мне кажется, что ответ Дария несколько отстает.
Роберт, мне нравится идиома ~ 0 для битовых масок, потому что она не зависит от дополнения до 2 и в этом смысле проще, но правда менее известна. Просто делаю свой вклад, чтобы это изменить!
@Darius: если вы используете беззнаковую арифметику / типы, как и следовало бы в этих контекстах, разве разница между дополнением до 2, дополнением до единицы и арифметикой с величиной знака несущественна?
@Darius, вы не должны в первую очередь выполнять побитовую арифметику для подписанных типов, и если бы вы это сделали, ваше решение каждый раз вызывает неопределенное поведение!
Это не определено? У меня нет спецификации, но я думаю, что это определено реализацией, то есть компилятору разрешено делать это так, как он хочет, но он всегда должен делать это одинаково. Поэтому, когда вы знаете, как работает (ваш компилятор), вы можете положиться на него.
C99 §6.5.7p4: «Результат E1 << E2 - E1 сдвинутые влево позиции битов E2; [...] Если E1 имеет знаковый тип и неотрицательное значение, а E1 * 2 ^ E2 может быть представлен в типе результата , то это результирующее значение; в противном случае поведение не определено ".
Я ошибался, говоря, что 2-х дополнение. Собственно, что проще, так это то, что код ~ 0 использует только сдвиги и индивидуально-битовые операции, а не арифметику в зависимости от деталей представления чисел. Это естественно для того, для чего нужны битовые маски. По общему признанию, не стоит никого запутывать.
(продолжение) Итак, (1 << m) -1 кажется более удивительным, если подойти к нему свежим взглядом, чего мы обычно не делаем.
@Darius: возможно, ваш лучший снимок: если целые числа 32-битные и m = 32, то поведение моего выражения не определено (6.5.7, пункт 3 в C99). И я не думаю, что смогу опровергнуть это утверждение.
@Darius: продолжаю - впрочем, тот же аргумент может быть использован против вашего ... да ладно. Это как никогда близко к ничьей. Поздравляю, вы попали туда первым.
Думаю, твой может быть немного быстрее, Джонатан. (Не тестировал.) Честно говоря, я не фанат великих ~ 0, потому что забавно, как самые мелкие вещи запускают самые длинные потоки.
@Darius: подсчет основных операций: в обоих решениях две смены на одинаковые суммы; у вас одна активная операция '~', а у меня одна операция '-' (конечно, компилятор оценивает '~ 0'). Оба выражения должны иметь одинаковую скорость.
Да, у меня были две умозрительные причины: ~ 0 - более дорогая константа, чем 1 в архитектуре без операции постоянной загрузки с расширенным знаком, и компилятор, который по какой-то причине может воспользоваться преимуществом распознавания этой идиомы, с большей вероятностью будет ищите более известного (вашего).
Мне нравятся оба решения. Вот еще один способ, который мне приходит в голову (вероятно, не лучше).
((~((unsigned int)0) << k) >> (k + n)) << n
Обновлено:
В моей предыдущей версии была ошибка (без приведения типа unsigned int). Проблема заключалась в том, что ~0 >> n добавляет впереди единицы, а не нули.
И да, у этого подхода есть один большой недостаток; он предполагает, что вам известно количество бит целочисленного типа по умолчанию, или, другими словами, предполагается, что вы действительно знаете 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;
}
Если исходить из предположения, что этот ответ может работать, очевидным недостатком по сравнению с двумя другими является наличие операции третьей смены, которая требует больше времени.
Другая проблема заключается в том, что он использует параметр k, который два других решения могут игнорировать (хотя он не использует m, поэтому по-прежнему использует только два из трех параметров).
Прямо в нем была ошибка, я исправил ее сейчас и добавил комментарий, что другие решения предпочтительнее. Я не удалил его полностью, может быть, кто-то сможет поучиться на моих ошибках, и было бы грустно потерять ваш хороший тестовый код :).
Вместо приведения вы должны иметь возможность использовать «0U» для обозначения беззнакового нуля или «0UL» для обозначения беззнакового длинного числа. Я согласен оставить ваш ответ на месте - и с внесенными вами изменениями.
Сделайте это макросом или встроенной функцией, компилятор будет генерировать константу во время компиляции вместо кода.
@Barry, компилятор может «встроить» статическую функцию, и я уверен, что в данном случае все современные компиляторы будут это делать.
Хотя основные ответы просты и эффективны, они не устанавливают 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, то есть ... 00111 0000.
(Только) Для тех, кто интересуется чуть более эффективным решением на системах 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 за цикл.
Для ответов на многие хитрости, подобные этому, очень хороший онлайн-источник - Bit Twiddling Хаки.