Maple's Story

剑指offer 47-48 ：不用加减乘除做加法、求1+2+3+...+n

剑指offer 算法笔记 计算机组成原理
字数统计: 341阅读时长: 1 min
2020/03/15 Share

这两道题看似是算法题，实际上是考察关于计算机底层实现加减乘除方法的知识。

不用加减乘除做加法

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

一个加法计算可以分为按位相加以及进位两部分，我们可以分别用异或运算和与运算来实现这两者。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int Add(int num1, int num2)
    {
        if (!(num1 & num2))
            return (num1 ^ num2);
        return Add(num1 ^ num2, (num1 & num2) << 1);
    }
};

求1+2+3+…+n

题目描述：
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

上式等价于 $\frac{(n+1)n}{2}$ ，故此题可以转化为如何使用加减法实现乘法。
同样乘法计算 $mn$ 可以分为两部分：m 与 n的每一位相乘，再把上述结果相加。转化为二进制则是 m 与 0 或 1 相乘，再相加，前者可以用简单的与运算完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int mask[2] = {0x00000000, 0x7FFFFFFF};
    int Sum_Solution(int n) {
        return sum(n + 1, n) >> 1;
    }
    
    int sum(int m, int n) {
        int res = 0;
        (n | 0) && (res =  (m & mask[n & 1]) + (sum(m, n >> 1) << 1));
        return res;
    }
};

原文作者：枫逸

原文链接：https://www.pengchen.top/posts/23296/

发表日期：March 15th 2020, 10:24:58 pm

更新日期：September 5th 2020, 1:44:05 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 不用加减乘除做加法
  2. 2. 求1+2+3+…+n
Total : 15
2020
2019
操作系统 学习笔记 并发编程 Fall Detection Machine Learning Deep Learning C++ 剑指offer 算法笔记 计算机组成原理 MySQL 数据库 Redis 实习总结 运维 集群监控 GO语言 后台开发 转载笔记
学习笔记 机器学习 实习总结 转载笔记