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

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

昨天笔记里对原码、反码、补码的描述有误,这里更正下:

正数三码相同,负数的反码才会除了首位符号位不变、其余位取反。位运算都是基于数字的补码来进行运算的。

昨天题目中代码结尾处有个特殊处理没来得及验证,今天细说下:

由于 Python 3 中整数是动态长度,并不是像其它语言中一般被限制到 32 位,所以通常如果涉及到复杂些的位运算,会通过整除一个 33 位的首位为 1、其余位全部为 0 的数来限制到 32 位——而这个除数在十进制中也就是 2 的 32 次方、用 16 进制则表示为 0x100000000,比如:

temp = 2**40+2
MASK = 0x100000000
result = temp%MASK

同时,32 位最小的负数为 32 位全部为 1,即十进制中的负(2 的 31 次方-1),十六进制中的负 0x7FFFFFFF,对于比其更小的数字 a, 我们昨天代码中的处理方式是 MIN_INT = 0x7FFFFFFF + 1, a%MIN_INT 即只保留 31 位,然后将结果与 0x7FFFFFFF 进行异或运算,即除了符号位全部取反,最后再按位取反,即符号位也取反,就能拿到负数结果。

比如我们对 -20 经过一番处理,仍旧可以取回 -20,但 -2「35 超出下限,就只返回 -2」31(这里貌似应该 - 1 的,之前代码中对数字是先整除 MASK 保证 32 位的,所以和这里会略有差异)

可以看到,上面这种处理方式比较绕,为了避开这操作,我们再看一份代码:

class Solution:
    def getSum(self, a: int, b: int) -> int:
    	# 将两数转化为 32 位内二进制可以表示的整数
        a &= 0xFFFFFFFF
        b &= 0xFFFFFFFF
        # 只要 b 进位不为 0 
        while b:
        	# 对两数按位与获取进位
            carry = a & b
            # 对两数按位异或获取不进位相加
            a ^= b
            # 进位左移
            b = ((carry) << 1) & 0xFFFFFFFF
		# 正数正常返回,负数单独处理
        return a if a < 0x80000000 else ~(a^0xFFFFFFFF)

#作者:lih
#链接:https://leetcode-cn.com/problems/sum-of-two-integers/solution/python-wei-yun-suan-yi-xie-keng-by-lih/

保留 32 位内有效值,直接通过 a & 0xFFFFFFFF, 也就是和 32 位的 1 来进行按位与运算,这就清晰明了太多,最后超出范围后,先进行异或运算再取反,也是相似的思路但更直接些。

我们接着看下其它题目:

题目一

「第 136 题:只出现一次的数字」

难度:简单

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

「说明:」

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

题目分析

常规操作可以建个字典统计每个元素出现次数,最后再遍历下字典中次数为 1 的值返回;

或者建个列表,当元素第一次出现时,加入到列表中,当再次遇到该元素时,从列表中删除,那么最终列表中剩下的就是结果。

再或者,我们对此列表求和,然后将其转化为集合,对集合求和再乘二,这两个数的差值即结果。

但这些思路都不满足题目中提到的「不使用额外空间」,我们来看看位运算的骚操作吧!

「位运算技巧:数字 a 与它本身按位异或结果为 0,与 0 按位异或结果为它本身,即 a ^ a = 0, a ^ 0 = a」

放到这题目里,出现两次的数字按位异或运算后为 0,那么只要把所有数接连按位异或运算一遍,结果就是只出现一次的元素了!

代码实现

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        # 遍历列表
        for i in nums:
        	# 这里是 result = result ^ i 的简写
            result ^= i
        return result

提交测试表现:

执行用时 : 40 ms, 在所有 Python3 提交中击败了 92.68% 的用户
内存消耗 : 15.3 MB, 在所有 Python3 提交中击败了 5.26% 的用户

就是这么骚气!

题目二

「第 137 题:只出现一次的数字 II」

难度:中等

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

「说明:」

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

示例 1:
输入: [2,2,3,2]
输出: 3

示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99

题目分析

这是专门针对位运算么?三次,刚我们设计的按位异或又变回该数本身了,无法甄别第一次还是第三次。

但是,我们结合着其它位运算来实现:当出现第一次时,记录结果,但出现第二次之后就不再记录该结果。

假设 seen_once = 0、seen_twice = 0,结合按位异或、按位取反和按位与,可以设计如下:

位运算图解

图片及算法来源:
https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetcode/

我们先看第一步,seen_twice 为 0,~seen_twice 即一串 1,再进行 & 的话其实相当于不改变右半部分,即 seen_once = seen_once ^ x

seen_twice = ~seen_once & (seen_twice ^ x), 这里 & 左右两边是反的,所以仍然为 0

到了第二步,seen_once 因为第二次出现变为 0,但 seen_twice 因为 seen_once 的变 0 就可以记录该值了

再到第三步,seen_twice 此时不为 0,会导致 seen_once 仍旧结果为 0;同时 seen_twice 也因为该值的再次出现被按位异或出结果 0

