python 异或的应用

Dear 丶 2022-12-09 15:54 171阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> 符号 </td> 
 <td> &nbsp;描述 </td> 
 <td> &nbsp;运算规则&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; </td> 
 </tr> 
 <tr> 
 <td> &amp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td> &nbsp;与 </td> 
 <td> 两个位都为1时，结果才为1&nbsp; &nbsp; &nbsp;（统计奇数）&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 全1为1 </td> 
 </tr> 
 <tr> 
 <td> |&nbsp;&nbsp; </td> 
 <td> &nbsp;或&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td> 两个位都为0时，结果才为0&nbsp; &nbsp; &nbsp; &nbsp;（统计偶数）&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;全0为0 </td> 
 </tr> 
 <tr> 
 <td> ^&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td> 异或 </td> 
 <td> 两个位相同为0，相异为1&nbsp; &nbsp; &nbsp; (常用统计不相同数）&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;不同为1 </td> 
 </tr> 
 <tr> 
 <td> ~&nbsp;&nbsp;&nbsp; </td> 
 <td> 取反 </td> 
 <td> 0变1，1变0 </td> 
 </tr> 
 <tr> 
 <td> &lt;&lt;&nbsp; </td> 
 <td> 左移 </td> 
 <td> 各二进位全部左移若干位，高位丢弃，低位补0 </td> 
 </tr> 
 <tr> 
 <td> &gt;&gt;&nbsp; </td> 
 <td> 右移 </td> 
 <td> 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） </td> 
 </tr> 
 </tbody> 
</table>

公式举例：

a^a = 0
            a^0 = a # 0 和谁异或就是谁
            a^b^c = a^c^b
            a&(-a)= 从右到左 出现第一个1 和 右边的0 组成的 数； 
            flag = (-a)&(a);  
            位操作：一般是将数字化为二进制数后进行操作。
            &：两个字符都为1时 结果才为1，^(异或):两个位相同为0，不同为1

作用：

1. 判断奇偶  （二进制数以1结尾是奇数，以0结尾是偶数）

for i  in range(100):  #打印所有奇数
        if i&1==1:  # 奇数 二进制 最低位 为1
            print(i)

2. 消去最后一位1

x & (x - 1)

举例：

bin(6) = '0b110'
    bin(5) = '0b101'
    bin(4) = '0b100'
    6&5 = 4 # 将 6的二进制 最后一位1 给消除（从左往右）；

3. **找出出现一次的数**

a ^ b ^ b = a

leetcode 题目:

[剑指 Offer 56 - I. 数组中数字出现的次数][Offer 56 - I.]

一个整型数组 `nums` 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

**示例 1：**

输入：nums = [4,1,4,6]
    输出：[1,6] 或 [6,1]

**示例 2：**

输入：nums = [1,2,10,4,1,4,3,3]
    输出：[2,10] 或 [10,2]

方法1:  异或的方法

class Solution:
        def singleNumbers(self, nums: List[int]) -> List[int]:
            # 异或知识点
            """
            a^a = 0
            a^0 = a # 0 和谁异或就是谁
            a^b^c = a^c^b
            a&(-a)= 从右到左 出现第一个1 和 右边的0 组成的 数； 
            flag = (-a)&(a); 
            """
            sum = 0
            i = 0
            for item in nums:
                sum = sum^item
            # print(sum)
            flag = (-sum)&(sum)  # 从右到左 出现第一个1 和 右边的0 组成的 数；
            # 分两组进行异或
            a = 0 
            b = 0
            for item in nums:  # 只有 两个 数出现 1 次， 而其他数都出现 2 次；
                if flag & item == 0:  # &与:  不太理解 
                    a = a^item
                else:
                    b = b^item
    
            return [a, b]

方法2:

class Solution:
        def singleNumbers(self, nums: List[int]) -> List[int]:
            
            nums_itr = {}
            for item in nums:
                if item in nums_itr.keys():
                    nums_itr[item] = nums_itr[item] + 1
                else:
                    nums_itr[item] = 1
            a = []
            for k, v in nums_itr.items():
                if v == 1:
                    a.append(k)
            return a

[136. 只出现一次的数字][136.]

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

**示例 1:**

输入: [2,2,1]
    输出: 1

**示例 2:**

输入: [4,1,2,1,2]
    输出: 4

解法1:   异或方法

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            # a ^ b ^ b = a
            sum = 0
            for item in nums:  # 只有一个数出现1次， 而其他数都出现 2 次；
                sum = sum^item
            return sum

解法2:  复杂度 不太符合要求

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            dirc = {}
            for item in nums:
                if item in dirc.keys():
                    dirc[item] += 1
                else:
                    dirc[item] = 1
    
            for k, v in dirc.items():
                if v == 1:
                    return k
            return False

[剑指 Offer 56 - II. 数组中数字出现的次数 II][Offer 56 - II. _ II]

在一个数组 `nums` 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

**示例 1：**

输入：nums = [3,4,3,3]
    输出：4

**示例 2：**

输入：nums = [9,1,7,9,7,9,7]
    输出：1

解法1:   不太理解的  大神解法

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            # 使用 异或 
            # a^b^c = a^c^b
            a = 0 
            b = 0
            for item in nums:
                a = (a ^ item) & (~b)  # ????
                b = (b ^ item) & (~a)
    
            return a

解法2:

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
    
            dict_nums = {}
            for item in nums:
                if item in dict_nums.keys():
                    dict_nums[item] += 1
                else:
                    dict_nums[item] = 1
            for k, v in dict_nums.items():
                if v == 1:
                    return k
            return False

参考： [python的与 或 异或 运算][python_ _ _]

[Offer 56 - I.]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
[136.]: https://leetcode-cn.com/problems/single-number/
[Offer 56 - II. _ II]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[python_ _ _]: https://blog.csdn.net/weixin_38740463/article/details/88254792