leetcode 371. Sum of Two Integers | 371. 两整数之和（补码运算）

清疚 2022-08-30 11:46 128阅读 0赞

## 题目 ##

[https://leetcode.com/problems/sum-of-two-integers/][https_leetcode.com_problems_sum-of-two-integers]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

根据 related topics 可知，本题考察二进制运算。  
![在这里插入图片描述][20210720121245486.png]  
第一次提交的时候，没想到输入包含负数，于是又调了好久。

既然题目是二进制运算，就借此机会复习一下补码吧。

需要知道：

*  正数的补码 = 其本身
 *  负数的补码 = 源码取反 + 1

补码的运算如下，参考：[补码加减法运算][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

class Solution { 
        public int getSum(int a, int b) { 
            int[] binA = toBinary(a);
            int[] binB = toBinary(b);
            int[] binSum = addBinary(binA, binB);
            int res = binToDec(binSum);
            return res;
        }
    
        // 二进制取反
        public void negateBinary(int[] arr) { 
            for (int i = 0; i < 32; i++) { 
                arr[i] = 1 - arr[i];
            }
        }
    
        // 二进制(补码)->十进制
        public int binToDec(int[] arr) { 
            boolean minus = false;
            if (arr[31] == 1) {  // 若补码符号位为1
                minus = true;
                negateBinary(arr); // 取反
                arr = addBinary(arr, toBinary(1)); // 加1
            }
            int sum = 0;
            for (int i = 0; i < 32; i++) { 
                sum += arr[i] * Math.pow(2, i);
            }
            if (minus) sum *= -1;
            return sum;
        }
    
        // 二进制加法
        public int[] addBinary(int[] a, int[] b) { 
            int carry = 0;
            int[] sum = new int[32];
            for (int i = 0; i < 32; i++) { 
                int t = a[i] + b[i] + carry;
                carry = t >= 2 ? 1 : 0;
                sum[i] = t % 2;
            }
            return sum;
        }
    
        // 十进制->二进制(补码)
        public int[] toBinary(int n) { 
            int abs = Math.abs(n);
            int[] arr = new int[32];
            int size = 0;
            while (abs != 0) { 
                arr[size++] = abs % 2;
                abs /= 2;
            }
            if (n < 0) { 
                negateBinary(arr);
                arr = addBinary(arr, toBinary(1));
            }
            return arr;
        }
    }

后来看了评论区，才知道这题真正的考察点，以及一些其他的位运算技巧，可以参考：[  
A summary: how to use bit manipulation to solve problems easily and efficiently][A summary_ how to use bit manipulation to solve problems easily and efficiently]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]

[https_leetcode.com_problems_sum-of-two-integers]: https://leetcode.com/problems/sum-of-two-integers/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/63c370b3275249f493084bf040f0ed36.png
[20210720121245486.png]: /images/20220829/68e42c202be24baf98addfac6f54f9d6.png
[Link 1]: https://wenku.baidu.com/view/f41c6934b0717fd5370cdc7d.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/e8f610b2e78e4a98b19a2c9f15f54cf4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/73e6af0148434779a952a67bb6f9a2d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/b1745594d6824191a93069ae44e532fa.png
[A summary_ how to use bit manipulation to solve problems easily and efficiently]: https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary:-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]: /images/20220829/b60b8e5ed3414cd09a760f18b42897cd.png