生成前缀位掩码

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位）。

是否有一种不需要分支的“规范”解决方法？

- Tobias Ribizel

---

((unit32_t)(-1)) >> (32-i) - Weather Vane

32不比整数类型大。这是因为你的5位规则吗？是的，我明白了，32位移不起作用。它具有与>> 0相同的效果，但可能未定义。 - Weather Vane

就此而言，未定义行为并不意味着“有两种方法可以得到相同的结果”，而是“有任意多种方法可以得到任意结果” ;) - 463035818_is_not_a_number

我知道，我主要是在尝试推理为什么基于底层机器架构，越界移位最有可能被声明为未定义行为 ;) - Tobias Ribizel

就C标准而言，它们是未定义行为。这并不意味着在任何给定的架构上你不能定义实际发生的情况。 - Weather Vane

Answer 1

((uint32_t) 1 << i/2 << i-i/2) - 1可以适用于任意无符号类型，不需要做其他更改。其他选项需要知道类型中位数 b 和掩码m = 2 ^{b −1，包括：}

((uint32_t) 1 << (i & m)) - 1 - (i >> b)（来自supercat）

和:

((uint32_t) i >> b) ^ 1) << (i & m)) - 1（基于Matt Timmermans的建议推导而来）。

- Eric Postpischil

---

任何半靠谱的优化器都能解决这个问题。 - MSalters

@MSalters：弄清楚什么？你的意思是它会认识到它等同于1 << i，除非在i是类型宽度时定义并实现最佳代码？如果机器没有实现完整宽度移位的指令，最优代码是什么样子的？是在测试i后进行条件移动或分支，两个按原样移位，还是其他什么？ - Eric Postpischil

你真正想要做的是 <<i，但对于 <<32，需要适当的清零语义。 - MSalters

@MSalters 既不是clang 10也不是gcc 10.1（点击此处查看）能够解决这个问题，但我可以说它们都不是很好的编译器。 - harold

@EricPostpischil：我猜对于i从0到32（包括0和32）的值，字面上的翻译(1u << (i & 31)) - 1 - (i >> 5)可能会相当不错。 - supercat

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

- Falk Hüffner

Answer 3

您可以将uint32_t转换为比它更多位的类型，进行移位操作，然后再转换回来：

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

- Socowi

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

- 0___________

---

我认为你在OP的问题中漏掉了一个重要点：“有没有一种“规范”的方法来解决这个问题，而不需要分支？” - Socowi