当前位置：首页 > 编程日记 > 正文

技术图文：Python 位运算防坑指南

编程日记 2024-09-25 15:30:00

背景

我们先看这个题目：

标题：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 = 0for i in range(32):mask = 1 << icount = 0for num in nums:if num & mask != 0:count += 1if count % 3 != 0:result |= maskreturn 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 = 0for i in range(32):mask = 1 << icount = 0for num in nums:if num & mask != 0:count += 1if count % 3 != 0:result |= maskif result > 2 ** 31-1:result -= 2 ** 32return result

技术分析

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

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

class Program
{static void Main(string[] args){string s1 = Convert.ToString(-3, 2);Console.WriteLine(s1); // 11111111111111111111111111111101string s2 = Convert.ToString(-3, 16);Console.WriteLine(s2); // fffffffd}
}

但我们看一下 Python 的bin() 输出。

print(bin(3))  # 0b11
print(bin(-3))  # -0b11print(bin(-3 & 0xffffffff))  
# 0b11111111111111111111111111111101print(bin(0xfffffffd))       
# 0b11111111111111111111111111111101print(0xfffffffd)  # 4294967293

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

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

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

总结

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

参考文献

https://oi-wiki.org/math/bit/
https://www.zhihu.com/question/314455297

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

Python基础刻意练习活动即将开启，你参加吗？
Task01：变量、运算符与数据类型
Task02：条件与循环
Task03：列表与元组
Task04：字符串与序列
Task05：函数与Lambda表达式
Task06：字典与集合
Task07：文件与文件系统
Task08：异常处理
Task09：else 与 with 语句
Task10：类与对象
Task11：魔法方法
Task12：模块

我是终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：

https://www.dkcj.cn/info/20289.html

技术图文：Python 位运算防坑指南

背景

技术分析

总结

相关文章：

聊聊nginx报错499问题

UI设计需要报培训班学习吗

技术图文：位运算技术在求解算法题中的应用

JavaScript学习系列6 充实文档的内容

mapreduce中设置自定义的输入类,进行文本解析(默认以tab键为分隔符)

如何分辨Web前端培训机构的好坏

mysql dba系统学习（19）配置mysql+lvs+keeplived实现Mysql读操作的负载均衡

技术图文：浅析 C# Dictionary实现原理

思念水饺吃成泡沫水饺（图）思念质量门

jQuery动画的显示与隐藏效果

技术图文：字典技术在求解算法题中的应用

[WCF REST] 解决资源并发修改的一个有效的手段：条件更新（Conditional Update）

Netty 之 Zero-copy 的实现（下）

Java中final关键字如何使用?

技术图文：双指针在求解算法题中的应用

【CSON原创】HTML5游戏框架cnGameJS开发实录（外部输入模块篇）

中国科协（深圳）海外人才离岸创新创业基地源创力中心开业，主打国际创业服务...

找java培训机构如何挑选

技术图文：集合技术在求解算法题中的应用

sql server 2008数据导入Oracle方法

nginx+tomcat配置负载均衡集群

参加UI设计培训要学多久

技术图文：C# 语言中的扩展方法

如何在ToolBar中显示文字和图标,自定义图标大小,并和MenuItem关联

C#程序调用cmd执行命令

Java虚拟机的内存空间有几种

技术图文：排序技术在求解算法题中的应用

如果有电脑——计算机达人成长之路（36）

Javascript中二进制数据处理方法

正规Java培训机构是什么样的