LeetCode 1009：十进制整数补码代码错误排查（输入299475结果不符）

问题描述 #

十进制整数的补码指将其二进制表示中的所有0翻转为1、所有1翻转为0后得到的整数。例如，整数5的二进制是"101"，其补码是"010"即整数2。给定整数n，返回它的补码。

我的解决方案 #

class Solution {
public:
    int bitwiseComplement(int n) {
        int k=1;
        if(n==0){
            return k;
        }
        long int binary=0,i=0;
        while(n){
            long int bit=n&1;
            if(bit==0){
                bit=1;
            }
            else{
                bit=0;
            }
            binary=(bit*pow(10,i))+binary;
            n=n>>1;
            i++;
        }
        long int ans=0,j=0;
        while(binary!=0){
            long int digit=binary%10;
            ans=digit*pow(2,j)+ans;
            j++;
            binary=binary/10;
        }
        return ans;
    }
};

遇到的问题 #

上述代码大部分测试用例运行成功，但输入为299475时，输出结果为224816，而预期输出是224812。

错误原因 #

核心问题是使用了pow()函数进行位权计算，pow()是浮点数运算函数，当指数较大时，无法精确表示整数结果，会出现精度丢失。

比如处理299475这类二进制位数较多的数时，pow(10,i)和pow(2,j)的计算结果会因为浮点数精度限制出现偏差，导致存储翻转后二进制位的binary变量值出错，最终转换回十进制时得到错误结果。

修正方案 #

完全使用位运算处理，避免浮点数运算的精度问题：

1. 先判断n为0的特殊情况，直接返回1；
2. 生成一个与n二进制位数相同的全1掩码；
3. 将n与掩码进行异或运算，得到的结果就是补码（异或运算会将对应位的0和1翻转）。

修正后的代码：

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) return 1;
        int mask = 0;
        int num = n;
        // 生成和n二进制位数一致的全1掩码
        while (num > 0) {
            mask = (mask << 1) | 1;
            num >>= 1;
        }
        return n ^ mask;
    }
};

内容的提问来源于stack exchange，提问作者Bhupesh Yadav