Python 位运算防坑指南
老马的程序人生 人气:01、背景
我们先看这个题目：
标题：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# 语言
- 执行结果：通过
- 执行用时：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
我们发现：
-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，即可得到对应的负数。
- 执行结果：通过
- 执行用时：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
是不是很颠覆认知，我们从结果可以看出：
Python中bin一个负数（十进制表示），输出的是它的原码的二进制表示加上个负号，巨坑。Python中的整型是补码形式存储的。Python中整型是不限制长度的不会超范围溢出。
所以为了获得负数（十进制表示）的补码，需要手动将其和十六进制数0xffffffff进行按位与操作，再交给bin()进行输出，得到的才是负数的补码表示。
总结：
这篇图文从一道Leetcode题目开始说起，发现C#语言与Python语言在利用二进制处理整型数据时存在不同，Python语言不属于强类型语言所以不限制整型的位数，表面上看好像方便使用其实就是个坑。大家使用时多加小心。
加载全部内容