推荐|异或运算的介绍+奇技淫巧 python

问题引入1

先来一个有趣的问题：
袋子里一共n个白球，m个黑球，每次从袋子里等概率地拿2个球。
若拿出2个白球、或2个黑球，那么就往袋子里重新放入1个白球
若拿出1个白球和1个黑球，那么就往袋子里重新放入1个黑球
最终袋子里一定会只剩1个球，请问最终的球是黑的概率是多少？

答案：
黑球的数量如果是偶数，最终的球是黑的概率是0%
黑球的数量如果是奇数，最终的球是黑的概率是100%
完全和白球的数量无关。为什么？别急，了解异或运算之后，你将豁然开朗

异或运算

定义

对于两个二进制位a和b,异或运算的结果为：
如果a和b相同，则结果为0。
如果a和b不同，则结果为1。
换句话说，异或运算是“不同则为真”的逻辑运算。

在这里插入图片描述

可以理解为：不进位的相加（这个理解至关重要）

性质

1.交换律、结合律都适用
2.0 ^ n = n, n ^ n = 0
3.根据2可得，（） ^ y = x , 则（）= x ^ y

以上性质通过 异或运算<==>不进位相加的理解可以很容易推导出

解决问题

把引入的问题以异或运算的角度重新审视一下：

n个白球，m个黑球。若取白加黑则放回黑，取白白或黑黑则放回白，有没有一点异或运算的感觉在呢？
如果还没有看出来的话，再直观一点：令白球为0，黑球为1。
取0和1或者1和0，返回1；取0和0或者1和1，返回0；
即：0 ^ 1 = 1 ; 1 ^ 0 = 1 ; 1 ^ 1 = 0 ; 0 ^ 0 = 0 完全符合异或运算的真值表。
再结合性质2 ，可以发现：0 ^ n = n , 所以无论白球多少个，都不会影响最终结果。
所以当黑球为奇数个时，异或结果为1 ，剩黑球；
当黑球为偶数个时，异或结果为0，剩白球

~~很强很骚的操作，别急，还有很多~~

交换两数

两个整数a，b 实现交换

def swap(a, b):
    a = a ^ b
    b = a ^ b  # b=(a^b)^b  通过交换律得 b=a^(b^b) 通过性质2：b^b=0 a^0=a得 b=a^0 即b=a
    a = a ^ b  # 如上，同理
    return a, b   

# 示例
a, b = 5, 9
a, b = swap(a, b)
print(f"a: {a}, b: {b}")  # 输出: a: 9, b: 5

~~当然，这个方法实际上用不到，毕竟python一行代码a,b=b,a就可以解决的事情。~~
但其中异或运算的思想值得体会

回顾经典

在一个数组中，有一个数字出现了奇数次，其他所有数字都出现了偶数次。问：怎么找到这个数？

相信认真学完今天的异或运算的小伙伴们应该不难得出：
遍历数组并对所有元素进行异或运算，其结果就是要找的数。

只出现一次的数字https://leetcode.cn/problems/single-number/description/

题解code：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for i in nums:
            xor ^= i
        return xor

举一反三

~~开始上强度了~~

把题目升级一下：在一个数组中，有两个数字出现奇数次，其他所有数字都出现偶数次。怎么找到这两个数？

只出现一次的数字 III https://leetcode.cn/problems/single-number-iii/

思路分析：
令这两个数为a，b,这时候我们将整个数组异或所得到的值xor1为a ^ b 。
没问题，接下来就得考虑怎么从a ^ b 得到a和b。
首先可以明确的是：a和b是不同的两个数（如果这两个数相同不就合并为一个出现偶数次的数了吗）
那么根据异或运算的性质：a ^ b 得到的为一个二进制的数，这个二进制表示的数其中某一位一定为1。
假设第四位为1： a ^ b 是（xxxx1xxx）那么a和b一定是（xxxx0xxx）和（xxxx1xxx）【所有x不一定相同】
进一步地：原数组就可以分为两类：一类：第四位为1，另一类：第四位是0
这时候我们对这两个子数组中任意一个去进行异或运算：是不是就能得到a或b的值了呢？xor2 = a or b
另一个怎么得到呢？很简单：xor1 ^ xor2

思路对了，开始写code：

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor1 = xor2 = 0   # xor1即整个数组的xor
        for i in nums:
            xor1 ^= i
        lowbit = xor1 & -xor1
        for i in nums:
            if (i & lowbit) == 0:
                xor2 ^= i
        return [xor2, xor1 ^ xor2]

等等，那我是怎么找到 xor1(a ^ b) 中第几位为1呢？
这涉及到：Brian Kernighan 算法：提取一个二进制数字最右边的1 即lowbit
具体用法可点此进入查看

总结

异或运算（XOR，Exclusive OR）是逻辑运算中的一种，通常用符号 ^ 表示。它在计算机科学和编程中有着广泛的应用，尤其是在位操作、加密算法和数据校验等领域。

如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注谢谢

异或运算的介绍+奇技淫巧 python

目录