1、位运算

一、基本概念

位运算是用来操作二进制的。

python中一共有六中位运算的操作符。二进制在python中表示为”0b”。例如 a = 0b100110。bin函数可以把十进制转化为二进制数。

&与

如果两个二进制相同位数为1，返回1，否则为0

|或

如果两个二进制相同位数至少有一个1，则返回的数字的二进制在该位置值也为1，否则为0。

^ 异或

简单理解就是非进位相加，相同为0，不同为1

异或运算有很多的技巧，首先就是

• 异或运算就是无进位相加

• 满足交换律，即 a ^ b = b ^ a，也就是异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终的结果都是一个。

• 相同两个数异或为0 ，即 a ^ a = 0，0异或一个数为那个数本身，即 0 ^ a = a。

• 整体异或和如果是x，整体中某个部分的异或和如果是y，那么剩下部分的异或和是x^y

~ 取反

将数字转化为二进制后，数字前加一个负号，二进制加1，再返回变换后二进制对应的数。

~a = -(a+1)所以-a=~a+1

<< 左移

将数字转化为二进制后，向二进制里添加几个零（取决于左移的位数），再返回变换后二进制对应的数。

a = 2
a << 1# 等于 2**2

>>右移

将数字转化为二进制后，将二进制里最后面的几个数剔除（取决于右移的位数），再返回变换后二进制对应的数。

二、常用技巧

袋子里一共a个白球，b个黑球，每次从袋子里拿2个球，每个球每次被拿出机会均等如果拿出的是2个白球、或者2个黑球，那么就往袋子里重新放入1个白球如果拿出的是1个白球和1个黑球，那么就往袋子里重新放入1个黑球那么最终袋子里一定会只剩1个球，请问最终的球是黑的概率是多少?用a和b来表达这个概率。

答案:
黑球的数量如果是偶数，最终的球是黑的概率是0%

黑球的数量如果是奇数，最终的球是黑的概率是100%完全和白球的数量无关。

1、打印32位的二进制的数字

def print_binary(num):
    result = ''
    for i in range(32, 0, -1):
        result += str('0' if num & (1 << i) == 0 else '1')
    print(len(result))


print_binary(10)

2、交换顺序, a需要不等于b

a = 1
b = 2
a = a ^ b  # a ^ b
b = a ^ b  # a ^ b ^ b 
a = a ^ b  # a ^ b ^ a ^ b ^ b 

print(a, b)

3、面试题 17.04. 消失的数字

# 数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        all_num = 0
        has_num = 0
        for i in range(len(nums) + 1):
            all_num ^= i
        for num in nums:
            has_num ^= num
        return all_num ^ has_num

4、判断奇数偶数

a = 1
a & 1 == 1
b = 2
b $ 1 == 0

5、找到右边第一个为1的数字

right = num & (-num)

三、经典题目

面试题 17.04. 消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

**注意：**本题相对书上原题稍作改动

示例 1：

输入：[3,0,1]
输出：2

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8

思路：

任何数^{本身都是0，我们先把0-n之间的所有数都}一遍，得到a1^a2^a3...^an

再把数组中所有的数^{一遍，再把两个结果进行},就得到缺失的数

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        temp1 = 0
        temp2 = 0
        for i in range(len(nums)+1):
            temp1 ^= i
        for num in nums:
            temp2 ^= num
        
        return temp1 ^ temp2

136. 只出现一次的数字

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

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

示例 3 ：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

思路一

任何数字^本身都是0，那么出现偶数的数字异或结果都会是0，留下来的数字就会是那个出现一次的数字

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

思路二

题目给定的是一个数组，那么我们是不是可以先进行排序，每次跳跃两个索引，如果当前索引和下一个索引不一致那么它就是不同的数字

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # result = 0
        # for num in nums:
        #     result ^= num
        # return result
        nums.sort()
        nums.append(float('inf'))# 我们加个一个元素就是防止越界
        for i in range(1, len(nums), 2):
            if nums[i-1] != nums[i]:
                return nums[i-1]

137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

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

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

思路一：

和上题一致

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        nums.append(float("inf"))
        for i in range(1, len(nums), 3):
            if i > 0 and nums[i] != nums[i - 1]:
                return nums[i - 1]

思路二：

这个题和上一题相比就差别比较大了

上题是有偶数个，求出现一次的数，本题是都是出现了奇数个，求出现一次的个数

我们可以统计每个数在32位下1的出现个数，然后除以3，看那个数字不是3的倍数，在使用或|运算计算每位1的影响值

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = [0] * 32
        # 统计每个数32位下出现的个数
        for num in nums:
            for i in range(32):
                count[i] += (num >> i) & 1

        result = 0
        for i in range(32):
            if count[i] % 3 != 0:
                if i == 31:
                    # 这个判断条件是因为Python的特殊性
                    result -= 1 << i
                else:
                    # 使用或|运算计算每位1对于结果的影响值
                    result = result | 1 << i
        return result

260. 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路：

当我们发现出现了偶数次我们第一反应就是使用^{,因为可以消除掉偶数次数的影响，那么把结果全部都}完得到的就是那两个不同的数a^b

得到a^b之后，我们如何得到a和b不同的数呢？

• 由于a和b不相同，所以啊a^b一定有一，所以我们可以得出其中一个数最右边一定不为1，另外一个最右边一定是1

• 我们可以获取到右边第一个不为一的数right_one =（num & (-num)）

• 我们将数组中所有的数字都和右边第一个不为一的数进行&运算，当num & right_one == 0,代表着这里面一定有a或b其中一个

• 所以我们在和a^b进行运算即可消除

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        num1 = 0
        for num in nums:
            num1 ^= num
        
        right_one = num1 & (-num1)
        # print(right_one)
        num2 = 0
        for num in nums:
            if num & right_one:
                num2 ^= num

        return [num2, num1 ^ num2]

2595. 奇偶位数

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。请注意，在数字的二进制表示中，位下标的顺序 从右到左。返回整数数组 answer ，其中 answer = [even, odd] 。

示例 1：

**输入：**n = 50

输出：[1,2]

**解释：**50 的二进制表示是 110010。在下标 1，4，5 对应的值为 1。

示例 2：

**输入：**n = 2

输出：[0,1]

**解释：**2 的二进制表示是 10。只有下标 1 对应的值为 1。

提示：

• 1 <= n <= 1000

思路：

把n当成一个二进制数来遍历。

遍历的顺序是从低位到高位。具体来说，通过n & 1取二进制的最低位，然后把n右移一位，继续计算n & 1，这样可以取到次低位。如此循环，直到n=0为止。

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        ans = [0, 0]
        i = 1
        while n:
            ans[i] += n & 1
            n >>= 1
            i ^= 1
        return ans