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

Question

我想创建一个宏或函数¹ mask(n),给定一个数字n返回一个无符号整数,其n最低有效位设置.虽然这似乎应该是一个基本的原语,经过大量讨论的实现有效编译 - 似乎并非如此.

当然,各种实现对于原始整数类型可能具有不同的大小unsigned int,因此,为了具体起见,我们假设我们正在讨论uint64_t具体返回,尽管当然可接受的解决方案对于任何无符号整数类型都有效(具有不同的定义).特别是,当返回的类型等于或小于平台的原始宽度时,解决方案应该是高效的.

重要的是,这必须适用于所有人n[0,64].尤其是mask(0) == 0和mask(64) == (uint64_t)-1.许多"明显的"解决方案不适用于这两种情况之一.

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

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

在性能名称中牺牲简单性的解决方案,例如,在不同平台上使用不同的实现,是很好的.

---

¹最常见的情况是一个函数,但理想情况下它也可以作为宏工作,而不必多次重新评估它的任何参数.

Answer 1

尝试

\n\n

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

\n\n

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

\n\n

您的编译器可能可以找出内联此内容，但您可以使用inlineor （在 C++ 中）给出提示constexpr。

\n\n

该unsigned long long int类型保证至少为 64 位宽并且存在于每个实现中，但事实uint64_t并非如此。

\n\n

如果您需要一个宏（因为您需要作为编译时常量的东西），则可能是：

\n\n

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

\n\n

正如几个人在评论中正确提醒我的那样，1ULL << 64U潜在的未定义行为！因此，请针对该特殊情况插入检查。

\n\n

如果在宽于 64 位的实现上支持该类型的全部范围对您来说很重要，则可以替换64U为。CHAR_BITS*sizeof(unsigned long long)

\n\n

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

\n\n

预计到达时间：

\n\n

（N1570 草案）标准的相关部分规定，对于左移和右移：

\n\n

\n

如果右操作数的值为负数或大于或等于提升的左操作数的宽度，则行为未定义。

\n

\n\n

这让我绊倒了。再次感谢评论中审查我的代码并向我指出错误的每个人。

\n

Answer 2

另一种没有分支的解决方案

unsigned long long mask(unsigned n)
{
    return ((1ULL << (n & 0x3F)) & -(n != 64)) - 1;
}

n & 0x3F将移位量保持在最大值63以避免UB.事实上,大多数现代架构只会抓取移位量的较低位,因此不需要and指令.

64的检查条件可以改为-(n < 64)使其返回所有的n = 64,相当于_bzhi_u64(-1ULL, (uint8_t)n).

Clang的输出看起来比gcc好.在发生这种情况时,gcc会针对MIPS64和ARM64发出条件指令,但不会针对x86-64发出条件指令,从而导致输出更长

条件也可以简化为n >> 6,利用n = 64时它将为1的事实.我们可以从结果中减去它而不是像上面那样创建一个掩码

return (1ULL << (n & 0x3F)) - (n == 64) - 1; // n >= 64
return (1ULL << (n & 0x3F)) - (n >> 6) - 1;

gcc编译后者

mov     eax, 1
shlx    rax, rax, rdi
shr     edi, 6
dec     rax
sub     rax, rdi
ret

一些更多的选择

return ~((~0ULL << (n & 0x3F)) << (n == 64));
return ((1ULL << (n & 0x3F)) - 1) | (((uint64_t)n >> 6) << 63);