Я столкнулся с этой уникальной проблемой создания битовой маски на основе входного параметра. Например,
если param = 2, тогда маска будет 0x3 (11b) если param = 5, то маска будет 0x1F (1 1111b)
Это я реализовал с помощью цикла for в C, что-то вроде
int nMask = 0;
for (int i = 0; i < param; i ++) {
nMask |= (1 << i);
}
Я хотел бы знать, есть ли лучший алгоритм ~~~
Что касается таких битовых масок, следует отметить, что они всегда на единицу меньше, чем степень двух.
Выражение 1 << n - это самый простой способ получить n-ю степень от двух.
Вы не хотите, чтобы Zero предоставлял битовую маску 00000001, вы хотите, чтобы она предоставляла ноль. Поэтому вам нужно вычесть один.
mask = (1 << param) - 1;
Edit:
Если вы хотите специальный случай для параметра> 32:
int sizeInBits = sizeof(mask) * BITS_PER_BYTE; // BITS_PER_BYTE = 8;
mask = (param >= sizeInBits ? -1 : (1 << param) - 1);
Этот метод должен работать для 16, 32 или 64-битных целых чисел, но вам, возможно, придется явно ввести "1".
С
#include <limits.h> /* CHAR_BIT */
#define BIT_MASK(__TYPE__, __ONE_COUNT__) \
((__TYPE__) (-((__ONE_COUNT__) != 0))) \
& (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__)))
С++:
#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));
}
BIT_MASK(unsigned int, 4) /* = 0x0000000f */
BIT_MASK(uint64_t, 26) /* = 0x0000000003ffffffULL */
#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;
}
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
Прежде всего, как уже обсуждалось в других ответах, вместо << используется >>, чтобы предотвратить проблему, когда количество сдвигов равно числу бит типа хранения значения. (Спасибо Жюльен ответил выше за идею)
Для удобства обсуждения давайте "создадим экземпляр" макроса с unsigned int как __TYPE__ и посмотрим, что произойдет (предположим, что на данный момент 32 бит):
((unsigned int) (-((__ONE_COUNT__) != 0))) \
& (((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))
Сфокусируйтесь на:
((sizeof(unsigned int) * CHAR_BIT)
первый. sizeof(unsigned int) известен во время компиляции. Он равен 4 согласно нашему предположению. CHAR_BIT представляет количество бит на char, a.k.a. за байт. Это также известно во время компиляции. Он равен 8 для большинства машин на Земле. Поскольку это выражение известно во время компиляции, компилятор, вероятно, будет выполнять умножение во время компиляции и рассматривать его как константу, которая в этом случае равна 32.
Переместить в:
((unsigned int) -1)
Он равен 0xFFFFFFFF. Кастинг -1 любому беззнаковому типу производит значение "all-1s" в этом типе. Эта часть также является постоянной времени компиляции.
До сих пор выражение:
(((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))
на самом деле то же самое, что:
0xffffffffUL >> (32 - param)
что является таким же, как ответ Жюльена выше. Одна из проблем с его ответом состоит в том, что если param равно 0, вызывая выражение 0xffffffffUL >> 32, результат выражения будет 0xffffffffUL вместо ожидаемого 0! (Вот почему я называю свой параметр как __ONE_COUNT__, чтобы подчеркнуть его намерение)
Чтобы решить эту проблему, мы могли бы просто добавить специальный случай для __ONE_COUNT equals 0 с помощью if-else или ?:, например:
#define BIT_MASK(__TYPE__, __ONE_COUNT__) \
(((__ONE_COUNT__) != 0) \
? (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__)))
: 0)
Но безрежимный код более холодный, не так ли?! Перейдите к следующей части:
((unsigned int) (-((__ONE_COUNT__) != 0)))
Пусть начнется от самого внутреннего выражения до самого внешнего. ((__ONE_COUNT__) != 0) создает 0, когда параметр 0 или 1 в противном случае. (-((__ONE_COUNT__) != 0)) создает 0, когда параметр 0 или -1 в противном случае. Для ((unsigned int) (-((__ONE_COUNT__) != 0))) трюк типа ((unsigned int) -1) уже описан выше. Вы заметили трюк сейчас? Выражение:
((__TYPE__) (-((__ONE_COUNT__) != 0)))
равно "all-0s", если __ONE_COUNT__ равно нулю, а "all-1s" - в противном случае. Он действует как битовая маска для значения, которое мы вычислили на первом этапе. Итак, если __ONE_COUNT__ отличен от нуля, маска как эффект не действует, и это то же самое, что и Жюльен. Если __ONE_COUNT__ 0, он маскирует все биты ответа Жюльена, создавая постоянный нуль. Чтобы визуализировать, смотрите это:
__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
В качестве альтернативы вы можете использовать сдвиг вправо, чтобы избежать проблемы, упомянутой в решении (1 << param) - 1.
unsigned long const mask = 0xffffffffUL >> (32 - param);
предполагая, что param <= 32, конечно.
Для тех, кого это интересует, это альтернатива таблицы поиска, обсуждаемая в комментариях к другому ответу - разница в том, что она корректно работает для параметра 32. Это достаточно просто, чтобы перейти к 64-битной версии unsigned long long, если вам это нужно и не должно быть значительно отличающимся по скорости (если он вызвал в узком внутреннем цикле, тогда статическая таблица останется в кэше по крайней мере L2, и если он не будет вызван в узкий внутренний цикл, тогда разница в производительности выиграет ' t важно).
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 */
}
Стоит отметить, что если вам нужен оператор if() (потому что вы беспокоитесь, что кто-то может назвать его с помощью param > 32), это не приведет к чему-либо другому по сравнению с другим ответом:
unsigned long mask(unsigned param)
{
if (param < 32)
return (1UL << param) - 1;
else
return -1;
}
Единственное отличие состоит в том, что последняя версия имеет специальный случай param >= 32, тогда как первый имеет только специальный случай param > 32.
Как насчет этого (на Java):
int mask = -1;
mask = mask << param;
mask = ~mask;
Таким образом, вы можете избежать поисковых таблиц и жесткого кодирования длины целого числа.
Объяснение: целое число со знаком со значением -1 представлено в двоичном виде как все. Shift оставил заданное количество раз, чтобы добавить, что многие 0 вправо. Это приведет к созданию "обратной маски". Затем смените результат смещения, чтобы создать свою маску.
Это может быть сокращено до:
int mask = ~(-1<<param);
Пример:
int param = 5;
int mask = -1; // 11111111 (shortened for example)
mask = mask << param; // 11100000
mask = ~mask; // 00011111
Если вас беспокоит переполнение в C-подобном языке с (1 << param) - 1 (когда param равен 32 или 64 при типе максимального размера, маска становится равной 0, так как битовое смещение выходит за границы типа), одно решение, о котором я только что подумал:
const uint32_t mask = ( 1ul << ( maxBits - 1ul ) ) | ( ( 1ul << ( maxBits - 1ul ) ) - 1ul );
Или другой пример
const uint64_t mask = ( 1ull << ( maxBits - 1ull ) ) | ( ( 1ull << ( maxBits - 1ull ) ) - 1ull );
Вот шаблонизированная версия, имейте в виду, что вы должны использовать ее с беззнаковым типом R:
#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 );
}
Допустим, максимальные биты равны 8 с байтом, с первой функцией переполнения у нас будет 1 << 8 == 256, которая при приведении к байту становится 0. С моей функцией мы имеем 1 << 7 == 128, который может содержать байт, так что становится 1<<7 | 1<<7 - 1.
Я не скомпилировал функцию, поэтому она может содержать опечатки.
И для забавы здесь Жюльен Ройер конкретизировал:
// 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 );
}
Просто для справки (Google), я использовал следующее, чтобы получить маску all 1 для целочисленных типов.
В C++ можно просто использовать:
std::numeric_limits<uint_16t>::max() // 65535