C语言中的位掩码

Question

如何在C语言中构建一个比特掩码（bit mask）, 该掩码有m个已置位的比特，之前有k个未置位比特，之后还有n个未置位比特：

00..0 11..1 00..0
  k     m     n

例如，k=1，m=4，n=3会产生位掩码：

01111000

- grigy

---

许多位操作技巧的答案，例如这个，一个非常好的在线资源是位操作技巧。 - Jonathan Leffler

通常情况下，位掩码宏是在包含位索引上定义的，类似于#define BITS(p,q) ...其中p = m + n - 1且q = n，p >= q。 - user246672

“Hacker's Delight”（http://www.hackersdelight.org/）更加全面（1.8千页）和令人惊叹。 - user246672

@grigy，我真的不明白为什么你需要在这里使用 k。只使用 m 和 n 指定要设置的位范围更容易。 - Nubcake

Answer 1

您可以进行以下操作：

~(~0 << m) << n

- Darius Bacon

---

这很棒。然而，最好在这一行添加注释，以便下一个程序员能够处理它。 - mkClark

如果将其编写为函数（@quinmar答案中的set_mask_n函数），则会有一行注释说明函数的作用（而没有参数“k”），并且函数的用户将使用名称作为文档。作为代码片段中的随机表达式，这无疑是不好的！ - Jonathan Leffler

~(~0 << m) 出现在《C程序设计语言第二版》的第2.9段"按位运算符"中。它也出现在《编程实践》的第7.5段"空间效率"中，这两本书都是由Brian Kernighan和Dennis Ritchie合著的。 - Alessandro Jacopson

这种方法无法创建一个掩码，其中包括最长无符号整数类型的最高位，通常会出现警告，如“预处理器表达式中的整数溢出”。 - user246672

@Barry，我看不到问题，毫无疑问是因为很多年以来我没有看过标准（而且还是旧版的）。使用gcc -Wall --ansi --pedantic对“(0 << 1) << 31”进行测试时，我没有收到任何警告（并且在将31增加到32时会收到不同的警告，因此这是一个使用32位数字进行测试的案例）。 - Darius Bacon

Answer 2

所以，你要求的是在 k 个重置位之前和 n 个重置位之后有 m 个设置位吗？我们可以忽略 k ，因为它在很大程度上会受到整数类型的选择的限制。

mask = ((1 << m) - 1) << n;

- Jonathan Leffler

---

它们都能用，但我认为乔纳森的答案更简单明了。达里乌斯的答案对我来说有点过于反向了。 - Robert Gamble

Robert，我喜欢使用 ~0 位掩码的习惯用法，因为它不依赖于二进制补码，从这个意义上讲更简单，但确实它不太出名。只是尽我的一份力来改变这种情况！ - Darius Bacon

@Darius，你不应该在有符号类型上执行位运算，如果你这样做了，你的解决方案每次都会引发未定义的行为！ - Robert Gamble

它是未定义的吗？我手头没有规范，但我认为它是实现定义的，即编译器可以按照自己的方式进行操作，但必须始终以相同的方式进行操作。因此，当您了解处理方式（您的编译器）时，您可以依赖它。 - flolo

@Darius：继续 - 然而，同样的论点也可以用来反驳你的...哦好吧。这是最接近平局的事情了。恭喜你第一个到达那里。 - Jonathan Leffler

Answer 3

我喜欢这两种解决方案。以下是我想到的另一种方式（可能并不更好）：

((~((unsigned int)0) << k) >> (k + n)) << n

编辑： 我的上一个版本中存在一个错误（没有使用unsigned int强制转换）。问题在于~0 >> n会在前面添加1而不是0。

是的，这种方法有一个缺点；它假设您知道默认整数类型的位数，或者换句话说，它假设您真的知道k，而其他解决方案则不依赖于k。这使得我的版本不太可移植，或者至少更难移植。（它还使用了3个移位，加法和位取反运算符，这是两个额外的操作。）

因此，最好使用其他示例中的一个。

以下是Jonathan Leffler编写的一个小测试应用程序，用于比较和验证不同解决方案的输出：

#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;
}

- quinmars

---

假设这个答案可以实现，与其他两种方法相比，明显的缺点是存在第三次移位操作，这使得它更加耗时。 - Jonathan Leffler

另一个问题是它使用参数k，而其他两个解决方案可以忽略它（虽然它不使用m，但仍然只使用了三个参数中的两个）。 - Jonathan Leffler

刚才有个错误，我已经修复了，并添加了一条注释说明其他解决方案更可取。我没有完全删除它，也许有人可以从我的错误中学习，失去你的好测试代码会很遗憾 :）。 - quinmars

不应该使用强制类型转换，而应该使用'0U'表示无符号零，或者使用'0UL'表示无符号长整型。我同意保留您的答案，并同意您所做的修改。 - Jonathan Leffler

将此转换为宏或内联函数，编译器将在编译时生成常量而非代码。 - user246672

@Barry，编译器可以自由地“内联”静态函数，我相信所有现代编译器在这种情况下都会这样做。 - quinmars

Answer 4

（仅适用于那些对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

这是比@Jonathan Leffler和@Darius Bacon的代码少一条指令。 在英特尔Haswell处理器或更新版本上，bzhi和shlx的延迟为1个时钟周期，吞吐量为每个周期2次。在AMD Ryzen上，这两条指令的吞吐量甚至达到每个周期4次。

- wim

Answer 5

虽然前面的答案简单有效，但它们没有考虑当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
  assert(n >=0 && m<=31);
  return (m - n == 31 ? ~0: ((1 << (m-n)+1)-1) << n);
}

这实际上获取范围[m,n]内的位（闭区间），因此create_mask(0,0)将返回第一位（位0）的掩码，create_mask(4,6)将返回位4到6的掩码，即... 00111 0000。

- Nubcake