优秀程序员必须知道的20个位运算技巧

优秀程序员必须知道的20个位运算技巧攻略

什么是位运算？

位运算是一种对二进制数进行运算的方法，包括按位与（&），按位或（|），按位异或（^），以及取反（~）等操作。在计算机领域，位运算被广泛使用，能够有效提高程序的效率和可靠性。

为什么需要位运算？

在很多情况下，位运算比其它运算符更高效。例如，在计算机领域，位运算操作单元的大小通常为字节（8位），因此对其进行操作比较方便。此外，在一些程序中，位运算可以更方便地实现某些特定功能，例如判断奇偶性、清零或设置特定的位等。

20个位运算技巧

1. 判断奇偶性

要判断一个整数是奇数还是偶数，可以使用按位与运算符（&）来判断。如果整数的最后一位是0，则为偶数，否则为奇数。

if (n & 1):
    print("This is an odd number")
else:
    print("This is an even number")

2. 计算2的幂

如果一个整数是2的幂，则它的二进制数中有且只有一个1。使用按位与运算符（&）可以判断是否是2的幂。

if (n & (n - 1) == 0):
    print("This is a power of 2")
else:
    print("This is not a power of 2")

3. 交换两个数

使用位运算可以在不定义临时变量的情况下，交换两个数的值。

a = 5  # 二进制：0101
b = 3  # 二进制：0011
a ^= b
b ^= a
a ^= b
print(a)  # 二进制：0011，即3
print(b)  # 二进制：0101，即5

4. 取整

位运算可以进行位运算取整，相当于数学中的除法取整。

n = 15
print(n >> 1)  # 7，相当于数学中的n // 2

5. 乘以2

要实现一个整数乘以2的操作，可以通过左移运算符（<<）实现。

n = 10
print(n << 1)  # 20，相当于数学中的n * 2

6. 除以2

要实现一个整数除以2的操作，可以通过右移运算符（>>）实现。

n = 10
print(n >> 1)  # 5，相当于数学中的n // 2

7. 取绝对值

对于一个32位带符号整数，可以通过位运算计算它的绝对值。先将这个数与0x80000000进行异或运算，然后再加上0x80000000，即可得到它的绝对值。

n = -10
abs_value = (n ^ 0x80000000) + 0x80000000
print(abs_value)  # 10

8. 取反

运用异或运算可以实现高效地取反操作。

n = 10
print(~n)  # -11，相当于数学中的-(n + 1)

9. 取模

如果一个整数n是2的幂，则将n对2的幂-1取模可以实现和n取模相同的效果。

n = 16
print(n % 15)  # 1，相当于n % (2的幂-1)

10. 判断整数的符号

通过位运算可以判断一个整数的符号。如果一个整数的最高位为1，则它为负数；如果为0，则为正数。

n = -10
if n & 0x80000000:
    print("This is a negative number")
else:
    print("This is a positive number")

11. 求最大值

通过位运算可以求出多个整数中的最大值。

a = 10
b = 15
max_value = a ^ ((a ^ b) & -(a < b))
print(max_value)  # 15

12. 求最小值

通过位运算可以求出多个整数中的最小值。

a = 10
b = 15
min_value = b ^ ((a ^ b) & -(a < b))
print(min_value)  # 10

13. 求平均值

通过位运算可以求出多个整数的平均值，相当于数学中的整数除法的结果。

a = 10
b = 15
avg_value = (a + b) >> 1
print(avg_value)  # 12，相当于(a + b) // 2

14. 求异或和

通过位运算可以求出多个整数的异或和。

a = 10
b = 15
xor_sum = a ^ b
print(xor_sum)  # 5，相当于a ^ b

15. 从低位到高位获取位

通过位运算可以获取一个整数的二进制表示中某个位的值。

n = 10  # 二进制：1010
print(n & 1)        # 0，第0位的值为0
print((n >> 1) & 1) # 1，第1位的值为1
print((n >> 2) & 1) # 0，第2位的值为0
print((n >> 3) & 1) # 1，第3位的值为1

16. 清零

将一个整数的某些位清零，可以通过与一个全为1、要清零的位为0的整数进行按位与运算来实现。

n = 10  # 二进制：1010
n &= ~(1<<2)  # 清零第2位
print(n)      # 二进制：1000，即8

17. 设置位

将一个整数的某些位设置为1，可以通过与一个全为0、要设置的位为1的整数进行按位或运算来实现。

n = 10  # 二进制：1010
n |= (1<<2)  # 将第2位设置为1
print(n)     # 二进制：1010，即10

18. 判断是否为2的幂

通过位运算可以判断一个整数是否为2的幂。如果一个整数n是2的幂，则n & (n - 1)的结果为0。

n = 16
if (n & (n - 1) == 0):
    print("This is a power of 2")
else:
    print("This is not a power of 2")

19. 求补码

求补码可以通过将一个整数取反并加1来实现。

n = -10
complement_value = ~n + 1
print(complement_value)  # 10

20. 获取整数的二进制表示中1的个数

获取一个整数的二进制表示中1的个数，可以通过循环计算每个二进制位是否为1来实现。也可以使用Brian Kernighan算法来实现。

n = 10  # 二进制：1010
count = 0
while n:
    n &= (n - 1)
    count += 1
print(count)  # 二进制中1的个数为2

结语

位运算作为一种高效的运算方法，在计算机领域得到广泛应用。掌握这20个位运算技巧，将提高程序员的编码能力和效率。