剑指offer系列——剑指 Offer 65. 不用加减乘除做加法

前面的话

大家好！本篇文章将介绍的剑指offerOJ题，来自力扣剑指 Offer 65. 不用加减乘除做加法题解，展示代码语言暂时为：Java，C，C++。

博客主页：未见花闻的博客主页
欢迎关注点赞收藏留言
本文由未见花闻原创，CSDN首发！
首发时间：2021年12月10日
坚持和努力一定能换来诗与远方！
刷题推荐书籍：《剑指offer专项版》，《剑指offer第2版》
参考在线编程网站：牛客网力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

导航小助手

• 剑指 Offer 65. 不用加减乘除做加法
• • 题目详情
  • 解题思路
  • 源代码
• 总结

---

---

剑指 Offer 65. 不用加减乘除做加法

题目详情

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

示例：

1. 输入: a = 1, b = 1
2. 输出: 2
3. 输入: a = 5, b = 6
4. 输出: 11

复制代码

提示：

1. a, b 均可能是负数或 0。
2. 结果不会溢出 32 位整数。

来源：力扣（LeetCode）链接：剑指 Offer 65. 不用加减乘除做加法

解题思路

方法1：你说不能使用加减乘除运算符？我偏要用，直接将两数相加返回。

方法2：位运算。

预备知识：

• 按位与 & ：双目运算符，对每位取与，都为1则为1，否则为0。
• 按位异或 ^ ：双目运算符，对每位取异或，对应位两数不相同为1，否则为0。
• 左移 << ：双目运算符，a << b ，表示将a的二进制位左移b位，最右边补0。
• 加法进位的特点：对于二进制，发生进位的条件是两个数所对应的二进制位均为1。

解题思路：

实现a，b两数完整加法的步骤：

1. 将a与b按位与并左移一位，即(a & b) << 1，不妨将此结果存至变量tmp，若此数值为0，就表示两数未发生进位。
2. 将a与b进行非进位加法，即a ^ b，不妨将此结果赋值给a，将上面所得tmp值赋值给b。
3. 此时b的值为tmp，判断b是否为0，若b不为0，需要进位，重复上述步骤，将进位数b与前一次非进位加法的值非进位相加，若b为0，不需要进位，加法过程结束，最终结果即a的值。

注意：C/C++对负数左移存在溢出，先将 a & b 强转为 unsigned int 以保护左移溢出的情况！

源代码

Java:

1. class Solution {
2. public int getSum(int a, int b) {
3. //两数异或相当于不进位相加，两数按位与运算能够得到需要进位的数，将此数左移再异或相加，直到该数为0，加法计算完毕
4. while (b != 0) {
5. int tmp = (a & b) << 1;
6. a ^= b;
7. b = tmp;
8. }
9. return a;
10. }
11. }

复制代码

C:

1. int getSum(int a, int b){
2. while (b) {
3. int tmp = (unsigned int)(a & b) << 1;//C/C++，负数情况，对有符号数左移存在溢出，先转无符号再左移对溢出情况保护处理
4. a ^= b;
5. b = tmp;
6. }
7. return a;
8. }

复制代码

C++:

1. class Solution {
2. public:
3. int getSum(int a, int b) {
4. while (b) {
5. int tmp = (unsigned int)(a & b) << 1;
6. a ^= b;
7. b = tmp;
8. }
9. return a;
10. }
11. };

复制代码

总结

不用加减乘除做加法，最容易想到的方法就是位运算，通过了解各种位运算的特点，找出模拟加法的适当方法。
力扣同源题：
371. 两整数之和
面试题 17.01. 不用加号的加法
力扣类似题：
面试题 08.05. 递归乘法
29. 两数相除
50. Pow(x, n)
69. Sqrt(x)
面试题 16.07. 最大数值

---

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！

来源：https://blog.csdn.net/m0_59139260/article/details/121858746
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！