23

什么是在 C 中构造位掩码的最佳方法，其中m设置位前面是未k设置位，然后是未n设置位：

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

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

01111000
4

5 回答 5

42

~(~0 << m) << n

于 2008-11-25T06:21:44.213 回答
29

那么，您要求以 k 个复位位为前缀的 m 个设置位，然后是 n 个复位位？我们可以忽略 k，因为它在很大程度上受到整数类型选择的限制。

mask = ((1 << m) - 1) << n;
于 2008-11-25T06:21:47.630 回答
5

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

((~((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;
}
于 2008-11-25T09:19:34.323 回答
1

虽然最重要的答案简单有效，但它们并没有为以下情况设置 MSBn=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.

于 2017-08-08T16:56:59.857 回答
1

（仅限）对于那些对支持 BMI2 的 x86 系统（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的代码少一条指令。在 Intel Haswell 处理器或更新的处理器上，两者bzhi都shlx具有 1 个周期的延迟和 2 个每个周期的吞吐量。在 AMD Ryzen 上，这两条指令的吞吐量甚至为每个周期 4 条。

于 2017-08-09T00:22:44.060 回答