logo标签列表

生成位掩码的算法

calgorithmbit-manipulation
69

我遇到了一个独特的问题，需要根据输入参数生成位掩码。

例如，如果参数为2，则掩码将为0x3（11b）；如果参数为5，则掩码将为0x1F（11111b）。

我使用C中的for循环来实现这个功能，大致如下：

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

    nMask |= (1 << i);
}

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

根据您的描述，这可能是您可以做的最简单的事情...除非有任何内置的东西:p - glasnt
相关链接：*如何在C语言中替换位字段中的位而不影响其他位* 和 如何在C语言中仅设置字节的特定位而不影响其余位？ - Peter Mortensen
9个回答
118

需要注意的是，这样的位掩码始终比2的幂少1个。

表达式1 << n 是获得第n个二次幂最简单的方法。

你不希望零提供00000001的位掩码，而是希望它提供0。因此，你需要减去一。

mask = (1 << param) - 1;

编辑：

如果您需要针对参数大于32的特殊情况：

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

这种方法适用于16、32或64位整数，但您可能需要显式地为'1'指定类型。

6
不错的想法，通过减法得到全为1 :) - Khaled Alshaya
谢谢。当我为单淘汰赛构建二叉树时，我已经想通了。 - John Gietzen
13
这是规范的解决方案，但有两个需要注意的地方。首先，您应该使用unsigned int作为mask的类型，并将1U用作移位运算符的左侧；其次，请注意如果param等于或大于int中的位数（如果您继续使用带符号数学，则为比位数少一），则结果是未指定的。如果在您的环境中存在此问题，请改用查找表。 - caf
1
此外，虽然C++标准严格规定左移操作中param == width_of_unsigned_in_bits的情况会产生未定义行为，但实际上很难遇到不会在这种情况下返回0的实现。因此，在实践中，我不会特别关注这个if特殊情况，因为主要代码可以很好地处理它。 - j_random_hacker
4
你实际上测试过它吗？在我的x86架构下，使用gcc编译时，当param=32时，它生成的掩码为0，而不是全1（因为x86移位实际上按照参数模32进行移位）。我认为在大多数情况下，查找表的速度不会显著变慢。 - caf
显示剩余10条评论
30

高效、无需分支、可移植且通用（但丑陋）的实现

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的答案提供的思路）

为了方便讨论，让我们把宏实例化为unsigned int，并看看会发生什么（假设现在是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表示每个字节中位数的数量，也在编译时已知。在地球上的大多数计算机上，它等于8。由于这个表达式在编译时是已知的，编译器可能会在编译时进行乘法运算并将其视为一个常数，在本例中等于32。

接下来让我们转到：

((unsigned int) -1)

它等于0xFFFFFFFF。将-1转换为任何无符号类型都会产生该类型中的“全1”值。这部分也是编译时常量。

到目前为止，表达式：

