算法与数据结构：进制转换

[Quickeryi]

在实际应用中，经常需要使用到数的进制转换，虽然现在许多语言都提供了相应的方法直接进行进制转换，但是作为一个工科gay，还是必须知道常见的进制转换的实现原理的～

十进制转为二进制

• 表示方法：这一点我们应该都知道，二进制只有0和1
• 十进制转二进制原理：十进制数除以二，得到的商再除以二，依次类推直到商为0或1时为止，然后在旁边标出各步的余数，最后倒着写出来，高位补零，就完成了
• 举个🌰：下面以42转为二进制为例
  
• 扩展：上面列举的例子只是关于十进制正整数转为二进制，那么十进制负整数或者小数转为二进制是如何转换的呢？
  • 负整数转换成二进制：先是将对应的正整数转换成二进制后，然后对二进制取反，然后对结果再加一
  • 小数转换为二进制：先将整数部分转换为对应的二进制，然后对小数部分作下面的处理，对小数点以后的数乘以2，有一个结果吧，取结果的整数部分（不是1就是0喽），然后再用小数部分再乘以2，再取结果的整数部分……以此类推，直到小数部分为0或者位数已经够了就OK了
  • 例子说明一切
    
• 补充：整数的原码 = 反码 = 补码，负数的二进制就是补码表示的
  • 原码：原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值
  • 反码：负数的反码是在其原码的基础上, 符号位不变，其余各个位取反，注意：正数的反码是其本身
  • 补码：在反码的基础上+1，注意：正数的补码是其本身

二进制转为十进制

• 直接一张图说明一切吧
  

十进制转八进制

• 表示方法：用0～7表示
• 十进制转八进制原理：与上述所讲的二进制一样，只是取余的基数不同而已

十进制转十六进制

• 表示方法：用0～9以及a-f表示
• 十进制转十六进制原理：与上述所讲的二进制一样，只是取余的基数不同而已

二进制与八进制互转

• 二进制转八进制：3位二进制数按权展开相加得到1位八进制数
• 八进制转成二进制：对每个八进制为3个二进制，不足时在最左边补零
  

扩展阅读

计算两个数的汉明距离

• 题目描述：两个整数之间的汉明距离是指，相应二进制位不同的位置的数目，给你两个整数x和y，计算他们之间的汉明距离。其中，0 ≤ x, y < 2^31
• 样例
  • 输入：x = 1, y = 4
  • 输出：2
  • 样例解释
    • x = 1 ==> 0 0 0 1
    • y = 4 ==> 0 1 0 0
• 思路：这就转换为求取两个数的对应二进制数，然后对每一位二进制做比较即可
• 解法（这里只是其中一种解法而已，还可以使用位运算等）

let hammingDistance = (x, y) => {
        let distance = 0;
        while (x != 0 || y != 0) { // 当某一个数的商为0时，二进制比较结束
            if (x%2 != y%2) { // 二进制逐位比较
                distance++;
            }
            x = Math.floor(x/2); // 获取商
            y = Math.floor(y/2); // 获取商
        }
        return distance;
    };

[OrdinaryYZH]

1010-0001=1001
图中算错了。。。