一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台:牛客网
书籍下载:共享资源
二、题目
写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
1、思路
首先看十进制是如何做的: 5+7=12,
可以使用三步走:
第一步:相加各位的值,不算进位,得到2。
第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。
第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。 同样我们可以
三步走的方式计算二进制值相加: 5-101,7-111
第一步:相加各位的值,不算进位,得到010,二进制每位相加就相当于各位做异或操作,101^111。
第二步:计算进位值,得到1010,相当于各位做与操作得到101,再向左移一位得到1010,(101&111)<<1。
第三步:重复上述两步, 各位相加 010^1010=1000,进位值为100=(010&1010)<<1。
继续重复上述两步:1000^100 = 1100,进位值为0,跳出循环,1100为最终结果。
2、代码
C++:
1 2 3 4 5 6 7 | class Solution { public: int Add(int num1, int num2) { return num2 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1; } }; |
Python:
1 2 3 4 5 6 7 8 9 10 11 | # -*- coding:utf-8 -*- class Solution: def Add(self, num1, num2): # write code here MAX = 0x7fffffff mask = 0xffffffff while num2 != 0: num1, num2 = (num1 ^ num2), ((num1 & num2) << 1) num1 = num1 & mask num2 = num2 & mask return num1 if num1 <= MAX else ~(num1 ^ mask) |
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
2018年4月29日 下午9:39 沙发
666
2019年5月26日 下午10:10 板凳
主要原因还是因为python没有无符号又移操作,所以需要越界检查一波
2019年5月27日 上午9:32 1层
@muyi
2020年9月6日 下午4:19 地板
可以算一下 0x7FFFFFFF 是多少
每个十六进制数4bit,因此8位16进制是4个字节,刚好是一个int整型
F的二进制码为 1111
7的二进制码为 0111
这样一来,整个整数 0x7FFFFFFF 的二进制表示就是除了首位是 0,其余都是1
就是说,这是最大的整型数 int(因为第一位是符号位,0 表示他是正数)
用 INT_MAX 常量可以替代这个值。
https://blog.csdn.net/themagickeyjianan/article/details/97524284
2020年9月6日 下午4:46 4楼
~表示按位取反。
按位取反的快捷运算公式 ~x = -(x+1)
正数的原、反、补码都是它本身;
负数的原码最高为为1开头,反码是最高符号位不变,其余位在原码的基础上取反,
负数的补码是在负数反码的基础上+1即可得到。
例如:
~5 (也就是5按位取反运算,下面涉及的是补码运算):
00000101按位取反,这里需要将原始01串完全反转过来,不存在最高符号位的概念,取反结果为: 11111010
注意这里的结果是用补码表示的,毕竟这还是机器表示形式,转化为自然语言的编码,把结果转化为原码就是:
补码-1转为反码: 11111010 – 1 = 11111001
反码再取反转为原码:11111001 = 10000110
原码转为十进制,答案就是-6
所以 ~5 = -6
(首先要明确的一点是,计算机内部在做数学运算时(也就是计算机的0和1的运算),都是以补码为标准的,说白了 计算机中就一种码那就是补码,而现实社会中的编码规则,例如原码、反码都是我们自定义的,为了和计算机中的补码形成转换关系。)
来自:
https://blog.csdn.net/Coder__CS/article/details/79186677