【剑指offer】面试题65:不用加减乘除做加法(Java)
异或运算:计算当前位的和,不带进位的部分。 与运算并左移:计算进位部分,将其左移处理。 重复上述步骤,直到进位为零。 初始化: 循环处理:当 循环结束:当
发布日期:2021-04-30 21:04:35
浏览次数:101
分类:精选文章
本文共 1215 字,大约阅读时间需要 4 分钟。
为了实现两个整数之和的计算而不使用四则运算符,我们可以利用位运算的方法。通过反复处理每一位,直到没有进位为止。具体步骤如下:
以下是使用C#实现的函数:
public int add(int a, int b) { int sum = 0; while (b != 0) { int temp = a ^ b; // 计算当前位的和,不带进位 b = (a & b) << 1; // 计算进位,并左移 a = temp; } return a;} 步骤解释:
sum 初始化为0,用于存储最终结果。b不为零时,进入循环。 - 计算当前位的和:
temp = a ^ b。 - 计算进位并左移:
b = (a & b) << 1,将进位左移处理。 - 更新变量:将
a设为当前位的和temp,b设为新的进位。
b为零时,循环结束,返回a,即为两个整数之和。示例验证:
- 输入:a = 1, b = 1
- 循环开始:b=1
- temp = 1 ^ 1 = 0
- b = (1 & 1) << 1 = 0
- a = 0
- 循环结束,返回a=0。这与期望的结果不符,表明该方法在a=1, b=1时有问题。
- 循环开始:b=1
修正方法:
在实际应用中,可能需要调整循环条件或处理进位的方式。正确的位运算加法应确保所有位都被处理,包括最低有效位。确保循环在b为零时结束,所有进位被处理。
优化代码:
public int add(int a, int b) { while (b != 0) { int sum = a ^ b; // 当前位的和 int carry = (a & b) << 1; // 进位 a = sum; b = carry; } return a;} 验证:
- 输入:a = 3, b = 5
- 循环开始:b=5
- sum = 3 ^ 5 = 6
- carry = (3 & 5) << 1 = 2
- a = 6, b = 2
- 循环继续:b=2
- sum = 6 ^ 2 = 4
- carry = (6 & 2) << 1 = 4
- a = 4, b = 4
- 循环继续:b=4
- sum = 4 ^ 4 = 0
- carry = (4 & 4) << 1 = 8
- a = 0, b = 8
- 循环继续:b=8
- sum = 0 ^ 8 = 8
- carry = (0 & 8) << 1 = 0
- a = 8, b = 0
- 循环结束,返回a=8,正确。
- 循环开始:b=5
结论:
通过上述优化后的代码,可以正确地使用位运算实现两个整数的加法,而无需使用四则运算符。该方法在所有情况下都能正确处理,包括负数和零。
发表评论
最新留言
感谢大佬
[***.8.128.20]2026年06月12日 17时35分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
PHP应用程序连接Oracle数据库Demo(附Oracle客户端安装文件)
2023-03-01
PHP开发api接口安全验证
2023-03-01
PHP开发规范PSR
2023-03-01
PHP开发遇到错误0001
2023-03-01
php异常处理
2023-03-01
PHP引入了泛型和集合两大重要特性,大大改善 PHP 代码的可维护性和可读性
2023-03-01
PHP引擎php.ini参数优化
2023-03-01
PHP引用(&)使用详解
2023-03-01
php引用及垃圾回收
2023-03-01
php当前时间的集中写法
2023-03-01
php微信 开发笔记,微信WebApp开发总结笔记
2023-03-01
php微信公众号开发access_token获取
2023-03-01
php微信公众号开发微信认证开发者
2023-03-01
php微信公众号开发用户基本信息
2023-03-01
php怎么将对象变成数组,php怎么将对象转换成数组
2023-03-01
RabbitMQ - 消息堆积问题的最佳解决方案?惰性队列
2023-03-01
php怎样比较两数大小,jquery如何判断两个数值的大小
2023-03-01
PHP性能监控 - 开启xhprof(一)
2023-03-01
PHP性能监控 - 怎么看xhprof报告(二)
2023-03-01