剑指Offer(四十八):不用加减乘除的加法

2018年1月19日12:21:20 5 2,841 °C
摘要

写一个函数,求两个整数之和,要求在函数体内不得使用加减乘除四则运算符号。

剑指Offer(四十八):不用加减乘除的加法

一、前言

本系列文章为《剑指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++:

Python:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:5   其中:访客  4   博主  1

    • avatar 到底对不对 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 上海理工大学 4

      666

      • avatar muyi 来自天朝的朋友 谷歌浏览器 Linux 广东省深圳市 电信 1

        主要原因还是因为python没有无符号又移操作,所以需要越界检查一波

          • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

            @muyi :wink: :wink: :wink: :wink:

          • avatar kkt 来自天朝的朋友 Safari浏览器 Windows 7 广东省东莞市 电信 1

            可以算一下 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

            • avatar kkt 来自天朝的朋友 Safari浏览器 Windows 7 广东省东莞市 电信 1

              ~表示按位取反。
              按位取反的快捷运算公式 ~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