创建一个设置了 N 个最低有效位的掩码

Question

我想创建一个宏或函数¹ mask(n) 给定一个数字 n 返回一个无符号整数及其 n 最低有效位设置。虽然这看起来应该是一个基本原语，具有经过大量讨论的可高效编译的实现 - 但事实并非如此。

当然，对于像 unsigned int 这样的原始整数类型，各种实现可能有不同的大小，所以为了具体起见，我们假设我们正在讨论返回一个 uint64_t具体来说，尽管可接受的解决方案当然适用于任何无符号整数类型(具有不同的定义)。特别是，当返回的类型等于或小于平台的 native 宽度时，该解决方案应该是高效的。

重要的是，这必须适用于 [0, 64] 中的所有 n。特别是 mask(0) == 0 和 mask(64) == (uint64_t)-1。许多“显而易见”的解决方案不适用于这两种情况之一。

最重要的标准是正确性:只有不依赖于未定义行为的正确解决方案才是有趣的。

第二个最重要的标准是性能:理想情况下，习语应该编译成大约最有效的特定于平台的方式，以便在通用平台上执行此操作。

为了性能而牺牲简单性的解决方案，例如，在不同平台上使用不同的实现，是好的。

---

¹ 最一般的情况是一个函数，但理想情况下它也可以作为一个宏使用，而不需要多次重新计算它的任何参数。

Answer 1

尝试

unsigned long long mask(const unsigned n)
{
  assert(n <= 64);
  return (n == 64) ? 0xFFFFFFFFFFFFFFFFULL :
     (1ULL << n) - 1ULL;
}

有几个很好的、聪明的答案可以避免条件，但现代编译器可以为此生成不分支的代码。

你的编译器可能会想出内联这个，但你可以用 inline 给它一个提示或者，在 C++ 中，constexpr .

unsigned long long int type 保证至少为 64 位宽并且出现在每个实现中，uint64_t不是。

如果你需要一个宏(因为你需要一些可以作为编译时常量的东西)，那可能是:

#define mask(n) ((64U == (n)) ? 0xFFFFFFFFFFFFFFFFULL : (1ULL << (unsigned)(n)) - 1ULL)

正如一些人在评论中正确提醒我的那样，1ULL << 64U是潜在的未定义行为!因此，为该特殊情况插入一个支票。

您可以替换 64U与 CHAR_BITS*sizeof(unsigned long long)如果在宽度超过 64 位的实现中支持该类型的全部范围对您来说很重要。

您可以类似地从无符号右移生成它，但您仍然需要检查 n == 64作为一种特殊情况，因为按类型宽度右移是未定义的行为。

预计到达时间:

The relevant portion of the (N1570 Draft) standard说，左右移位:

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

这把我绊倒了。再次感谢评论中所有审阅我的代码并向我指出错误的人。