Алгоритм генерации битовой маски

Question

Я столкнулся с этой уникальной проблемой создания битовой маски на основе входного параметра. Например,

если параметр = 2, то маска будет 0x3 (11b) если параметр = 5, то маска будет 0x1F (1 1111b)

Это Я реализован с использованием для цикла в C, что-то вроде

int nMask = 0; 
for (int i = 0; i < param; i ++) { 

    nMask |= (1 << i); 
} 

Я хотел бы знать, если есть лучший алгоритм ~~~

Answer 1

одно заметить о битмасках как то, что они всегда один меньше, чем степень двойки.

Выражение «1 < < n» - это простой способ получить n-ю степень двух.

Вы не хотите, чтобы Zero предоставил битмаску «00000001», вы хотите, чтобы она обеспечивала нуль. Поэтому вам нужно вычесть его.

mask = (1 << param) - 1; 

Edit:

Если вы хотите, особый случай для PARAM> 32:

int sizeInBits = sizeof(mask) * BITS_PER_BYTE; // BITS_PER_BYTE = 8; 
mask = (param >= sizeInBits ? -1 : (1 << param) - 1); 

Этот метод должен работать на 16, 32 или 64 битные целые числа, но вы можете должны явно ввести «1».

Answer 2

Для тех, кого это интересует, это альтернатива альтернативного варианта, обсуждаемая в комментариях к другому ответу - разница в том, что она корректно работает с параметром 32. Достаточно просто перейти к 64-битной версии unsigned long long, если вы нужно, и не должно быть значительно отличающимся по скорости (если он вызван в узком внутреннем цикле, тогда статическая таблица останется как минимум в кэше L2, а если это , а не, вызываемый в плотном внутреннем цикле, тогда разница в производительности выиграла не важно).

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.

Answer 3

В качестве альтернативы вы можете использовать смену вправо, чтобы избежать проблемы, упомянутой в решении (1 << param) - 1.

unsigned long const mask = 0xffffffffUL >> (32 - param); 

при условии, что param <= 32, конечно.

Answer 4

Эффективное, Отделение-Free, портативный и универсальный (но Уродливый) Реализация

C:

#include <limits.h>  /* CHAR_BIT */ 

#define BIT_MASK(__TYPE__, __ONE_COUNT__) \ 
    ((__TYPE__) (-((__ONE_COUNT__) != 0))) \ 
    & (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__))) 

C++:

#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 

Объяснение

Прежде всего, как уже обсуждалось в других ответах, >> используется вместо << для того, чтобы предотвратить проблему, когда величина сдвига равна к числу бит типа хранения значения. (Спасибо Julien's answer above за идею)

Для простоты обсуждения, давайте «экземпляр» макрос с 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 равно 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))) 

равно "все-0", если __ONE_COUNT__ равен нулю, и "все-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 

Answer 5

Как об этом (в 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