如何改进 Python 代码以交换 32 位整数的位

Question

Swap bits - 编码面试问题

几天前，我遇到了以下编码面试问题（使用Python）。

问题：

给定一个 32 位整数，交换第 1 位和第 2 位，第 3 位和第 4 位，直到第 31 位和第 32 位。

这是一些起始代码和示例：

def swap_bits(num):
    # Fill this in.

print(f"0b{swap_bits(0b10101010101010101010101010101010):032b}")
# 0b01010101010101010101010101010101

我的解决方案：

def swap_bits(num):
    num_out = 0
    for ii in range(16):
        num_out += (num & (2**(2*ii))) << 1
        num_out += (num & (2**(2*ii+1))) >> 1
    return num_out

print(f"0b{swap_bits(0b10101010101010101010101010101010):032b}")

# Output: 
# 0b01010101010101010101010101010101

我要问你的问题：

在效率、代码长度、可读性等方面，您有什么改进建议吗？我将非常感谢您的反馈。 谢谢！

Answer 1

你不需要为此使用循环（好吧，你不能为此使用循环，在编码面试中），只需几个二元运算符：

>>> n = 752846942
>>> bin(n)
'0b101100110111111000100001011110'
>>> bin(((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1))
'0b011100111011110100010010101101'

我在最后一个数字前添加了一个 0，以使结果更容易与 n 进行比较。

有什么诀窍？

将您的数字视为位向量。交换位对相当于将所有偶数位向左移动一位，所有奇数位向右移动一位（假设位编号从 0 开始，从右边的 LSB 开始）。

向左和向右移动只是二进制移位：n << 1和n >> 1。但是如果我简单地做(n << 1) | (n >> 1)，我会移动所有位，结果是错误的。所以，首先 select 你想要的位：偶数位是 0x55555555 & n，奇数位是 n & 0xaaaaaaaa.

所以一种可能是：

((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >> 1)

另一种方法是select位在移位之后但在二进制之前：

((n << 1) & 0xaaaaaaaa) | ((n >> 1) & 0x55555555)

由于位奇偶校验被移位反转，我只需要交换常量 0x55555555 和 0xaaaaaaaa。

为了在二进制的两边获得相同的常量，或者，我 select 在一侧移位之前，在另一侧移位之后。

Answer 2

你绝对可以摆脱代价高昂的求幂。可以进一步压缩它，但只要每个运算符都是二进制的，复杂性就保持不变。

# to keep the code readable
def swapBits(n, p1, p2): 

    ''' Move p1'th to rightmost side '''
    bit1 = (n >> p1) & 1

    ''' Move p2'th to rightmost side '''
    bit2 = (n >> p2) & 1

    ''' XOR the two bits '''
    x = (bit1 ^ bit2) 

    ''' Put the xor bit back to their  
        original positions '''
    x = (x << p1) | (x << p2) 

    ''' XOR 'x' with the original number  
        so that thetwo sets are swapped '''
    result = n ^ x 
    return result 

n = 11
print(bin(n))
k = 0
for i in range(32):
    n = swapBits(n, k, k+1)
    k+= 2

print(n)
print(bin(n))

如何改进 Python 代码以交换 32 位整数的位

How to improve Python code for swapping bits of a 32-bit integer

python

bit-manipulation

Swap bits - 编码面试问题

问题：

我的解决方案：

我要问你的问题：