专栏首页大白技术控的技术自留地C++版 - 剑指offer 面试题47:不用+、-、×、÷做加法 题解

C++版 - 剑指offer 面试题47:不用+、-、×、÷做加法 题解

面试题47:不用加减乘除做加法

提交网址: http://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201

时间限制:1秒   空间限制:32768K  参与人数:2147

题目描述

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

分析: 此题属发散思维能力的题型。

看到的这个题目,我的第一反应是懵了,四则运算都不能用,那还能用什么呢?不过化为二进制数之后,用位运算 与&、或|、异或^、取反~可以派上用场。

首先看十进制是如何做的: 9+19=28,使用分3步走的策略。 对应与函数int Add(int num1, int num2),此时num1=9, num2=19 第1步:相加各位的值,不算进位,得到不计进位的和sum=18(共2位)。 第2步:计算进位值,得到与进位等价的数carry=10. (如果这1步的进位值为0,那么第1步得到的值就是最终结果,否则继续第3步。) 第3步:重复上述两步,只是相加的值变成上述两步的得到的结果num1=18和num2=10,无进位,此时Add()的num2=0,结束。(如果还有进位,重复上述两步。) 同样我们可以用3步走的方式计算二进制值相加: 9->1001(num1),19->10011(num2) 第1步:不计进位地各位相加,得到11010,二进制每位相加就相当于各位做异或操作,sum=01001^10011=11010。 第2步:计算进位值,得到10,相当于各位做与操作得到1,再向左移一位得到00010,carry=(01001&10011)<<1=10。 第3步:重复上述两步, 不计进位地各位相加:11010^00010=11000,进位值为100=(11010&00010)<<1。      继续重复上述两步:11000^100 = 11100,进位值carry为0,此时Add()的num2=0,结束,11100(十进制28)为最终结果。

递归实现 AC代码:

#include<cstdio>
using namespace std;
class Solution {
public:
    int Add(int num1, int num2)
    {
    	int sum, carry;
    	sum=num1^num2;  // 按位异或表示各位分别相加,不计入进位 
    	carry = (num1 & num2) << 1;  // carry用0、1来记录各bit的进位 
        if(num2==0) return num1; // 递归出口 
        return Add(sum, carry);
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	int res1 = sol.Add(3,6);
	int res2 = sol.Add(-5, 256);
	
	printf("%d\n", res1);	
	printf("%d\n", res2);	
	return 0;
}

迭代实现 AC代码:

#include<cstdio>
using namespace std;
class Solution {
public:
    int Add(int num1, int num2)
    {
        int sum, carry;
        while(num2 != 0)   // 当被加数为0时,迭代找到了结束出口 
        {
            sum = num2 ^ num1;           // 按位异或表示各位分别相加,不计入进位 
            carry = (num1 & num2) << 1;  // carry用0、1来记录各bit的进位 
            num2 = carry;
            num1 = sum;
        }
        return num1;
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	int res1 = sol.Add(3,6);
	int res2 = sol.Add(-5, 256);
	
	printf("%d\n", res1);	
	printf("%d\n", res2);	
	return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++版 - Leetcode No.1 - Two sum题解

    提交网址: https://leetcode.com/problems/two-sum/

    Enjoy233
  • C#版 - Leetcode 136. Single Number题解

    在线提交: https://leetcode.com/problems/single-number/

    Enjoy233
  • 桶排序的单链表实现及其变种

    《算法导论》CLRS 第八章 线性时间排序 8.4 桶排序 桶排序的思想就是把区间[0, 1)划分成n个相同大小的子区间,每一个区间称为桶(buck...

    Enjoy233
  • 打印字符图形(蓝桥杯基础题 Java版)

    问题描述 利用字母可以组成一些美丽的图形,下面给出了一个例子: ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC 这...

    张俊怡
  • 十分钟视频,手把手教你用Python撒情人节狗粮的正确姿势

    大数据文摘
  • 剑指OFFER之把数组排成最小的数(九度OJ1504)

    题目描述: 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排...

    用户1154259
  • 隐忍一年,百度钱包杀回正面战场

    一个著名鸡汤是,所有人都知道世界第一高峰是珠穆朗玛峰,却很少有人能回答第二高峰的名字。在互联网行业第一和第二因为时常交锋可以时常进入大众视野,第三却鲜有人关注。...

    罗超频道
  • 百度CEO李彦宏称如果google回到中国,有信心再赢一次,有这种可能嘛?

    百度已经很久没有发出如此豪言壮语了,这件事如果真的发生对于百度来讲未必是坏事,毕竟现在百度在中国市场上的份额还是独一份的老大,虽然有很多的搜索引擎也在极力去争夺...

    程序员互动联盟
  • 聊聊Elasticsearch的ConcurrentMapLong

    elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/common/util/concurren...

    codecraft
  • GitHub最著名的20个Python机器学习项目,值得收藏!

    关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 源 | kdnuggets|小象 开...

    昱良

扫码关注云+社区

领取腾讯云代金券