当前位置：首页 > news >正文

剑指Offer65.不用加减乘除做加法 C++

news 2025/6/30 12:43:49

1、题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2

2、VS2019上运行

使用位运算的方法

#include <iostream>class Solution {
public:/*** 计算两个整数的和* @param a 第一个整数* @param b 第二个整数* @return 两个整数的和*/int add(int a, int b) {while (b != 0) {unsigned int carry = (unsigned int)(a & b) << 1; // 计算进位//按位异或，相同为0，不同为1a = a ^ b; // 计算无进位和b = carry; // 将进位值存入b，用于下一轮循环}return a; // 返回最终结果}
};int main() {Solution solution;int a = 5; // 第一个整数int b = 7; // 第二个整数int sum = solution.add(a, b); // 计算两个整数的和std::cout << "Sum: " << sum << std::endl; // 输出结果return 0;
}

Sum: 12

3、解题思路

假设我们要计算 a = 3 + 5。
首先，将a初始化为第一个加数3（a=3），将b初始化为第二个加数5（b=5）。
在while循环中，不断执行以下操作，直到b等于0：
1.计算进位值carry：carry = (unsigned int)(a & b) << 1。
2.这一步使用位运算符&和<<计算a和b的按位与操作，然后将结果左移1位来得到进位值carry。这是因为两个数相加的进位值是它们按位与操作的结果向左移动一位。
3.更新a的值：a = a ^ b。
4.这一步使用位运算符^计算a和b的按位异或操作，将结果存储回a。按位异或操作得到的结果相当于不考虑进位的加法结果。
5.更新b的值：b = carry。
6.这一步将进位值carry赋值给b，为下一次循环准备。
在第一次循环中，执行以下操作：
carry = (unsigned int)(3 & 5) << 1 = 1 << 1 = 2。
a = 3 ^ 5 = 6。
b = 2。
在第二次循环中，执行以下操作：
carry = (unsigned int)(6 & 2) << 1 = 0 << 1 = 0。
a = 6 ^ 2 = 4。
b = 0。
由于b现在为0，循环结束。
最后，返回a的值4，即3 + 5的结果。