python - 位操纵将最左边的设置位转换为右边的交替位？

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

给定一个二进制整数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
答案必须仅使用恒定数量的位操作和/或算术运算(即无循环)，并且不能使用任何类型转换(仅整数，无字符串)。

最佳答案

一种方法是使用以下步骤:

右对齐(舍弃尾随零)

摆脱2个设置位

设置位数的两倍

屏蔽偶数位

例如，仅使用“基本”操作:

// 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

该步骤“将置位的位数加倍”取决于x在该点上是2减1的幂。如果x可以写为2k-1，则x * (x + 2)将为(2k-1)*(2k + 1)= 22k-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 将其截断。最佳。