剑指offer-48、不使⽤加减乘除实现加法
<h2 id="题描述">题⽬描述</h2><p>写⼀个函数，求两个整数之和，要求在函数体内不得使⽤ + 、 - 、 * 、 / 四则运算符号。</p>
<p>示例1<br>
输⼊：1,2<br>
返回值：3</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="位运算迭代法推荐">位运算迭代法（推荐）</h3>
<p>将加法分解为「无进位和」+「进位值」，循环直到进位为0</p>
<p><strong>位运算加法的数学原理</strong>：</p>
<ul>
<li><strong>异或运算 (^)</strong>：实现无进位加法
<ul>
<li><code>0^0=0</code>, <code>0^1=1</code>, <code>1^0=1</code>, <code>1^1=0</code>（进位丢失）</li>
</ul>
</li>
<li><strong>与运算 (&)</strong>：检测需要进位的位置
<ul>
<li>只有<code>1&1=1</code>，其他情况都为0</li>
</ul>
</li>
<li><strong>左移运算 (<<)</strong>：将进位值移到正确位置</li>
</ul>
<pre><code class="language-java">public class Solution {
public int add(int a, int b) {
// 循环直到进位为0
while (b != 0) {
// 计算无进位和：异或运算相当于无进位加法
// 例如：5^3=6 (101^011=110)
int sum = a ^ b;
// 计算进位值：与运算后左移1位得到进位
// 例如：(5&3)<<1=2 (101&011=001, 左移1位=010)
int carry = (a & b) << 1;
// 更新a为无进位和，b为进位值
a = sum;
b = carry;
// 继续下一轮计算，直到进位为0
}
return a;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(1) - 最多循环32次（整数位数）</li>
<li>空间复杂度：O(1) - 只使用常数空间</li>
</ul>
<h3 id="位运算递归法">位运算递归法</h3>
<p>将迭代过程转为递归调用，基础案例是进位为0</p>
<pre><code class="language-java">public class Solution {
public int add(int a, int b) {
// 递归终止条件：当进位为0时，直接返回无进位和
if (b == 0) {
return a;
}
// 递归过程：计算无进位和与进位值，继续递归相加
return add(a ^ b, (a & b) << 1);
}
}
</code></pre>
<ul>
<li>时间复杂度：O(1) - 递归深度最多32层</li>
<li>空间复杂度：O(1) - 但递归栈有深度限制</li>
</ul>
<p>递归案例：</p>
<pre><code class="language-text">add(2, 3)
→ add(2^3, (2&3)<<1) = add(1, 2)
→ add(1^2, (1&2)<<1) = add(3, 0)
→ b=0, 返回3
最终结果：5
</code></pre>
<h3 id="投机取巧">投机取巧</h3>
<pre><code class="language-java">import java.util.concurrent.atomic.AtomicInteger;
public class Solution {
// 方法1：使用内置的加法方法
public int add1(int a, int b) {
return Integer.sum(a, b); // 内部实现还是用+，不符合要求
}
// 方法2：使用AtomicInteger（实际开发中更不实用）
public int add2(int a, int b) {
AtomicInteger ai = new AtomicInteger(a);
return ai.addAndGet(b); // 内部使用CAS操作
}
// 方法3：使用BigDecimal（过度设计）
public int add3(int a, int b) {
// 需要创建对象，性能较差
return BigDecimal.valueOf(a)
.add(BigDecimal.valueOf(b))
.intValue();
}
}
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19316215
頁:
[1]