生成位掩码的算法

Question

我正面临着这个基于输入参数生成位掩码的独特问题.例如,

如果param = 2,那么如果param = 5,则掩码将为0x3(11b),然后掩码将为0x1F(1 1111b)

这是我在C中使用for循环实现的

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

    nMask |= (1 << i);
}

我想知道是否有更好的算法~~~

Answer 1

有关像这样的位掩码需要注意的一点是,它们总是小于2的幂.

表达式1 << n是获得2的n次幂的最简单方法.

你不希望Zero提供一个位掩码00000001,你希望它提供零.所以你需要减去一个.

mask = (1 << param) - 1;

编辑:

如果你想要一个> 32的param特例:

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

此方法应适用于16位,32位或64位整数,但您可能必须显式键入"1".

Answer 2

高效,无分支,可移植和通用(但丑陋)的实现

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

说明

首先,如在其他答案中已经讨论的那样,>>使用而不是<<为了在移位计数等于值的存储类型的位数时防止问题.(感谢朱利安上面的回答)

为了便于讨论,让我们用unsigned intas "实例化"宏,__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,也就是每个字节的位数.它在编译时也是已知的.它等于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)))

如果__ONE_COUNT__为零则等于"all-0s",否则等于"all-1s".它充当我们在第一步中计算的值的位掩码.因此,如果__ONE_COUNT__非零,那么掩码没有效果,它与Julien的答案相同.如果__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 3

或者,您可以使用右移以避免(1 << param) - 1解决方案中提到的问题.

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

param <= 32当然,假设

Answer 4

对于那些感兴趣的人来说,这是在另一个答案的评论中讨论的查找表替代方案 - 不同之处在于它对于32的参数正确工作.unsigned long long如果你需要,它很容易扩展到64位版本,并且应该速度有明显不同(如果在紧密的内循环中调用它,那么静态表将保持至少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.