【LeetCode】Day211-不用加减乘除做加法
创始人
2025-05-30 22:54:35
0次
题目
剑指 Offer 65. 不用加减乘除做加法【中等】
题解
不能用加减乘除的题，要考虑位运算。
设两数字的二进制形式a，b，s=a+b，a(i)代表a的二进制的第i位，则分为以下四种情况：
| a(i) | b(i) | 无进位和n(i) | 进位c(i+1) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
观察发现，无进位和==异或运算 规律，进位==与运算 规律（需左移一位），因此 n 和 c 的计算公式如下：
n=a⊕bn=a \oplus bn=a⊕b，非进位和：异或运算
c=a&b<<1c=a \& b<<1c=a&b<<1，进位：与运算+左移一位
由于 和s=非进位和n + 进位和c，即s=a+b=>s=n+c
循环求n和c，直到进位c=0；此时s=n，返回n即可。举例20+17如下：
Q：如果a或者b是负数，怎么办？
A：计算机系统中，数值一律用补码来表示和存储
补码的优势：加法、减法可以统一处理（CPU只有加法器）
因此，以上方法同时适用于正数和负数的加法。
class Solution {public int add(int a, int b) {while(b!=0){int c=(a&b)<<1;//进位ca^=b;//非进位和ab=c;//进位b}return a;}
}
时间复杂度：O(1)O(1)O(1)
空间复杂度：O(1)O(1)O(1)
相关内容
热门资讯
监控摄像头接入GB28181平...
流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
Windows10添加群晖磁盘...
在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer...
目录 目录 什么是protocol buffer 1.protobuf 1.1安装 1.2使用...
Fluent中创建监测点
1 概述某些仿真问题，需要创建监测点，用于获取空间定点的数据...
MySQL下载和安装（Wind...
前言：刚换了一台电脑，里面所有东西都需要重新配置，习惯了所...
MFC文件操作
MFC提供了一个文件操作的基类CFile，这个类提供了一个没有缓存的二进制格式的磁盘...
在Word、WPS中插入AxM...
引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
有效的括号
一、题目 给定一个只包括 '('，')'，'{'，'}'...
【Ctfer训练计划】——(三...
作者名：Demo不是emo 主页面链接：主页传送门 创作初心ÿ...