C中的位掩码
在C中构造位掩码的最佳方法是m
设置位,前面是k
设置位,后跟n
设置位:
00..0 11..1 00..0 kmn
例如,k = 1,m = 4,n = 3将导致位掩码:
01111000
〜(〜0 << m)<< n
那么,你要求m个设置位前缀为k个复位位,后跟n个复位位? 我们可以忽略k,因为它在很大程度上受到整数类型选择的约束。
mask = ((1 << m) - 1) << n;
我喜欢这两种解决方案 这是我想到的另一种方式(可能不是更好)。
((~((unsigned int)0) << k) >> (k + n)) << n
编辑:我以前的版本中有一个错误(没有unsigned int cast)。 问题是〜0 ~0 >> n
在前面增加1,而不是0。
是的,这种方法有一个很大的缺点; 它假设您知道默认整数类型的位数,或者换句话说它假设您确实知道k,而其他解决方案独立于k。 这使得我的版本不那么便携,或者至少难以移植。 (它还使用3个移位,加法和按位求反运算符,这是两个额外的运算。)
所以你最好使用其他一个例子。
这是Jonathan Leffler完成的一个小测试应用程序,用于比较和validation不同解决方案的输出:
#include #include 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; }
虽然最高答案是简单有效的,但当n=0
且m=31
时,它们不会为情况设置MSB:
~(~0 << 31) << 0
= 0111 0111 1111 1111 1111 1111 1111 1111 1111
((1 << 31)-1) << 0
= 0111 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 return (m - n == 31 ? 0xFFFFFFFF : ((1 << (mn)+1)-1) << n); }
这实际上得到了[m,n]
范围内的位(闭区间),因此create_mask(0,0)
将返回第一位(位0)的掩码, create_mask(4,6)
返回位4的掩码6即... 00111 0000
。
(仅限)对于那些对支持BMI2的x86系统(英特尔Haswell或更新版本,AMD挖掘机或更新版本)更有效的解决方案感兴趣的人:
mask = _bzhi_u32(-1,m)<
bzhi
指令bzhi
定位位置的高位置零。 _bzhi_u32
内在编译到此指令。 测试代码:
#include #include /* gcc -O3 -Wall -m64 -march=haswell bitmsk_mn.c */ unsigned int bitmsk(unsigned int m, unsigned int n) { return _bzhi_u32(-1,m)<
输出:
$./a.out k= 000FE000
代码片段_bzhi_u32(-1,m)<
movl $-1, %edx bzhi %edi, %edx, %edi shlx %esi, %edi, %eax
这是比@Jonathan Leffler和@Darius Bacon的代码少一条指令。 在Intel Haswell处理器或更新版本上, bzhi
和shlx
的延迟为1个周期,每个周期的吞吐量为2。 在AMD Ryzen上,这两条指令甚至每个周期的吞吐量为4。