title: 算法小练——A + B 问题
categories:

  • Algorithms
    tags:
  • esay
    abbrlink: 115354012
    date: 2019-11-02 12:47:29

描述

给出两个整数 aa 和 bb , 求他们的和。

你不需要从输入流读入数据，只需要根据aplusb的两个参数a和b，计算他们的和并返回就行。

您在真实的面试中是否遇到过这个题？ 是

题目纠错

说明

a和b都是 32位 整数么？

  • 是的

我可以使用位运算符么？

  • 当然可以

样例

样例 1:

输入:  a = 1, b = 2
输出: 3	
样例解释: 返回a+b的结果.

样例 2:

输入:  a = -1, b = 1
输出: 0	
样例解释: 返回a+b的结果.

挑战

显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？（不使用++等算数运算符）

代码

public class Solution {
    /** * @param a: An integer * @param b: An integer * @return: The sum of a and b */
    public int aplusb(int a, int b) {
        // write your code he
      return a+b;
    }
}

这道题目前为止，都很简单。但是如果你关注到了挑战的话，就引出思考的问题了。

对于作者这种初次接触算法的新手来说，对于不使用算术运算符的思路完全没有，于是便查询了下资料，才了解到算术运算符的底层是位运算符，可以用位运算符来替代算数运算符。

那么就科普下位运算符的知识：

XOR异或 :当 a、b 不等时，为1,反之，为0

AND 且：当 aANDb 就是 a与b 在位上的相加，需要进位

<<：进位

eg: 5+6 => 101 +110 => 1011 => 11

那么把一个十进制数先转化为二进制数，就发现，非进位部分通过XOR来运算，进位部分通过AND来运算。因为 0和0得0 0和1为1 符合异或的规则，1和1为10 符合AND的规则。

public static int aplusb(int a, int b) {
        // write your code he
        return b==0?a:aplusb(a^b,(a&b)<<1);
    }