专栏首页用户6811391的专栏Python 刷题笔记:位运算专题一

Python 刷题笔记:位运算专题一

学 Python 初接触 &、| 等运算符时,只大概了解它们被称为位运算符,并不同于逻辑运算符 and、or,今天就通过基础知识点和几道题目来熟悉下。

知识点

我们都知道所有数值在计算机底层是以二进制形式存在的,首先要明确几个概念:

  • 原码:直接将一个数值转化为二进制,其首位代表符号,0 为正 1 为负
  • 反码:最高位符号位不变,其余为取反,即 1 变 0、0 变 1
  • 补码:正数的补码与原码相同;负数的补码为其反码 +1

以正数 4 和负数 -5 为例,其 32 位二进制形式如下:

关键点来了,我们接下来要接触的「位运算符,都是对数字的补码进行运算的」!这就是我们自己测试时,正数间的位运算看着都挺正常,但一涉及到负数就老不按预想走。

接下来我们看常用的运算符:

我们运行下示例:

示例位运算结果

结合着之前 4 和 -5 的补码,就很容易理解 ~ 4 值为何是 -5 了。

当然,这只是最基础的位运算,当具体到特定情景时,位运算有很多妙用,我们就在题目中去体会学习吧!

题目

第 371 题:两整数之和

难度:简单

不使用运算符 + 和 - ,计算两整数 a 、b 之和。

示例 1:
输入: a = 1, b = 2
输出: 3

示例 2:
输入: a = -2, b = 3
输出: 1

位运算技巧

这里的解释说明我直接选用精选题解,还是容易理解的:

题解来源:https://leetcode-cn.com/problems/sum-of-two-integers/solution/wei-yun-suan-xiang-jie-yi-ji-zai-python-zhong-xu-y/

位运算中两数加法情况如下:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0(进位 1)

恰好与「按位异或」基本一致,但却缺少进位,例如 5 + 4:

a = 5 = 0101
b = 4 = 0100

a ^ b 如下:

0 1 0 1
0 1 0 0
-------
0 0 0 1

a ^ b 得到了一个无进位加法结果,如果要得到 a + b 的最终值,我们还要找到进位的数,把这二者相加。在位运算中,我们可以使用与操作获得进位:

a = 5 = 0101
b = 4 = 0100

a & b 如下:

0 1 0 1
0 1 0 0
-------
0 1 0 0

由计算结果可见,0100 并不是我们想要的进位,1 + 1 所获得的进位应该要放置在它的更高位,即左侧位上,因此我们还要把 0100 左移一位,才是我们所要的进位结果:a & b << 1

此时,将上述两结果“相加”即可得到最终结果,但是,我们没有加号,所以要对上述两结果重复类似运算,直到最后无需进位:

  1. a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
  2. 无进位加法使用异或运算计算得出
  3. 进位结果使用与运算和移位运算计算得出
  4. 循环此过程,直到进位为 0

此外要注意的是,Python 中整数并不是 32 位的,即 << 左移并不会导致溢出,所以需要我们要对 Python 中的整数处理来达到 32 位整型效果,具体做法是将整数对 0x100000000 (0x 代表此数是 16 进制) 取模,即超出 32 位的部分不要、设为 0。

所以上述位运算模拟的加法在 Python 中除了上述循环位运算,还要通过整数取模保证结果一直在 32 位内。

代码实现

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        # 2^32
        MASK = 0x100000000
        # 整型最大值
        MAX_INT = 0x7FFFFFFF
        MIN_INT = MAX_INT + 1
        # 进位结果若不为 0 ,一直循环执行位运算
        while b != 0:
            # 计算进位
            carry = (a & b) << 1 
            # 取余范围限制在 [0, 2^32-1] 范围内
            a = (a ^ b) % MASK
            b = carry % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)   

#作者:jalan
#链接:https://leetcode-cn.com/problems/sum-of-two-integers/solution/wei-yun-suan-xiang-jie-yi-ji-zai-python-zhong-xu-y/

结尾处的 return 语句也对其超出范围时做了特殊处理,我也找来了评论区相关的注解:

❝~((a % MIN_INT) ^ MAX_INT) 这里为什么要对负数做这样的处理呢? 因为在 Python 中 int 不是 32 位的,所以一个负数比如 -2, 其 64 位表示就是 0x00000000FFFFFFFE, 用 Python 求取这个 16 进制的值 int('0x00000000FFFFFFFE', 16), 得到的数字是 4294967294 不是我们想要的 -2,所以:(a % MIN_INT) ^ MAX_INT 是先对 a 的 32 位以外部分取反,对应 -2,就得到0x0000000000000002 再用 ~ 操作符对所以位置取反,对应 -2,得到 0xFFFFFFFFFFFFFFFE。 ❞

这里总感觉描述的不准确,后续我还要再验证下,但大致就是如果不对负数特殊处理,那么负数前面还可能存在 0,最后输出的是大于32位的正数。

结论

其实挺简单的一个运算过程,但由于 Python 中 int 没有 32 位限制,导致对数字的处理显得挺麻烦了。原本想多记录几个用法的,没成想这个最简单的加法都整理这么一堆。不过也好,一次性理清其概念,明天直接题目走起~

今天心态又爆炸,各种不顺、不爽,被血虐。。

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 零基础Python修炼笔记

    如果你从未接触过编程,那么推荐本篇中的教材资源给你。在这里对你的编码经验完全没有要求。倘若你有过编程经验,可以看下我们准备的进阶页面:

    TTTEED
  • 2019了,一起来学Python?

    我很惭愧,给了自己诸多借口,将Python学习给搁置了,一直拖到了2019年。时不我待,趁着有精力有兴趣,我要重启学习计划了。

    TTTEED
  • 给无网络的办公电脑插上 Python 小翅膀

    写在前面:本文涉及的点偏基础,主要是 Python 及 pandas 包的无网络安装,例如 whl 和 tar.gz 压缩包安装等。如有需要请继续阅读,如用不到...

    TTTEED
  • 七个神奇的网站,让你的工作效率大幅度提升~~

    今天周六了,菜鸟小白带着家里一起去游乐场玩去了,所以今天没有办法给大家分享编程小项目了,今天就给大家推荐一些非常好用的网站吧。

    菜鸟小白的学习分享
  • 量子计算机研发20年,刚进入它的“电子管时代”

    量子计算机(quantum computer)是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当某个装置处理和计算的是量子信息,运行...

    互扯程序
  • 谷歌:量子计算是深度学习的完美选择么?(12月8日将发布转折消息)

    在过去的几年里,谷歌一直在试着提升他人工智能的服务水平。谷歌恰好也有量子计算机——一个能够在某些计算上执行速度比经典计算机快的系统。 认为谷歌会把运行AI的工作...

    新智元
  • NGINX部署HTTPS

    nginx是一款高性能的Web服务器,可以用作反向代理和负载均衡。随着HTTPS的不断推进,越来越多的网站都开始转到HTTPS方式,HTTP仅仅作为重定向到HT...

    drunkdream
  • NGINX部署HTTPS

    drunkdream
  • 让视频里的你完全消失,Adobe最新SOTA模型实现无痕修图,无需先验知识

    Adobe 提出的这种新型视频修图算法可以同时修复缺失图像和移动(光流)信息,基于 Deep Image Prior(DIP)提出。DIP 利用卷积网络架构来修...

    机器之心
  • 数据库怎么存储手机号,QQ等纯数字内容,最省内存

    Python疯子

扫码关注云+社区

领取腾讯云代金券