将最左边的设置位转换为右侧交替位的位操作？

Question

我正在尝试最大程度地优化低级子例程，但我无法找出在这种特定情况下翻转位的最快方法：

给定一个二进制整数n，其中所有设置位都在所有清除位的左侧（例如11110000、110000、1110000），是否可能生成数字长度为 ((number of set bits in n) - 2) * 2 的二进制整数，所有偶数位均已设置且所有奇数位均已清除？

示例：

n = 111000, answer: 10
n = 1111000, answer: 1010
n = 110, answer: 0
n = 111110000000, answer: 101010
n = 1111111111000000000, answer: 1010101010101010

n 保证至少有 2 个 set bits，并且至少有 (set bits - 1) clear bits

答案必须仅使用固定数量的位操作and/or算术运算（即无循环），并且不能使用任何类型转换（仅整数，无字符串）。

Answer 1

一种方法可能是使用这些步骤：

右对齐（丢弃尾随零）
去掉 2 个设置位
设置位数加倍
屏蔽偶数位

例如，仅使用 "basic" 操作：

// right-justify
x = x / (x & -x)
// get rid of 2 set bits
x >>= 2
// double the number of set bits
x *= x + 2
// mask out even bits
x &= 0xAAAAAAAAAAAAAAAA

那一步 "double the number of set bits" 依赖于 x 在这一点上是 2 减 1 的幂。如果 x 可以写成 2^k-1 那么 x * (x + 2) 将是 (2^k-1) * ( 2^k+1) = 2^2k-1 所以它使设置位数加倍。

除法不是很好，如果你有一个快速 tzcnt 那么你可以右对齐：

x >>= tzcnt(x)

使用快速 pdep（Intel Haswell 和更新版本，在 AMD Ryzen 上运行但速度较慢），可以避免将设置位数加倍，

// spread out the bits to even positions
x = pdep(x, 0xAAAAAAAAAAAAAAAA)

快速 pext 可以用作替代右对齐，

// right-justify
x = pext(x, x)

对于常见的 popcnt 可以使用更直接的方法，计算设置位的数量，减去二，然后生成该大小的模式，例如通过右移 0xAAAAAAAAAAAAAAAA 直到它足够短，或者使用 bzhi 在顶部截断它。

Answer 2

这是一个 Python 算法，它不关心第一个右边有多少个零位。它构建答案时无需担心减去 1 位中的 2 位，最后将结果向右移动 4 位以将其考虑在内。

k = 0
n = 0b111110000

while n != 0:
    if n & 1 != 0:
        k = (k << 2) + 2
    n >>= 1

print(bin(k>>4))

将最左边的设置位转换为右侧交替位的位操作？

Bit manipulation to convert leftmost set bits to right-side alternating bits?

c

c++

python

bit-manipulation

bitwise-operators