leetcode-1009. 十进制整数的反码刷题笔记（c++）

今天药忘吃喽~ 2023-02-24 03:48 12阅读 0赞

#### 写在前面 ####

*  难度：简单
 *  数学题，`原码、反码、补码`

#### 题目详情 ####

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。
    
    二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。
    
    给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。
    
     
    
    示例 1：
    
    输入：5
    输出：2
    解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。
    示例 2：
    
    输入：7
    输出：0
    解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。
    示例 3：
    
    输入：10
    输出：5
    解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。
     
    
    提示：
    
    0 <= N < 10^9
    本题与 476：本题与 476：https://leetcode-cn.com/problems/number-complement/ 相同

#### ac代码 ####

*  [解题思路][Link 1]
    
     *  N=0,返回1
     *  N的二进制逐位取反，结果为1，将2^i累计到结果中；指数加1（i++，i初始取0）。
        
         *  说明:二进制（101）转化成十进制为`1*2^0 + 0*2^1 + 1*2^2 = 5`

class Solution
    {
        
    public:
        int bitwiseComplement(int N)
        {
        
            int i = 0, cc = 0, p = 0;
            if(N == 0)
                return 1;
            while(N)
            {
        
                cc = !(N&1);
                N = N >> 1;
                if(cc != 0)
                    p += pow(2,i);
                i++;
            }
            return p;
        }
    };

*  知识点补充

// 位操作--判断奇偶
    奇数：a & 1 == 1
    偶数：a & 1 == 0
    
    // 判断一个数是否是2的幂次
    // 求一个(正)数二进制中1的个数
    n & (n - 1)
    
    // 相反数
    // 一个数的相反数 = 取反再加1
    - n = ~n + 1 = ~(n - 1)
    
    // 获取整数最右边的1
    n & (-n)
    // n & ~(n - 1)
    
    // 去除整数最右边的1
    n & (n - 1)
    
    // 加法
    // 异或操作：得到本位的加法结果
    // 与操作：得到高位的进位值
    int add(int a, int b)
    {
        
        int add, jin_wei;
        while (b != 0)                     //循环到没有进位退出
        {
        
            add = a^b;
            jin_wei = (a & b) << 1;        //得到高位的进位值
            a = add;
            b = jin_wei;
        }
        return add;
    }
    
    // 减法
    // 减法容易转换为加法：a - b = a + (-b) = a + (~b + 1)
    int subtract(int a, int b)
    {
        
        return add(a, add(~b, 1));
    }
    
    // 正整数）乘法 [待掌握]
    // 乘法：与十进制乘法类似，逐位乘的结果在不同位上相加
    int multiply(int a, int b)
    {
        
        int ans = 0;
        while (b)
        {
        
            if (b & 1)
                ans = add(ans, a);
            a = a << 1;
            b = b >> 1;
        }
        return ans;
    }
    
    // 除法 [待掌握]
    // 二进制除法竖式运算（正负数）
    int divide(int a, int b)
    {
        
        bool neg = (a > 0)^(b > 0);
        if (a < 0)
            a = -a;
        if (b < 0)
            b = -b;
        if (a < b)
            return 0;
    
        int zuoyi;
        //zuoyi记录除数要左移的位数
        for (zuoyi = 0; zuoyi < 32; zuoyi++)
        {
        
            if ((b << zuoyi) >= a)
                break;
        }
    
        //记录每次除法的商
        int shang = 0;
        int i;
        for (i = 0; i < zuoyi; i++)
        {
        
            if ((b << i) > a)              //确定商的位置，保证够除
                continue;
            shang = shang | (1 << i);    //新的商
            a = a - (b << i);            //新的除数
        }
        if (neg)
            return -shang;
        return shang;
    }
    
    // 正数除法
    int divide(int a, int b)
    {
        
        int count = 0;
        while (a >= b)
        {
        
            a = substract(a, b);
            count++;
        }
        return count;
    }

*  参考文章
    
     *  [Leetcode——1009.十进制整数的反码——题解+代码实现][Link 1]
     *  [C/C++基础-原码/反码/补码/位操作实现四则运算][C_C_-]

[Link 1]: https://blog.csdn.net/gaoyu1253401563/article/details/90550895
[C_C_-]: https://blog.csdn.net/baidu_35692628/article/details/78339920?utm_source=blogxgwz8