首页 > 代码库 > 剑指Offer之不用加减乘除做加法
剑指Offer之不用加减乘除做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
解题思路
求两个数的和在不能使用加减乘除的条件下，可以使用位运算。位运算是针对二进制的，我们以5和17这两个数字为例。5的二进制是101,17的二进制是10001。我们把计算分成三步：第一步各位相加但不计进位，得到的结果是10100（最后一位两个数都是1，相加的结果是二进制的10。这一步不计进位，因此结果仍是0）；第二步记下进位。在这个例子中只在最后一位相加时产生一个进位，结果是二进制的10；第三步是把前两步的结果相加，得到的结果是10110，转成十进制正好是22。
接下来我们把二进制的加法用位运算代替。第一步不考虑进位对每一位相加。0加0、1加1的结果都是0,0加1、1加0的结果都是1。这和异或的结果是一样的。对于异或而言，0和0、1和1异或的结果是0，而0和1、1和0的异或结果都是1。接着考虑第二步进位，对0加0、0加1、1加0而言，都不会产生进位，只有1加1时，会向前产生一个进位。此时我们可以想象成是两个数现做位与运算，然后再向左移动一位。只有两个数都是1的时候，位与得到的结果是1，其余都是0.第三部就是把前两个步骤的结果相加。第三步相加的过程依然是重复前两步，直到不产生进位为止。
Java代码
package com.swordOffer.addTwoNumbers41;import java.util.Scanner;/** * Created by Feng on 2017/6/20. * 写一个函数，求两个整数之和， * 要求在函数体内不得使用+、-、*、/四则运算符号。 */public class AddTwoNumbers { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int num1 = sc.nextInt(); int num2 = sc.nextInt(); int result = addTwoNumbers(num1, num2); System.out.println(result); } } private static int addTwoNumbers(int num1, int num2) { int sum, carry;//进位值 do { //以5和17为例 //第一步：相加各位的值，不算进位，得到10100， //二进制每位相加就相当于各位做异或操作，00101^10001。 //第二步：计算进位值，得到00001，相当于各位做与操作得到00101&10001， // 再向左移一位得到00010,(00101 & 10001)<<1。 //第三步重复上述两步,各位相加。 //继续重复上述两步：直到进位值为0，跳出循环，10110为最终结果 sum = num1 ^ num2; carry = (num1 & num2) << 1; num1 = sum; num2 = carry; } while (num2 != 0); return sum; }}
剑指Offer之不用加减乘除做加法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。