专栏首页用户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
  • Python 刷题笔记:贪心算法专题一

    LeetCode 每月都会搞每日一题活动,昨天的题目是贪心算法类型,折腾好久才做出来,索性今天就围绕贪心算法多看几道。

    TTTEED
  • Python 刷题笔记:贪心算法专题二

    最近我们开始练习贪心算法的题目,昨天因为卡在其中一道简单级别的题目上没能更新,今天补更,正好也借着卡的点分享下经验。关于贪心算法的介绍,如果想回顾,可以点上篇来...

    TTTEED
  • Python 刷题笔记:贪心算法专题三

    今天仍旧是贪心算法的题目,加上之前两篇的四道题,对贪心算法的应用也大致有些印象了,明天换个其它类型题目来继续刷。

    TTTEED
  • Python 刷题笔记:二叉树专题一

    今天来看二叉树专题,首先我们先整理下基础知识点;基于在 LeetCode 推荐题解中发现的一个适用于二叉树遍历的套路解法,我们今天也会连刷三道关于前序、中序和后...

    TTTEED
  • Python 刷题笔记:二叉树专题二

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

    TTTEED
  • Python 刷题笔记:数组专项练习一

    昨天是刷题的第 25 天,基本保持了每天一两道,同步分享了其中前 35 题的记录。通过二十多天的摸索,慢慢熟悉 LeetCode 平台,为了提高刷题学习效率,我...

    TTTEED
  • 《剑指 offer》刷题记录之:位运算

    位运算是把数字用二进制表示之后,对每一位上 0 或者 1 的运算。位运算总共包括以下 5 种:

    口仆
  • Python 刷题笔记:深度优先搜索专题

    今天来接触下专业术语——深度优先搜索算法(英语:Depth-First-Search,DFS)

    TTTEED
  • Python 刷题笔记:广度优先搜索专题

    昨天看过了简单题汇聚的深度优先搜索专题,今天来体验下简单级别的广度优先搜索专题。老样子,先熟悉下术语概念:

    TTTEED
  • Python 刷题笔记:随缘题目

    给定一个 m x n 的字符矩阵和字符串 s,在矩阵中每次只能横向、纵向移动一步,不能超出矩阵范围,问:是否可以由矩阵中拼接出 s?

    TTTEED
  • Python 刷题笔记:背包问题

    刷动态规划的第二天,有些自闭,刚靠着大魔王的歌缓过来了。关于动态规划,我还处于看题解时哦哦哦、看题目时???的阶段,所以整理的点不深。除了昨天推给大家的链接,今...

    TTTEED
  • 第二轮 Python 刷题笔记一:数组

    经过四十多天缓慢的刷题,现在进度大概是刷了八十多道 LeetCode 题,最近也在吸取过来人的经验,仍然需要对刷题计划进行调整。

    TTTEED
  • Python 刷题笔记:一道简单级的动态规划题

    今天翻看了关于时间复杂度、空间复杂度的文章和视频,对其认知加深了些,之后也要养成分析复杂度的习惯,顺手添加,大家如果看到我写错的还望予以纠正。

    TTTEED
  • OJ刷题记录:一元多项式的运算 题目编号:463

    题目要求: 已知一元多项式:A(x)=a0+a1x+a2x2+a3x3+….anxn, B(x)= b0+b1x+b2x2+b3x3+….bmxm设计算法实现...

    英雄爱吃土豆片
  • OJ刷题记录:集合的运算 题目编号:456

    题目要求: 已知A和B均是由整型数据组成的集合,使用线性表表示集合,设计算法求集合A、B的交集和并集,功能包括输入集合A,输入集合B,求A和B的并集,求A和B...

    英雄爱吃土豆片
  • 专题 | Python编写渗透工具学习笔记一

    目录&基础知识 0x00 Python编程中一些模块的简单介绍(基础知识) 0x01web目录扫描程序 --脚本代码的实现和分析 --优化脚本 0x02实现一个...

    安恒网络空间安全讲武堂
  • 神了!无意中发现一位大佬1500道的LeetCode算法刷题pdf笔记!

    昨晚逛GitHub,无意中看到一位大佬的算法刷题笔记,感觉发现了宝藏!有些小伙伴可能已经发现了,但咱这里还是忍不住安利一波,怕有些小伙伴没有看到。

    java进阶架构师
  • Python 版 LeetCode 刷题笔记 #7 整数反转

    今天迎来了个简单难度的题目,在经历一番中等难度题目的洗礼后,情不自禁露出吊打小朋友的微笑,感觉今天可以多做几道。

    TTTEED

扫码关注云+社区

领取腾讯云代金券