Python实现《算法很美》位运算：奇偶数判断与异或操作应用

22 浏览量更新于2024-08-30 收藏 81KB PDF 举报

在《算法很美》一书中，Python是常用的编程语言之一，特别是对于学习和理解算法概念。本书关注点之一是位运算，这是一种基础但强大的计算机操作，用于处理二进制数据。位运算符包括"&"（位与）、 "|"（位或）和"^"（位异或），它们的工作原理如下： 1. **位与(&)**：当两个数的对应位都是1时，结果位才为1。例如，用来判断一个整数是否为奇数，通过将其与1进行位与运算，如果结果为1，说明该数为奇数，否则为偶数。如代码片段所示： ```python n = int(input()) if n & 1 == 1: print(n, "为奇数") else: print(n, "为偶数") ``` 2. **位或(|)**：只要有一个数的对应位为1，结果位就是1。可以用于检查二进制某位的状态，通过右移一位后与1进行位与运算。 3. **位异或(^)**：如果两个数的对应位相同，则结果位为0；不同则为1。这种运算常用于查找数组中的“落单”数（只出现一次的数）和“成对”数（出现两次的数）。例如，寻找数组中落单的数： ```python numlist = [1, 1, 2, 3, 4, 6, 3, 4, 2, ...] res = 0 for i in range(len(numlist)): res ^= numlist[i] print(res) # 输出的是唯一出现一次的数，如6 ``` 在这些例子中，位运算利用了二进制数的特性，简化了问题的解决过程。通过位运算，可以高效地进行逻辑判断和数据处理，尤其在处理大量二进制数据时，其优势更为明显。在学习算法时，理解并掌握位运算对于提升编程技能和解决问题的能力至关重要。《算法很美》这本书不仅提供了理论讲解，还通过实际代码展示了如何在Python中应用这些概念，是初学者和进阶者学习算法的优秀参考资料。

展开

《算法很美》《算法很美》python实现实现（位运算）（位运算）

《算法很美》《算法很美》python实现实现记录记录python算法学习算法学习

python入门，开始学习算法，通过写博客记录，总结，巩固学习成果。

代码通过python实现，学习参考资料为蓝桥学院《算法很美》

位运算位运算

位运算符号：&(位与)，|（位或），^（位异或）

&：对应数位都是1，该位运算结果才为1

|：对应数位只要有1个为1，该位运算结果就为1

^: 对应数位相同（同1 或同0），该位运算结果为1

位运算基础运用：

① 判断奇偶数

原因：将待判断的数转换为二进制数，若为奇数，二进制最后一位为1，否则，二进制最后一位为0，因此，让待判断的数和1

做位与运算，结果为1，则为奇数，反之，则为偶数。

n=int(input())

if n&1==1:

print(n,"为奇数")

else:

print(n,"为偶数")

② 获取二进制某位是0 还是1

方法：通过位移运算符，将查找某位移到最低位，和1做位与运算，结果为1，则该位为1，反之，则为0

a=13 # 1101

b=14 # 1110

#判断a ,b值对应的二进制的倒数第二位

result1=(a>>1)&1

result2=(b>>1)&1

print(result1,result2) #1 0

例题1 寻找数组中落单的数

一个数组除了某一个数字之外，其他的数字都出现了两次。请写一个程序找出这个只出现一次的数字

思路：运用异或运算

首先，明确异或运算的相关知识点

^:对应数位相同（同1 或同0），该位运算结果为1

A^A=0

A^0=A

数组=[X1,X2,X3,X4……Xn] 因为A ^ A=0，那么对该数组所有元素求异或运算，即X1^ X2^ X3^ X4^ ……^ Xn,其中出现两次的

数字Xi ^ Xj=0,最后X1^ X2^ X3^ X4^ ……^ Xn=X单^0=X单

代码如下：

numlist=[1,1,2,3,4,6,3,4,2,] #该数组落单的数字位6

res=0

for i in range(len(numlist)): #对数组所有元素进行^运算

res^=numlist[i] print(res) #输出的是6

例题2 寻找数组中成对的数

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素重复，其他的数字均只出现1次，每个数字只能访问

一次，设计一个算法，将他找出来，不用辅助储存空间

思路：同上题，运用异或运算，稍微有点小变通

A^A=0

A^0=A

若像上题所有元素进行异或运算，那么相同的那两个数结果为0，被消去，不可行。

假设成对的数为k，那么对该数组所有元素进行异或运算（1^ 2 ^ 3 ^ 4 ^ ……^ k ^ k ^ … …^ 999^1000)[1001个数] ，在和( 1 ^

2 ^ 3 ^ 4 ^ … … ^ 999 ^1000)[1000个数]进行异或运算，即（ 1 ^ 2 ^ 3 ^ 4 ^ …… ^ k ^ k ^ …… ^ 999 ^ 1000) ^ ( 1 ^ 2 ^ 3 ^ 4

^ … ^k … ^ 999 ^1000) ,那么之后成对的数多了1个，变为了3个，其位运算结果k ^ k ^ k=0 ^ k =k，其余出现一次的数成对，

其位运算结果为0，就类似例题一的情况。

代码如下：

import random

numlist1=[i for i in range(1,1001)] a=random.randrange(1,1001) #生成一个随机数

numlist1.append(a) #随机添加一个数，使得一个数成对，

res1=0

for i in range(len(numlist1)):

res1^=numlist1[i] #1^ 2 ^ 3 ^ 4 ^ ……^ k ^ k ^ … …^ 999^1000

numlist2=[j for j in range(1,1001)] res2=0

for i in range(len(numlist2)):

res1^=numlist2[i] #1 ^ 2 ^ 3 ^ 4 ^ … ^k … ^ 999 ^1000

下载后可阅读完整内容，剩余3页未读，立即下载

身份认证购VIP最低享 7 折!

30元优惠券

weixin_38567962

粉丝: 2

Python实现《算法很美》位运算：奇偶数判断与异或操作应用

RSA算法的纯Python实现（源码）

RSA算法的纯Python实现

python实现PageRank算法

Python位运算应用场景举例

python算法有哪几种算法

python换位加密算法_移位XOR的加密算法还原（python 实现）

加密算法RSA，其中包含快速模幂乘算法和大整数幂取模算法用python实现

bresenham算法python实现

python 进行位运算

机器学习算法的数学解析与python实现

最新资源