[LintCode] A + B 问题-阿里云开发者社区

[LintCode] A + B 问题

2015-06-29 758

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Bit-by-Bit summation: 1 class Solution { 2 public: 3 /* 4 * @param a: The first integer 5 * @param b: The second integer 6...

Bit-by-Bit summation:

 1 class Solution {
 2 public:
 3     /*
 4      * @param a: The first integer
 5      * @param b: The second integer
 6      * @return: The sum of a and b
 7      */
 8     int aplusb(int a, int b) {
 9         // write your code here, try to do it without arithmetic operators.
10         int res = 0, sum = 0, carry = 0;
11         for (int i = 0; i < 32; i++, a >>= 1, b >>= 1){
12             int d1 = a & 1, d2 = b & 1;
13             sum = (d1 ^ d2 ^ carry);
14             carry = max((d1 & d2), max((d1 & carry), (d2 & carry)));
15             res ^= (sum << i);
16         }
17         return res;
18     }
19 };

Treat a + b as two parts:

a + b without carry;
carry of a + b;
recursively plus part 1 and part 2 until no carry exists.

 1 class Solution {
 2 public:
 3     /*
 4      * @param a: The first integer
 5      * @param b: The second integer
 6      * @return: The sum of a and b
 7      */
 8     int aplusb(int a, int b) {
 9         // write your code here, try to do it without arithmetic operators.
10         while (b) {
11             int carry = a & b;  // carry
12             a ^= b;             // plus without carry
13             b = carry << 1;     // recursively plus the two parts
14         }
15         return a;
16     }
17 };

The code can be further shortened by writing it recursively.

 1 class Solution {
 2 public:
 3     /*
 4      * @param a: The first integer
 5      * @param b: The second integer
 6      * @return: The sum of a and b
 7      */
 8     int aplusb(int a, int b) {
 9         // write your code here, try to do it without arithmetic operators.
10         if (!b) return a;
11         return aplusb(a ^ b, (a & b) << 1);
12     }
13 };

Or just in one line :-)

 1 class Solution {
 2 public:
 3     /*
 4      * @param a: The first integer
 5      * @param b: The second integer
 6      * @return: The sum of a and b
 7      */
 8     int aplusb(int a, int b) {
 9         // write your code here, try to do it without arithmetic operators.
10         return (!b ? a : aplusb(a ^ b, (a & b) << 1));
11     }
12 };