27

背景

很长一段时间以来，gcc 一直提供许多内置的位旋转函数，特别是尾随和前导 0 位的数量（也用于long unsignedand long long unsigned，后缀为land ll）：

— 内置功能：int __builtin_clz (unsigned int x)

返回 中前导 0 位的数量x，从最高有效位位置开始。如果x为 0，则结​​果未定义。

— 内置功能：int __builtin_ctz (unsigned int x)

返回 中尾随 0 位的数量x，从最低有效位位置开始。如果x为 0，则结​​果未定义。

然而，在我测试的每个在线（免责声明：仅限 x64）编译器上，结果都是两者都clz(0)返回ctz(0)底层内置类型的位数，例如

#include <iostream>
#include <limits>

int main()
{
    // prints 32 32 32 on most systems
    std::cout << std::numeric_limits<unsigned>::digits << " " << __builtin_ctz(0) << " " << __builtin_clz(0);    
}

活生生的例子。

尝试的解决方法

最新的 Clang SVN 主干std=c++1y模式使所有这些函数都放松了 C++14 constexpr，这使得它们可以在 SFINAE 表达式中使用，用于围绕 3 ctz/clz内置函数的包装函数模板unsigned，unsigned long和unsigned long long

template<class T> // wrapper class specialized for u, ul, ull (not shown)
constexpr int ctznz(T x) { return wrapper_class_around_builtin_ctz<T>()(x); }

// overload for platforms where ctznz returns size of underlying type
template<class T>
constexpr auto ctz(T x) 
-> typename std::enable_if<ctznz(0) == std::numeric_limits<T>::digits, int>::type
{ return ctznz(x); }

// overload for platforms where ctznz does something else
template<class T>
constexpr auto ctz(T x) 
-> typename std::enable_if<ctznz(0) != std::numeric_limits<T>::digits, int>::type
{ return x ? ctznz(x) : std::numeric_limits<T>::digits; }

这个 hack 的好处是，提供所需结果的平台ctz(0)可以省略一个额外的条件来测试x==0（这似乎是一个微优化，但是当你已经降到内置位旋转函数的水平时，它可以使差别很大）

问题

内置函数系列clz(0)和的未定义程度如何ctz(0)？

  • 他们可以抛出std::invalid_argument异常吗？
  • 对于 x64，它们对于当前的 gcc 发行版会返回底层类型的大小吗？
  • ARM/x86 平台有什么不同吗（我无权测试这些平台）？
  • 上述 SFINAE 技巧是分离此类平台的明确方法吗？
4

2 回答 2

18

该值未定义的原因是它允许编译器使用结果未定义的处理器指令，而这些指令是获得答案的最快方式。

但重要的是要了解，不仅结果未定义；他们是不确定的。例如，根据英特尔的指令参考，指令返回当前时间的低 7 位是有效的。

这就是它变得有趣/危险的地方：编译器编写者可以利用这种情况来生成更小的代码。考虑一下您的代码的这个非模板专业化版本：

using std::numeric_limits;
template<class T>
constexpr auto ctz(T x) {
  return ctznz(0) == numeric_limits<T>::digits || x != 0
       ? ctznz(x) : numeric_limits<T>::digits;
}

这适用于决定为 ctznz(0) 返回#bits 的处理器/编译器。但是在决定返回伪随机值的处理器/编译器中，编译器可能会决定“我可以为 ctznz(0) 返回任何我想要的内容，如果我返回#bits，代码会更小，所以我会” . 然后代码最终总是调用 ctznz，即使它产生了错误的答案。

换句话说：编译器的未定义结果不能保证与运行程序的未定义结果一样是未定义的。

真的没有办法解决这个问题。如果必须使用 __builtin_clz，源操作数可能为零，则必须始终添加检查。

于 2014-11-07T20:01:17.843 回答
15

不幸的是，即使是 x86-64 实现也可能与英特尔的指令集参考不同，BSF并且BSR，在源操作数值为 的情况下(0)，目标未定义，并设置ZF（零标志）。因此，微架构或 AMD 和 Intel 之间的行为可能不一致。（我相信 AMD 不会修改目的地。）

较新的LZCNT和TZCNT指令并不无处不在。两者都只存在于 Haswell 架构（对于英特尔）。

于 2013-10-22T21:43:56.237 回答