1、背景

我們先看這個題目：

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

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

說明：

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

示例 1:

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

示例 2:

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

思路：

初始result = 0，將每個數(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個一樣，只需要把代碼改成count % k即可，很通用并列去找每一位。

2、C# 語言

• 執(zhí)行結(jié)果：通過
• 執(zhí)行用時：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# 代碼邏輯完全一致，但提交時報錯。錯誤信息如下：

輸入：[-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

如果不考慮符號位

1111 1111 1111 1111 1111 1111 1111 1100 -> 4294967292

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

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

• 執(zhí)行結(jié)果：通過
• 執(zhí)行用時：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一個負(fù)數(shù)（十進(jìn)制表示），輸出的是它的原碼的二進(jìn)制表示加上個負(fù)號，巨坑。
• Python中的整型是補(bǔ)碼形式存儲的。
• Python中整型是不限制長度的不會超范圍溢出。
  

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

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

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

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。