生成前缀位掩码

Question

我正在寻找一种便携式方法来生成前缀位掩码，其中第一个

n

位设置为

0 <= n <= 32

（或64或任意整数类型位宽度）。

示例：

prefix_bitmask(0)  = 0b00000000000000000000000000000000u
prefix_bitmask(4)  = 0b00000000000000000000000000001111u
prefix_bitmask(32) = 0b11111111111111111111111111111111u

如果我们忽略这些情况

n == 0

或

n == 32

：

，有两种方法可以实现这一点

// "constructive": set only the required bits
uint32_t prefix_mask1(int i) { return (uint32_t(1) << i) - 1; }
// "destructive": shift unneeded bits out
uint32_t prefix_mask2(int i) { return ~uint32_t(0) >> (32 - i); } 

prefix_mask1

对于 32 失败，

prefix_mask2

对于 0 失败，两者都是因为大于整数类型的移位是未定义的行为（因为允许 CPU 仅使用移位大小的最低 5 位）。

有没有一种“规范”的方法可以在不分支的情况下解决这个问题？

Answer 1

((uint32_t) 1 << i/2 << i-i/2) - 1

.

上面的工作原理是，

uint32_t

可以替换为任何无符号类型。并且不需要其他改变。需要知道类型中的位数

b

和掩码

m

= 2

b

−1 的其他选项包括：

((uint32_t) 1 << (i & m)) - 1 - (i >> b)

（来自超级猫）

和：

((uint32_t) i >> b) ^ 1) << (i & m)) - 1

（源自Matt Timmermans的建议）。

Answer 2

这可以使用

prefix_mask2

思想通过算术移位来准备正确的模式，总共三个指令（假设 CPU 中的移位计数以字宽为模）：

// minimal instruction dependency (2 cycles), but requires large constant
// that some architectures have trouble generating
uint32_t prefix_mask2a(int i) {
    return ((int32_t) (i + (0x80000000 - 32))) >> ((i ^ 31) & 31);
}

// 3 cycles
uint32_t prefix_mask2b(int i) {
    return (uint32_t) ((int32_t) -i >> 31) >> (-i & 31);
}

Answer 3

您可以将

uint32_t

转换为具有更多位的内容，将其移位，然后转换回来：

uint32_t prefix_mask(int i) {
  return UINT32_MAX & ((UINT64_C(1) << i) - 1);
}

Answer 4

我觉得它很便携

#define PREFIX(type, n) (type)(((sizeof(type) * CHAR_BIT - (n)) == sizeof(type) * CHAR_BIT) ? ((type)0) : (!(sizeof(type) * CHAR_BIT - (n)) ? (~(type)(0)) : ((~(type)(0)) << (sizeof(type) * CHAR_BIT - n))))
#define POSTFIX(type, n) (type)(((sizeof(type) * CHAR_BIT - (n)) == sizeof(type) * CHAR_BIT) ? ((type)0) : (!(sizeof(type) * CHAR_BIT - (n)) ? (~(type)(0)) : ((~(type)(0)) >> (sizeof(type) * CHAR_BIT - n))))

#define TEST_TYPE unsigned long long

void printbin(TEST_TYPE x)
{
    TEST_TYPE mask = (TEST_TYPE)1 << (sizeof(x) * CHAR_BIT - 1);
    while(mask)
    {
        printf("%d", !!(x & mask));
        mask >>= 1;
    }
}


int main()
{
    for(int x = 0; x <= sizeof(TEST_TYPE) * CHAR_BIT; x++)
    {
        printbin(PREFIX(TEST_TYPE, x)); printf("\n");
    }
    printf("\n");
    for(int x = 0; x <= sizeof(TEST_TYPE) * CHAR_BIT; x++)
    {
        printbin(POSTFIX(TEST_TYPE, x)); printf("\n");
    }
}

https://godbolt.org/z/_NadkH