c++ 当n等于类型的位宽时，获得避免UB的n位掩码？

lndjwyie 于 2023-06-25 发布在其他

关注(0)|答案(4)|浏览(172)

我有一个小的正整数n，我使用一个无符号整数类型来存储一个包含n位的掩码。通常，需要构造具有所有n位集的掩码。例如，如果n是5，则掩码将是0b11111u。
构造这种掩码的典型方法是执行以下操作（本示例假设掩码使用unsigned，但可以为任何无符号整数类型编写一些内容）：

unsigned all_set_mask = (1u << n) - 1u;

然而，如果n正好等于无符号整数类型的位宽，则1u << n是未定义的行为，如[expr.shift#1]所示：
操作数应为整数或无作用域枚举类型，并执行整数提升。结果的类型是提升的左操作数的类型。如果右操作数为负，或大于或等于提升的左操作数的宽度，则行为未定义。
合理的解释“构造一个掩码，设置所有n位”可以说应该允许这样的情况，即我们的位数正好与底层整数类型的位宽一样多，因此典型的实现不支持所有合理的输入。
此外，在现代处理器上，汇编左移指令在移位位宽时是无操作的，因此all_set_mask可能最终成为0，这在任何情况下都不是预期的答案。
有没有一种符合标准的方法来重写它，而不需要求助于if语句或复杂的位操作？我查看了<bit>，但没有看到任何有用的东西。

c++

来源：https://stackoverflow.com/questions/76501163/get-an-n-bit-mask-avoiding-ub-when-n-is-equal-to-the-bit-width-of-the-type

4条答案

按热度按时间

t98cgbkg1#

一个简单的方法如下：

n == 0 ? 0 : 0xffffffff >> (32 - n)

我们可以稍微重写一下，以在移位计数取寄存器宽度取模的典型架构上保存一条指令：

n == 0 ? 0 : 0xffffffff >> (-n & 31)

然后去掉条件：

(unsigned)(-(signed)n >> 31) >> (-n & 31)

这应该在典型的CPU上编译为三条指令（汇编比C更可读的罕见情况之一）。
请注意，这假设有符号右移是算术移位，只有从C20开始它才是迂腐的正确。

赞(0）回复(0）举报 2023-06-25

nmpmafwu2#

我建议设置所有的位和右移走不需要的位。
当n是0时，您仍然需要测试边缘情况，否则它将移走所有位，结果是未定义的行为。

template <class T>
    requires std::is_unsigned_v<T>
constexpr T all_set_mask(unsigned n) {
    if(n == 0) return T{};
    
    constexpr unsigned  bits = sizeof(T) * CHAR_BIT;
    // extra test for too many bits if needed:
    //if(n > bits) return static_cast<T>(-1);
    
    return static_cast<T>(-1) >> (bits - n);
}

Demo

赞(0）回复(0）举报 2023-06-25

yc0p9oo03#

你可以对任何unsigned类型无条件地执行此操作：

(((1u << (n + 1) / 2) - 1u) << n / 2) | ((1u << n / 2) - 1u);

使用16位无符号的示例：

#include <iostream>

int main() {
  for (int n = 0; n <= 16; ++n) {
    const uint16_t r = (((1u << (n + 1) / 2) - 1u) << n / 2) | ((1u << n / 2) - 1u);
    std::cout << std::hex << r << " ";
  }
}

// Output: 0 1 3 7 f 1f 3f 7f ff 1ff 3ff 7ff fff 1fff 3fff 7fff ffff

赞(0）回复(0）举报 2023-06-25

vfh0ocws4#

在x86 - 64上，_bextr_u64(UINT64_C(-1), 0, n)。

赞(0）回复(0）举报 2023-06-25