2-二进制-计算机程序的细胞

一个数的大小，就是它各个位置的数字乘以对应进制的该数字所在位置（从低位到高位的位置）减 1 次方的和。

引出问题：为什么是十进制？

我们的日常生活中，大都采取十进制，比如 10 厘米等于 1 分米，10 两等于 1 斤，这是为什么呢？

这是习惯决定的！

因为我们有 10 个手指，在没有纸笔和计算器的年代，我们是采用数手指的方式来计数的，这样很方便，久而久之，就形成了习惯。所以，十进制不是一个科学性的定义，而是一个习惯性的定义。

我们知道十进制有两个特点：

只有 0～9 这十个数字，大于 9 的就要用两位数字来表示。
计算的时候满 10 就要进 1，高位上的数字是相邻低位的 10 倍。

废话？

不，往下看！

追根溯源：十进制的基本规则

我们假设 N=10，那么上面两个点换种说法就是：

N 进制只有 0 到（N-1）这 N 个数字，大于（N-1）的就要用两位数字表示。计算的时候满 N 就要进 1，高位上的数字是相邻低位的 N 倍。好，没毛病。

在十进制中，abc = a×100 + b×10 + c×1 也就是：abc = a×10^2 + b×10^1 + c×10^0，那么既然 N=10，那就是：abc = a× N^2 + b× N^1 + c× N^0，也没毛病。

所以，我们可以得到结论：对于十进制来说，任意一个数字，它的大小就是各个位置的数字，乘以 10 的这个位置（从低位到高位的位置）减 1 次方的和。

比如，上面的 abc：

abc = a×10^2 + b×10^1 + c×10^0

从低位往高位看，c 在第 1 位，b 在第 2 位，a 在第 3 位，所以它们的位置依次是 1、2、3，那么这些位置减 1，就分别是 0、1、2，那么 10 的“位置减 1”次方就是：10^0、10^1、10^2 ，那么对应数字乘以 10 的位置减 1 次方的和就是：a ×10^2 + b×10^1 + c×10^0。

这正是上述的结论。

那么，既然 N=10 都没毛病，那么上述结论就变成：对于 N 进制来说，任意一个数字，它的大小就是各个位置的数字，乘以 N 的这个位置（从低位到高位的位置）减 1 次方的和。

这正是文章开头的结论。

这到底对不对呢？答案已经有了。

打开格局：进制的最基础原理

我们上面得出了一个结论：

对于 N 进制来说，任意一个数字，它的大小就是：各个位置的数字，乘以 N 的这个位置（从低位到高位的位置）减 1 次方的和。

这是针对十进制演变来的的，那么，如果不是十进制呢？如果是二进制呢？那么就是：

对于二进制来说，任意一个数字，它的大小就是：各个位置的数字，乘以 2 的这个位置（从低位到高位的位置）减 1 次方的和。

我们让 N=2，然后来验证下，还是 abc：

abc = a × 2^2 + b × 2^1 + c × 2^0

又因为这是二进制，最大的数字就是 2-1，也就是 1，所以 abc 只能取 0 或 1。

如果 abc 是 110，那么就是: 1×4+1×2+0×11×4+1×2+0×1，也就是 6，搜索一下这明显是对的。我们看到，这跟十进制的计算没什么区别，也就是说，这个结论可以用于任何进制。

所以，我们上述结论是对的：

对于 N 进制来说，任意一个数字，它的大小就是各个位置的数字，乘以 N 的这个位置（从低位到高位的位置）减 1 次方的和。

这正是文章开头给出的结论。

由此，我们可以得出一个结论：N 进制的特点。

最大数字是 N-1，大于 N 就用两位数表示；高位的数字是低位的 N 倍。
也就是上述的结论。

好，现在你应该会表示并且计算二进制了，那么计算机为什么采用二进制呢？

触类旁通：计算机为什么用二进制？

因为简单！

计算机的底层是基于晶体管实现的，可以简单地理解为一组开关，打开就表示 1，关闭就表示 0，所以，采用二进制的话，计算机只需要简单地打开/关闭这些开关即可。

事物只有两种状态：有和无！用数字表示就是 0 和 1！

假设我们的计算机有 1 个开关，打开表示天亮，关闭表示天黑；打开表示对，关闭表示错；打开表示 1，关闭表示 0，这种例子有很多。那么如果是十进制呢？用谁表示打开，用谁表示关闭呢？又怎么表示 1，怎么表示 9 呢？太麻烦了！

我们来看二进制的最大优点：位运算。

我们高中时候都学过真值表，学了与或运算，如下：

p	q	p与q	p或q
0	0	0	0
1	0	0	1
0	1	0	1
1	1	1	1

