關于Python 位運算防坑指南

更新時間：2021年09月16日 16:22:59 作者：老馬的程序人生

這篇文章主要介紹了關于Python 位運算防坑指南，小編將劇烈向大家說明并且列舉python及C#兩種語言,需要的朋友可以參考下面文章的具體內容

1、背景

我們先看這個題目：

標題：137. 只出現一次的數字 II
難度：中等
https://leetcode-cn.com/problems/single-number-ii/

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現了三次。找出那個只出現了一次的元素。

說明：

你的算法應該具有線性時間復雜度。你可以不使用額外空間來實現嗎？

示例 1:

輸入: [2,2,3,2]
輸出: 3

示例 2:

輸入: [0,1,0,1,0,1,99]
輸出: 99

思路：

初始result = 0，將每個數想象成 32 位的二進制，對于每一位的二進制的1累加起來必然是3N或者3N + 1(出現3次和1次)；3N代表目標值在這一位沒貢獻，3N + 1代表目標值在這一位有貢獻（=1），然后將所有有貢獻的位記錄到result中。這樣做的好處是如果題目改成k個一樣，只需要把代碼改成count % k即可，很通用并列去找每一位。

2、C# 語言

執(zhí)行結果：通過
執(zhí)行用時：112 ms, 在所有 C# 提交中擊敗了 91.53% 的用戶
內存消耗：25.2 MB, 在所有 C# 提交中擊敗了 100.00% 的用戶

public class Solution
{
    public int SingleNumber(int[] nums)
    {
        int result = 0;
        for (int i = 0; i < 32; i++)
        {
            int mask = 1 << i;
            int count = 0;
            for (int j = 0; j < nums.Length; j++)
            {
                if ((nums[j] & mask) != 0)
                { 
                    count++;
                }
            }
            if (count % 3 != 0)
            {
                result |= mask;
            }
        }
        return result;
    }
}

3、Python 語言

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for i in range(32):
            mask = 1 << i
            count = 0
            for num in nums:
                if num & mask != 0:
                    count += 1
            if count % 3 != 0:
                result |= mask
        return result

以上 Python 代碼與 C# 代碼邏輯完全一致，但提交時報錯。錯誤信息如下：

輸入：[-2,-2,1,1,-3,1,-3,-3,-4,-2]
輸出：4294967292
預期結果：-4

我們發(fā)現：

-4 補碼為 1111 1111 1111 1111 1111 1111 1111 1100

如果不考慮符號位

1111 1111 1111 1111 1111 1111 1111 1100 -> 4294967292

是不是很坑，C++，C#，Java等語言的整型是限制長度的，如：byte 8位，int 32位，long 64位，但 Python 的整型是不限制長度的（即不存在高位溢出），所以，當輸出是負數的時候，會導致認為是正數！因為它把32位有符號整型認為成了無符號整型，真是坑。

我們對以上的代碼進行修改，加入判斷條件 if result > 2 ** 31-1: 超過32位整型的范圍就表示負數了result -= 2 ** 32，即可得到對應的負數。

執(zhí)行結果：通過
執(zhí)行用時：96 ms, 在所有 Python3 提交中擊敗了 19.00% 的用戶
內存消耗：14.8 MB, 在所有 Python3 提交中擊敗了 25.00% 的用戶

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for i in range(32):
            mask = 1 << i
            count = 0
            for num in nums:
                if num & mask != 0:
                    count += 1
            if count % 3 != 0:
                result |= mask
            if result > 2 ** 31-1:
                result -= 2 ** 32
        return result

4、技術分析

上面的問題解決了，我們在深入的探討一下。

整數在內存中是以補碼的形式存在的，輸出自然也是按照補碼輸出。

class Program
{
    static void Main(string[] args)
    {
        string s1 = Convert.ToString(-3, 2);
        Console.WriteLine(s1); 
        // 11111111111111111111111111111101
        
        string s2 = Convert.ToString(-3, 16);
        Console.WriteLine(s2); 
        // fffffffd
    }
}

但我們看一下 Python 的bin() 輸出。

print(bin(3))  # 0b11
print(bin(-3))  # -0b11

print(bin(-3 & 0xffffffff))  
# 0b11111111111111111111111111111101

print(bin(0xfffffffd))       
# 0b11111111111111111111111111111101

print(0xfffffffd)  # 4294967293

是不是很顛覆認知，我們從結果可以看出：