计算机基础知识---位运算的应用

Author：baiyucraft

BLog： baiyucraft’s Home

前置学习：

  在了解位运算后，我们要明白一点：为什么要学习位运算呢。其实很重要的一个原因是因为位运算速度极其快，在写算法题或者程序时，将一些操作换成位运算，会大大提升程序的性能。以下就是一些位运算的应用

1.位运算实现乘除：

原理： 右移1位，相当于整除2；a左移1位，相当于乘以2

1
2
a >> n	# 将a整除2^n
a << n	# 将a乘以2^n

2.位运算判断奇偶

原理： 在二进制中，奇数的最后一位必为1，偶数的最后一位必为0，所以可以通过与1做与运算来判断奇偶

1
2
3
4
5
6
7
8
9
10
   nnnn nnnn nnnn nnn1	--- 奇数
&  0000 0000 0000 0001	--- 1
——————————————————————
   0000 0000 0000 0001	--- 1
   
   
   nnnn nnnn nnnn nnn0	--- 偶数
&  0000 0000 0000 0001	--- 1
——————————————————————
   0000 0000 0000 0000	--- 0

代码：

1
2
3
4
if a & 1:
    # 奇数
else:
    # 偶数

3.位运算交换两数

原理： 数a与数a做异或运算结果为0，数a与0做异或运算结果为a。所以位运算也能不使用临时变量交换两数，效率比普通运算高

1
2
3
4
5
6
7
8
9
10
   nnnn nnnn nnnn nnnn	--- a
^  nnnn nnnn nnnn nnnn	--- a
——————————————————————
   0000 0000 0000 0000	--- 0


   nnnn nnnn nnnn nnnn	--- a
^  0000 0000 0000 0000	--- 0
——————————————————————
   nnnn nnnn nnnn nnnn	--- a

代码：

1
2
3
4
5
6
7
8
9
10
11
# 普通运算
def swap(a, b):
    a = a + b
    b = a - b	# b = a + b - b = a
    a = a - b	# a = a + b - a = b

# 位运算
def swap(a, b):
    a = a ^ b	
    b = b ^ a	# b = b ^ a ^ b = (b ^ b) ^ a = 0 ^ a = a
    a = a ^ b	# a = a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

4.位运算求绝对值

ComputerBase
#Python #LeetCode #位运算
计算机基础知识---位运算的应用
http://baiyucraft.top/ComputerBase/ComputerBase-BitOperation-2.html
作者
baiyucraft
发布于
2021年5月22日
许可协议