学点算法(七)——十进制数转换为二进制数

今天我们来学习十进制转为二进制的算法。

大家学习计算机或者编程，都会知道计算机处理数据都是基于二进制的，而我们在日常生活中都是使用十进制。如果要用计算机存储数据，肯定要将十进制转化为二进制，或者我们要查数据，要将二进制转换为十进制，那么问题来了：现在有一个十进制数，我们如何将其转换为二进制数呢？

比如我们现在有一个数字：1024（预先给定的数字默认用十进制理解）。用十进制表示为：

用二进制可表示为：

可以发现一个规律：十进制或者二进制的最终表示形式1024或10,000,000,000可以取展开式的系数得到，而这个展开式公式里面的数字都是以十进制表示的。我们只要取到这些系数就可以得到二进制数的表示，那么我们如何取到这些系数呢？

为了简便和易于理解，我们以十进制来分析，可以发现，最后一项值是4，10的指数是0，即最后一项值本身就是系数本身，而展开式的其他项的指数都大于等于1，即意味着它们都可以被10整除，那么最后一项就是整体值除以10后留下的余数，即系数。通过除10取余的方法，我们可以得到最后一项的系数4，那么如何取到倒数第二项的系数呢？很简单，除以两次10就得到了倒数第二项的系数。其他项系数可以通过同样的方法取到。那么什么时候结束呢？就是我们取不到任何系数的时候，就是我们上一次除完10得到的商为0，即表示最后一个系数被我们取到了，整个过程宣告终止。

整体流程如下：

①取倒数第一个系数：

②取倒数第二个系数：

③取倒数第三个系数：

④取倒数第四个系数：

这时，商变成了0，整个过程终止。

而最终得到数即是把每一步得到的数反过来排列，4201反过来即是1024。

二进制的原理同十进制，只是把每个过程的除数换成2即可。

注意到我们将每轮求得的结果值反过来排列才是最后的结果值，这种逆序输出的性质刚好对应了栈的后进先出的特性。索引我们可以使用栈来保存计算过程中求得的系数，所有系数求解完毕后再逆序输出即可。

代码实现如下：

/**
 * 十进制转为二进制
 *
 * @return 十进制数对应的二进制数
 */
public static String decimal2BinaryString(int decimal) {
    // 如果十进制为0，则直接返回0
    if (decimal == 0) {
        return "0";
    }
    // 使用栈来保存先求出来的系数
    Deque<Integer> stack = new ArrayDeque<>();
    int r = decimal;
    int m;
    while (r != 0) {
        // 求当前最后一个系数
        m = r % 2;
        // 求当前商，并赋值回r，做下一轮运算
        r = r >> 1;
        // 将当前系数保存到栈中
        stack.push(m);
    }
    // 依次将保存在栈中的数据取出，拼接成二进制
    StringBuilder builder = new StringBuilder(stack.size());
    while (!stack.isEmpty()) {
        builder.append(stack.pop());
    }
    // 返回二进制字符串
    return builder.toString();
}

测试代码如下：

System.out.println(decimal2BinaryString(1024));

输出结果如下：

10000000000

符合我们的预期。