Bit Hack 获取位变化的位置

Question

我需要想出一个 bit-hack 来找到位值变化的第一个位置。它可以是从 0 到 1 或 1 到 0。

// This would give 0 since no changes happen
let x1 = 0b00000000

// This also gives 0 since there is no change
let x2 = 0b11111111

// This would give 1 since the value changes after the first bit
let x3 = 0b10000000

// This would also give 1 since the value change 
// happens at the first bit
let x4 = 0b01111111

// This would return 7 since the change is at the 7th bit
let x5 = 0b00000001

// This would also return 7
let x6 = 0b11111110

对能产生这些结果的咒语有什么建议吗？

Answer 1

密钥 building-block 与 bsr 类似 bit-scan。（或 31-lzcnt）。
这找到了最高 1 位的位置，我们可以转换您的输入以为此工作。

如果设置了前导位，则在 bit-scan 之前不设置。喜欢 x = ((int32_t)x<0) ? ~x : x; 和 mov ecx, eax / xor eax, -1（喜欢 NOT 但设置 FLAGS）/ cmovns ecx, eax。所以就像一个 absolute-value 习语，但用 NOT 而不是 NEG 。另一个选项是 sar reg,31 (or cdq) / xor 是否翻转。

#include <bit>          // C++20
#include <stdint.h>

int transition_position(uint32_t x)
{
    x = ((int32_t)x<0) ? ~x : x;            // make the leading bits zero
    if (x == 0) __builtin_unreachable();    // optional, x|=1 is another way to handle the case where all bits are the same, allowing BSF without branching
    return std::countl_zero(x) ^ 31;        // 31-lzcnt in a way that GCC can optimize back to bsf
}

这与 GCC / clang 编译得很好：https://godbolt.org/z/63nEcnTso

gcc11.2 and clang13 -O3 both make this asm
transition_position(unsigned int):
        mov     eax, edi
        sar     eax, 31            # missed optimization: should shift EDI so mov is off the critical path on CPUs without mov-elimination
        xor     eax, edi
        bsr     eax, eax
        ret

使用 -march=haswell，他们都 de-optimize 通过使用 lzcnt 然后是实际的 xor eax,31。（那个 asm 对 AMD 来说仍然更好，其中 bsf 比 tzcnt/lzcnt 慢得多，所以它对 -mtune=generic -mbmi 有好处，但对 -march=haswell 不好）