1、背景

我們先看這個(gè)題目：

標(biāo)題：137. 只出現(xiàn)一次的數(shù)字 II
難度：中等
https://leetcode-cn.com/problems/single-number-ii/

給定一個(gè) 非空 整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)了三次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

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

示例 2:

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

思路：

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

2、C# 語言

• 執(zhí)行結(jié)果：通過
• 執(zhí)行用時(shí)：112 ms, 在所有 C# 提交中擊敗了 91.53% 的用戶
• 內(nèi)存消耗：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# 代碼邏輯完全一致，但提交時(shí)報(bào)錯(cuò)。錯(cuò)誤信息如下：

輸入：[-2,-2,1,1,-3,1,-3,-3,-4,-2]
輸出：4294967292
預(yù)期結(jié)果：-4

我們發(fā)現(xiàn)：

-4 補(bǔ)碼為 1111 1111 1111 1111 1111 1111 1111 1100

如果不考慮符號(hào)位

1111 1111 1111 1111 1111 1111 1111 1100 -> 4294967292

是不是很坑，C++，C#，Java等語言的整型是限制長度的，如：byte 8位，int 32位，long 64位，但 Python 的整型是不限制長度的（即不存在高位溢出），所以，當(dāng)輸出是負(fù)數(shù)的時(shí)候，會(huì)導(dǎo)致認(rèn)為是正數(shù)！因?yàn)樗?2位有符號(hào)整型認(rèn)為成了無符號(hào)整型，真是坑。

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

• 執(zhí)行結(jié)果：通過
• 執(zhí)行用時(shí)：96 ms, 在所有 Python3 提交中擊敗了 19.00% 的用戶
• 內(nèi)存消耗：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、技術(shù)分析

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

整數(shù)在內(nèi)存中是以補(bǔ)碼的形式存在的，輸出自然也是按照補(bǔ)碼輸出。

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

是不是很顛覆認(rèn)知，我們從結(jié)果可以看出：

• Python中bin一個(gè)負(fù)數(shù)（十進(jìn)制表示），輸出的是它的原碼的二進(jìn)制表示加上個(gè)負(fù)號(hào)，巨坑。
• Python中的整型是補(bǔ)碼形式存儲(chǔ)的。
• Python中整型是不限制長度的不會(huì)超范圍溢出。
  

所以為了獲得負(fù)數(shù)（十進(jìn)制表示）的補(bǔ)碼，需要手動(dòng)將其和十六進(jìn)制數(shù)0xffffffff進(jìn)行按位與操作，再交給bin()進(jìn)行輸出，得到的才是負(fù)數(shù)的補(bǔ)碼表示。

總結(jié)：
這篇圖文從一道Leetcode題目開始說起，發(fā)現(xiàn)C#語言與Python語言在利用二進(jìn)制處理整型數(shù)據(jù)時(shí)存在不同，Python語言不屬于強(qiáng)類型語言所以不限制整型的位數(shù)，表面上看好像方便使用其實(shí)就是個(gè)坑。大家使用時(shí)多加小心。

到此這篇關(guān)于關(guān)于Python 位運(yùn)算防坑指南的文章就介紹到這了,更多相關(guān)Python 位運(yùn)算防坑指南內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論