leetcode 371. Sum of Two Integers | 371. 两整数之和（补码运算）-蒲公英云

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

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

题目

https://leetcode.com/problems/sum-of-two-integers/
在这里插入图片描述

题解

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

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

需要知道：

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

补码的运算如下，参考：补码加减法运算
在这里插入图片描述

在这里插入图片描述

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;
    }
}