关于Python位运算防坑指南

背景

我们先看这个题目:

  • 标题: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即可,很通用并列去找每一位。

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;
    }
}

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

技术分析

上面的问题解决了,我们在深入的探讨一下。

整数在内存中是以补码的形式存在的,输出自然也是按照补码输出。

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

是不是很颠覆认知,我们从结果可以看出:

  1. Python中bin一个负数(十进制表示),输出的是它的原码的二进制表示加上个负号,巨坑。
  2. Python中的整型是补码形式存储的。
  3. Python中整型是不限制长度的不会超范围溢出。

所以为了获得负数(十进制表示)的补码,需要手动将其和十六进制数0xffffffff进行按位与操作,再交给bin()进行输出,得到的才是负数的补码表示。


总结

这篇图文从一道Leetcode题目开始说起,发现C#语言与Python语言在利用二进制处理整型数据时存在不同,Python语言不属于强类型语言所以不限制整型的位数,表面上看好像方便使用其实就是个坑。大家使用时多加小心。好了今天就到这里吧,See You。

收藏 (0)
评论列表
正在载入评论列表...
我是有底线的
为您推荐
    暂时没有数据