关于Python 位运算防坑指南
作者:老马的程序人生 发布时间:2022-06-13 08:06:55
目录
1、背景
2、C# 语言
3、Python 语言
4、技术分析
1、背景
我们先看这个题目:
标题: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语言不属于强类型语言所以不限制整型的位数,表面上看好像方便使用其实就是个坑。大家使用时多加小心。
来源:https://lsgogroup.blog.csdn.net/article/details/105716738
猜你喜欢
- SQL Server通常都运行在多处理器的服务器上,这一点在现在尤为普遍。原因是多内核的处理器越来越普及。那么,在多处理器环境下,Windo
- 一、前言这里我先为大家提供一个中文网站,大家可以下去更深入的学习。https://pypi.org/project/pypinyin/pyp
- 你知道(X)HTML中最多余的标签中是什么吗?在我看来就是这个<a>标签,不错,就是每个网站使用最多的超级链接标签<a&g
- 前言:泛型是静态类型语言的基本特征,允许将类型作为参数传递给另一个类型、函数、或者其他结构。TypeScript 支持泛型作为将类型安全引入
- 有些使用Z-Blog的用户询问我,怎么实现我的月光博客首页上这种自动图文混排的版式效果,今天我就详细介绍一下在Z-Blog中实现这种图文混排
- K线图概念股市及期货市bai场中的K线图的du画法包含四个zhi数据,即开盘dao价、最高价、最低价zhuan、收盘价,所有的shuk线都是
- 构思学生管理系统 应该包含老师注册登录 管理学生信息(增删改查)还有数据持久化因为数据存入JSON文件 增删改查都需要读取和修改文件所以需要
- python可以在处理各种数据时,如果可以将这些数据,利用图表将其可视化,这样在分析处理起来,将更加直观、清晰,以下是 利用 PyEchar
- 前言大家好,我是辣条相信大家都能感觉到最近天气的多变,好几次出门半路天气转变。辣条也深受其扰,直接给我整感冒,就差被隔离起来了,既然天气我没
- 本文实例讲述了Flask教程之重定向与错误处理。分享给大家供大家参考,具体如下:Flask类有一个redirect()方法. 当我们调用它时
- 一、简介提取图片的边缘信息是底层数字图像处理的基本任务之一。边缘信息对进一步提取高层语义信息有很大的影响。大部分边缘检测算法都是上个世纪的了
- 本文实例讲述了Python实现配置文件备份的方法。分享给大家供大家参考。具体如下:这里平台为Linux:#!/usr/bin/python#
- 正文:本文展示一些高级的Python设计结构和它们的使用方法。在日常工作中,你可以根据需要选择合适的数据结构,例如对快速查找性的
- home.html:<!DOCTYPE html><html lang="en"><hea
- 如下所示:list = [5,6,7,9,1,4,3,2,10]list.index(9)out:3同时可以返回列表中最大值的索引list.
- import 机制功能Python 的 import 机制基本上可以切分为三个不同的功能:Python运行时的全局模块池的维护和搜索;解析与
- 注意:本示例仅供学习参考~混淆原理出于某种原因,明文信息通过自定义字体进行渲染,达到混淆目的。举个例子:网页源码 <p>123&
- 微信(WeChat) 是腾讯公司于2011年1月21日推出的一个为智能终端提供即时通讯服务的免费应用程序,由张小龙所带领的腾讯广州研发中心产
- 1.如何让计算机自动判断一张图是否偏暗?或是判断一张图是否是处于夜晚?我们可以先把图片转换为灰度图,然后根据灰度值的分布来判断,如:我们可以
- 最近在一个项目中遇到一个查询页面,其中一个查询条件是根据选择的年份、月以及周数显示选择的该周从几号到几号,这样一个需求。在网上搜