關(guān)于Python 位運(yùn)算防坑指南
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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python跑循環(huán)時(shí)內(nèi)存泄露的解決方法
這篇文章主要介紹了Python跑循環(huán)時(shí)內(nèi)存泄露的解決方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01Python開發(fā)之QT解決無邊框界面拖動(dòng)卡屏問題(附帶源碼)
朋友在學(xué)習(xí)QT的過程中,都會(huì)遇到各種問題,今天就QT無邊框拖動(dòng)花屏問題給大家詳細(xì)介紹,究竟該如何解決呢,下面通過實(shí)例代碼和圖文相結(jié)合給大家詳細(xì)介紹,需要的朋友參考下吧2021-05-05python 將dicom圖片轉(zhuǎn)換成jpg圖片的實(shí)例
今天小編就為大家分享一篇python 將dicom圖片轉(zhuǎn)換成jpg圖片的實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01Django模板繼承與模板的導(dǎo)入實(shí)例詳解
模板繼承主要是為了提高代碼重用,減輕開發(fā)人員的工作量,下面這篇文章主要給大家介紹了關(guān)于Django模板繼承與模板導(dǎo)入的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-03-03Python?matplotlib繪圖時(shí)指定圖像大小及放大圖像詳解
Matplotlib是一個(gè)面向?qū)ο蟮睦L圖庫,我們繪制的圖像中,每條曲線,每個(gè)邊框等等都對應(yīng)一個(gè)對象,下面這篇文章主要給大家介紹了關(guān)于Python?matplotlib繪圖時(shí)指定圖像大小及放大圖像的相關(guān)資料,需要的朋友可以參考下2022-05-05python獲取外網(wǎng)IP并發(fā)郵件的實(shí)現(xiàn)方法
下面小編就為大家?guī)硪黄猵ython獲取外網(wǎng)IP并發(fā)郵件的實(shí)現(xiàn)方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-10-10