我们知道：p 与 q 等于取交集，全部为 1 才为 1；p 或 q 等于取并集，全部为 0 才为 0。

OK，现在我们是二进制，只有 0 和 1。那么根据上述法则:

000100∩011=000，100∪011=111。

好，那么有个问题：给定一个数 n，怎么判断 n 是不是 2 的 n 次方呢？

很简单啊，直接求余就行了。

void is2Power(int n) {
    if (n <= 0) return false;
    int temp = n;
    while (temp > 1) {
        if (temp % 2 != 0) return false;
        temp /= 2;
    }
    return true;
}

嗯，代码没毛病，不过不够好。看下面代码：

public boolean isPowerOfTwo(int n) {
    return (n>0) && ((n & (n - 1)) == 0);
}

我们知道，10 的 n 次方最高位是 1，其他位都是 0；2 的 n 次方也是同理。也就是说：如果一个数 a 是 2 的 n 次方，那么 a 的最高位就是 1，其他位全是 0；那么，a-1 呢，就变成高位是 0，其他位全是 1 了。

比如：a = 10000，a-1 就是 01111，根据真值表，我们知道:

10000∩01111=0

所以如果 a 是 2 的 n 次方，那么就有:

a∩(a−1)=0

根据这个特性，我们只需要进行简单的按位与运算，就能很快得到正确的结果。这就是位运算的强大之处。大家可以在 leetcode 上试一下，对比下运行速度便知。

灵活运用二进制的位运算不仅能提高速度，熟练使用二进制还能节省内存。

在很多人的认知中，最省内存的就是基本数据类型，也就是布尔值、短整型、byte 类型等。

但是，这不是最省的。比如，我要存储一个人的年龄和性别，我们可以用两个字段：

int age;
boolean isMan;

这大概是所有人的写法了，也确实符合逻辑，但是，我们可以用更少的空间来记录的。我们知道，一个人的年龄最多也就是三位数，一个人的性别要么是男、要么是女，雌雄同体和人妖除外。

那么，一位数就能表示性别，三位数就能表示年龄。也就是说，一个二进制就能表示性别：0 表示女，1 表示男。人的年龄很少超过 120 岁，而一个 byte 最大表示 127，我们用一个 byte 就能表示年龄，一个 byte 是 8 位二进制，那就是说，我们只需要 9 个二进制位就能表示人的年龄和性别。也就是两个 byte。而一个 int 是 4 个 byte 呢，这样我们就直接节省了一半以上的内存。

那么二进制怎么表示一个 32 岁的男性呢？像这样：1_0010_0000，我们用首位的 1 表示性别，后面的 8 位表示年龄。这样只需要两个 byte 就足够。

有人可能会说：这有点小题大做啊，至于吗？

嗯，对于大部分场景，是意义不大的，但是对于一些很多人用的公共库、工程代码以及一些追求极致的设备上，这就很重要了。

比如 Java 的字节码，我们知道，我们写的语言都是最后要跑在 CPU 里面的，而 CPU 只认识机器码，也就是二进制；所以我们写的代码要有个编译过程，Java 语言的这个过程的产物就是字节码文件，这个文件要尽可能紧凑，尽可能小，那么上述的小题就不大做了。

我们可能会看到一些源码里面有很多 flag 变量，对这些 flag 进行按位与或按位或运算来检测标记，从而判断是否开启了某个功能。他为什么不直接用布尔值呢？很简单，这样效率高还节省内存。比如Android源码中的测量过程，就用到MeasureSpec这个类，它是一个int类型，用高两位表示测量模式，用低 30 位表示测量值，这样只用一个变量就保存了多个信息，有兴趣的同学可以去看下相关源码。

归纳总结：本节要点

本节的知识点很简单，可以简单概括为两点：

N 进制的数字范围为：[0, N-1]，大于 N-1 的就要用两位数字来表示。
对于 N 进制来说，任意一个数字，它的大小就是各个位置的数字，乘以 N 的这个位置（从低位到高位的位置）减 1 次方的和。

所以，我们不必纠结于几进制了，只要理解或者牢记上述两个结论，即使是 100 进制，也能直接把它按在地上摩擦。

本节的每个小标题都有个前缀，这就是本小册的核心思想：自顶向下再向上的思维。因为底层原理共通，所以我们先站在 A 的角度理透 A 的逻辑，然后去研究 A 的底层，然后再利用 A 的底层去扩展到 B 的底层，最后，利用 B 的底层，就可以推出 B 的逻辑。这是快速扩张知识面的手段之一，也是解决非认知领域知识的方法之一，希望大家能够理解并运用。

下一节我们就详细讲解二进制中的位运算的法则和实现原理，我们下一节见。