bit-manipulation - 计算 AVX2 向量中每个元素的前导零位，模拟 _mm256_lzcnt_epi32

Question

使用 AVX512，有内在的 _mm256_lzcnt_epi32 ，它返回一个向量，对于 8 个 32 位元素中的每一个，该向量包含输入向量元素中前导零位的数量。

有没有一种仅使用 AVX 和 AVX2 指令来实现这一点的有效方法？

目前我正在使用一个循环来提取每个元素并应用 _lzcnt_u32功能。

相关:对一个大的位图进行位扫描，参见 Count leading zeros in __m256i word使用 pmovmskb -> bitscan 查找要对哪个字节进行标量位扫描。

这个问题是关于当您实际上要使用所有 8 个结果而不是仅选择一个结果时，在 8 个单独的 32 位元素上执行 8 个单独的 lzcnt。

Answer 1

float以指数格式表示数字，因此 int->FP 转换为我们提供了指数字段中编码的最高设置位的位置。

我们要 int -> float幅度向下舍入(将值向 0 截断)，而不是默认舍入最近。这可以四舍五入，使 0x3FFFFFFF看起来像 0x40000000 .如果您在没有进行任何 FP 数学运算的情况下进行大量这些转换，则可以将 MXCSR1 中的舍入模式设置为截断，然后在完成后将其设置回原位。

否则你可以使用 v & ~(v>>8)保留 8 个最高有效位并将一些或所有较低位归零，包括可能设置的低于 MSB 的第 8 位。这足以确保所有舍入模式永远不会舍入到下一个 2 的幂。它总是保持 8 MSB 因为 v>>8移位 8 个零，所以倒过来就是 8 个 1。在较低的位位置，无论 MSB 在哪里，8 个零都从较高的位置移过去，因此它永远不会清除任何整数的最高有效位。根据 MSB 下方的设置位如何排列，它可能会或可能不会清除低于 8 位最高有效位的更多位。

转换后，我们在位模式上使用整数移位将指数(和符号位)带到底部，并通过饱和减法消除偏差。我们使用 min如果原始 32 位输入中未设置任何位，则将结果设置为 32。

__m256i avx2_lzcnt_epi32 (__m256i v) {
    // prevent value from being rounded up to the next power of two
    v = _mm256_andnot_si256(_mm256_srli_epi32(v, 8), v); // keep 8 MSB

    v = _mm256_castps_si256(_mm256_cvtepi32_ps(v)); // convert an integer to float
    v = _mm256_srli_epi32(v, 23); // shift down the exponent
    v = _mm256_subs_epu16(_mm256_set1_epi32(158), v); // undo bias
    v = _mm256_min_epi16(v, _mm256_set1_epi32(32)); // clamp at 32

    return v;
}

脚注 1:fp->int 转换可用于截断 (cvtt)，但 int->fp 转换仅适用于默认舍入(取决于 MXCSR)。

AVX512F 为 512 位向量引入了舍入模式覆盖，可以解决这个问题， __m512 _mm512_cvt_roundepi32_ps( __m512i a, int r); .但是所有带有 AVX512F 的 CPU 也支持 AVX512CD，所以你可以使用 _mm512_lzcnt_epi32 .使用 AVX512VL， _mm256_lzcnt_epi32