剑指 Offer 65. 不用加减乘除做加法_⚠️特别注意_CodingPark编程公园

最新推荐文章于 2022-11-26 11:00:37 发布

TEAM-AG

最新推荐文章于 2022-11-26 11:00:37 发布

阅读量167

点赞数

分类专栏： leetcode 文章标签： python

版权由TEAM-AG团队所有

本文链接：https://blog.csdn.net/weixin_38411989/article/details/113655117

版权

leetcode 专栏收录该内容

138 篇文章

订阅专栏

不用加减乘除做加法

问题

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

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

提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数

链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/

解答

本题考察对位运算的灵活使用，即使用位运算实现加法

📍二进制补码计算器
http://www.99cankao.com/numbers/twos-complement.php

机器数

一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

比如，十进制中的数 +3 ，计算机字长为8位，转换成二进制就是00000011。如果是 -3 ，就是 10000011 。

那么，这里的 00000011 和 10000011 就是机器数。

真值

因为第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011，其最高位1代表负，其真正数值是 -3 而不是形式值131（10000011转换成十进制等于131）。所以，为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。

例：0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1

原码, 反码, 补码的基础概念和计算方法.

在探求为何机器要使用补码之前, 让我们先了解原码, 反码和补码的概念.对于一个数, 计算机要使用一定的编码方式进行存储. 原码, 反码, 补码是机器存储一个具体数字的编码方式.

原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:

[+1]原 = 0000 0001

[-1]原 = 1000 0001

第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是:

[1111 1111 , 0111 1111]

即

[-127 , 127]

原码是人脑最容易理解和计算的表示方式.

反码

反码的表示方法是:

正数的反码是其本身

负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.

[+1] = [00000001]原 = [00000001]反

[-1] = [10000001]原 = [11111110]反

可见如果一个反码表示的是负数, 人脑无法直观的看出来它的数值. 通常要将其转换成原码再计算.

补码

补码的表示方法是:

正数的补码就是其本身

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补

[-1] = [10000001]原 = [11111110]反 = [11111111]补

对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值.

解题思路

在这里插入图片描述

def add(a: int, b: int) -> int:
    x = 0xffffffff
    a = a & x
    b = b & x
    while b != 0:
        a, b = (a ^ b), (a & b) << 1 & x
    if a <= 0x7fffffff:
        return a
    else:
        return ~(a ^ x)


fin = add(a=1, b=1)
print(fin)

在这里插入图片描述

⚠️由于 Python 的数字存储特点，需要做特殊考虑，以下详细介绍

Python 负数的存储：

Python，Java 等语言中的数字都是以补码形式存储的。但 Python 没有 int , long 等不同长度变量，即在编程时无变量位数的概念。

获取负数的补码：需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字 32 位以上的数字（将 32 位以上都变为 0 ），从无限长度变为一个 32 位整数。

返回前数字还原：若补码 a 为负数（ 0x7fffffff 是最大的正数的补码），需执行 ~(a ^ x) 操作，将补码还原至 Python 的存储格式。 a ^ x 运算将 1 至 32 位按位取反； ~ 运算是将整个数字取反；因此， ~(a ^ x) 是将 32 位以上的位取反，1 至 32 位不变。


print(hex(1)) # = 0x1 补码
print(hex(-1)) # = -0x1 负号 + 原码 （ Python 特色，Java 会直接输出补码）

print(hex(1 & 0xffffffff)) # = 0x1 正数补码
print(hex(-1 & 0xffffffff)) # = 0xffffffff 负数补码

print(-1 & 0xffffffff) # = 4294967295 （ Python 将其认为正数）

反思与总结

Q ：若数字 a 和 b 中有负数，则变成了减法，如何处理？
A ：在计算机系统中，数值一律用补码 来表示和存储。补码的优势：加法、减法可以统一处理（CPU只有加法器）。因此，以上方法同时适用于正数和负数的加法。

Q：对0取反：~0，输出结果为什么是-1啊？
A：
0 的机器码（原码）：0|0000000000000000000000000000000
-1的机器码（补码）：1|1111111111111111111111111111111

Q：进位 << 问题
A：
a=9,那么就是2进制的0000 1001，
～a，是位运算取反，那么~a的结果就是1111 0110.
b=020，说明shub是8进制，化成2进制就是0001 0000，
~a&b就是1111 0110 & 0001 0000，其结果是0001 0000，
然后是0001 0000<<1,所以是0010 0000.
最后是8进制打印，0010 0000的8进制表示是040，所以结果为40.

在这里插入图片描述