(((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))

实际上与以下内容相同：

0xffffffffUL >> (32 - param)

这与上面Julien的答案相同。他的答案有一个问题，如果param等于0，那么产生的表达式0xffffffffUL >> 32的结果将是0xffffffffUL，而不是预期的0！（这就是为什么我将我的参数命名为__ONE_COUNT__以强调其意图）

要解决这个问题，我们可以简单地添加一个特殊情况来处理__ONE_COUNT__等于0，使用if-else或?:，像这样：

这与Julien的答案相同。他的答案有一个问题，如果param等于0，那么产生的表达式0xffffffffUL >> 32的结果将是0xffffffffUL，而不是预期的0！（这就是为什么我将我的参数命名为__ONE_COUNT__以强调其意图）

为了解决这个问题，我们可以通过使用if-else或?:语句，在代码中添加一个特殊情况来处理__ONE_COUNT__等于0的情况，像这样：

#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__为零，则等于“全0”，否则为“全1”，它作为我们在第一步计算的值的位掩码。因此，如果__ONE_COUNT__非零，则该掩码没有影响，与Julien的答案相同。如果__ONE_COUNT__是0，则屏蔽掉Julien答案的所有位，产生一个常量零。可视化效果如下：

__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
3
虽然这是一个很好的答案，但由于使用了保留标识符，所以编写的宏会引发未定义的行为。 - Remember Monica
4
实际上，情况更糟，它还会在移位时引起未定义的行为（通过将32位无符号数向右移动32位来进行移位会引起未定义的行为），因此即使修复标识符问题后，这也无法解决问题，因为它可能会导致系统崩溃或删除文件。 - Remember Monica
1
@MarcLehmann：你能举个例子说明如何将32位右移会触发文件删除吗？哪个平台和编译器会这样做？我不认为任何现有或未来的编译器会有这种疯狂的行为。虽然你说这种行为是未定义的，但你能引用一下你的声明来源吗，比如哪个规范或哪篇文章说了这个？ - Siu Ching Pong -Asuka Kenji-
2
@SiuChingPong-AsukaKenji- 一个例子是它会触发CPU异常，导致运行时跳转到一个删除文件的函数，然后解释任何寄存器设置以删除一些文件。虽然这可能不会在您特定的编译器和/或平台上发生，但问题是关于C语言，而不是其特定实现。至于该声明的起源，请参阅任何版本的C标准并搜索“未定义行为”。 - Remember Monica
1
@SiuChingPong-AsukaKenji- 以双下划线开头的标识符始终被保留。在您的情况下，是__ONE_COUNT__和__TYPE__。再次使用这些标识符会触发未定义的行为，可能会导致删除文件或更糟的情况 := - Remember Monica
显示剩余3条评论
13

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

unsigned long const mask = 0xffffffffUL >> (32 - param);
假设当然前提是 param <= 32。
2
如果“long”是32位类型，则当param = 0时，此代码将无法正常工作。 - phuclv
8
对于那些感兴趣的人，这是在其他答案的评论中讨论的查找表替代方案——区别在于它对于参数为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。
让参数等于32时使其工作很容易，而不需要创建查找表：在无符号整数中设置最后的n位，创建一个具有N个最低有效位集的掩码。 - phuclv
4
这个（Java代码）怎么样？
int mask = -1;
mask = mask << param;
mask = ~mask;

通过这种方式，您可以避免查找表以及硬编码整数的长度。

解释：带有值-1的有符号整数在二进制中表示为全1。将给定的数字左移相应次数，将许多0添加到右侧。这将导致一种“反向掩码”。然后取反移位的结果，以创建您的掩码。

这可以简化为：

int mask = ~(-1<<param);

一个例子：
int param = 5;
int mask = -1;        // 11111111 (shortened for example)
mask = mask << param; // 11100000
mask = ~mask;         // 00011111
4
或者，你可以使用0而不是-1。 "int mask = (0<<param);" 这对于无符号数可能更好。 - broadbear
这在C语言中也是完全有效的。但至少在C语言中，您需要添加后缀（ull）才能使其对于（几乎）任何类型都有效：#define BITMASK_GEN(pos, len) (~(~0ull << len) << pos)。这适用于除unsigned __int128之外的所有类型。 - alx - recommends codidact
2

从我的经验来看，抱歉我在移动设备上。为了清晰起见，我假设使用64位类型，但这可以很容易地推广。

(((uint64_t) (bits < 64)) << (bits & 63)) - 1u

这是一个典型的无分支、无未定义行为的代码：(1 << bits) - 1，对于整个值范围都能得到正确结果，在某些平台上& 63可以被优化掉。
当移位大于或等于类型宽度时，左移操作数变成0。
为避免未定义行为，右移操作数被掩码处理，其值永远不会超过63。这只是为了让编译器和语言专家满意，因为当左操作数已经为零时（对于大于63的值），没有平台会再添加1。在已经具有底层指令此行为的平台（如x86）上，好的编译器应该删除& 63掩码处理。
正如我们所看到的，大于63的值会从移位中得到0的结果，但后面会减去1，使得所有位都设置为无符号整数下溢，这在无符号类型上不是未定义行为。
1
如果您担心在类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。
我没有编译这个函数，所以可能会有拼写错误。

为了好玩，这里有Julien Royer的详细介绍：

// 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 );
}
1

如果您需要一个32位掩码，可以使用以下代码（对于64位掩码，请使用uint64_t）：

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int
main()
{
    size_t n = 8;
    assert(n <= 32);
    uint32_t mask = ~(uint32_t)0 >> (32 - n);

    printf("mask = %08" PRIX32 "\n", mask);
}

我知道这是对一个非常旧的帖子的回答。但是如果有人类真正阅读了这个：我欢迎任何反馈。

1
你可以避免使用显式的 32，这里有一个适用于所有无符号类型和所有值从 1 到类型宽度的解决方案：uint32_t mask = -1; mask = ~(mask << (n - 1) << 1); - chqrlie
@chqrlie 在我看来，C语言并不保证使用二进制补码（当然，这只是纯学术问题）。因此，在使用符号和大小表示的奇特机器上，-1可能被表示为类似于10...01的东西。 - Michael Lehn
1
纯粹的学术问题，但是无论如何将 -1 表示为有符号整数，在转换为无符号类型时，值都是该类型的最大值，并且 uint32_t 必须恰好有 32 位。 - chqrlie
-2

仅供参考（谷歌），我使用以下内容获取整数类型的所有1掩码。
在C++中，可以简单地使用：

std::numeric_limits<uint_16t>::max() // 65535

2
问题是如何在右侧获取 N 个 1 位的掩码，而不是如何获取全部为 1。 - phuclv
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接