所以如果对所有数全部执行一遍上述操作,那么结果就是只出现一次的数字。

代码实现

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen_once = 0
        seen_twice = 0
		# 遍历列表,执行上述操作
        for i in nums:
            seen_once = ~ seen_twice & (seen_once ^ i)
            seen_twice = ~ seen_once & (seen_twice ^ i)
        # 最终结果存在 seen_once 中
        return seen_once

提交测试表现:

执行用时 : 48 ms, 在所有 Python3 提交中击败了 63.90% 的用户
内存消耗 : 14.6 MB, 在所有 Python3 提交中击败了 25.00% 的用户

这种骚操作,除非遇到原题,不然挺难考虑的。

题目三

「第 231 题:2 的幂」

难度:简单

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1

示例 2:
输入: 16
输出: true
解释: 24 = 16

示例 3:
输入: 218
输出: false

#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/power-of-two

题目分析

常规思路可以建立个 while 循环一直除以 2 取余数,若直到最后一直为 0 则返回 True。涉及到位运算的话,2 的幂次方,即 2 进制位中只会出现 1 个 1,那么可以通过位运算将这个 1 变成 0 从而检测剩余的数值是否为 0。

「位运算技巧:数字 a & (a-1) 可以去除 a 二进制位中最右侧的 1」

去除最右侧1图解

图片和算法来源:
https://leetcode-cn.com/problems/power-of-two/solution/2de-mi-by-leetcode/

当然还有其它位运算可以提取这个最右侧的 1,比如 a & (-a) ,这个上面链接里也都有提到。

回归到题目,只要判断 a & (a-1) 结果为 0,则该数是 2 的幂次方、返回 True

代码实现

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<=0:
            return False
        return n&(n-1)==0

提交测试表现:

执行用时 : 44 ms, 在所有 Python3 提交中击败了 56.49% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 6.25% 的用户

结论

对于位运算的练习,这两天接触了四道题目,基本都是参考着题解算法来做的。这类题目,属于知道了可能会用,不知道完全没这概念的类型,所以,我们主要通过练习加深对位运算的理解,有这么个位运算概念,能记住最好,记不住也不用强求。

整理一下遇到的位运算技巧:

  1. 加法通过 a ^ b 进行不进位加法、 a & b << 1 获取进位结果来实现
  2. 按位异或运算特点:a ^ a = 0, a ^ 0 = a
  3. 去除最右侧的 1: a ^ (a-1) ; 应用是通过判断该结果是否为 0 检测是否为 2 的幂次方

此外,还有些常用技巧:

  1. 判断奇偶性:a & 1, 若结果为 1 则 a 为奇数;若为 0 则 a 为偶数
  2. 这个比较奇怪,但记着吧:a + (~ a) = -1
  3. 判断两数是否同号:a ^ b >= 0,若 a、b 同号,则其首位符号位相同,a ^ b 结果首位为 0、整体 >= 0; 若异号,则首位为 1,则结果是小于 0 的

今早有周赛的,睡过了没能参加,趁机休整下,明天准备看一下二叉树的题目,明儿见!

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python:我的眼里只有你

    这个表白可还行?别急,为了自动生成这两张图片,可是动用了Python人脸识别功能这秘密武器的!

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

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

    TTTEED
  • QR 二维码纠错码(三)

    纠错码可以帮助 QR 读码器检测 QR 二维码中的错误并予以校正。继对文本数据编码后,本篇将继续介绍生成纠错码的过程。

    TTTEED
  • vi 新建文件后保存文件时遇到的问题:E212: 无法打开并写入文件

    Zoctopus
  • 大规模分布式ST 2110部署的案例研究

    本文来自The Broadcast Knowledge,主题是大规模分布式ST 2110部署的案例研究。

    用户1324186
  • 中国电信网络AI领域新突破 ——连任ETSI ENI副主席并主导完成基于意愿的5G承载网切片原型系统展示

    在2019年4月9日-4月11日于波兰华沙召开的ETSI ENI工作组第九次全会上,中国电信战略与创新研究院新兴信息技术研究所网络AI研究中心的王海宁同志成功连...

    灯塔大数据
  • Maven 依赖管理

    在我们创建使用 Maven 项目的过程中,当需要用到第三方的控件时,都是通过依赖管理来达成,也就是 Maven 项目中必有的 pom.xml 文件。POM(Pr...

    村雨遥
  • if语句的汇编表示

    转自:https://blog.csdn.net/u011608357/article/details/22586137

    墨文
  • JS高级测试: 下列说法中正确的是?

    舒克
  • 【JAVA零基础入门系列】Day13 Java类的继承与多态

      继承是类的一个很重要的特性,什么?你连继承都不知道?你是想气死爸爸好继承爸爸的遗产吗?(滑稽)   开个玩笑,这里的继承跟我们现实生活的中继承还是有很大区别...

    弗兰克的猫

扫码关注云+社区

领取腾讯云代金券