程序员的数学(一本为程序员朋友们写的数学书)

2-1是什么
0所起的作用
0的作用：占位
0的作用：统一标准，简化规则
日常生活中的0
人类的极限和构造的发现
重温历史进程
为了超越人类的极限
本章小结
第2章逻辑——真与假的二元世界
本章学习内容
为何逻辑如此重要
逻辑是消除歧义的工具
致对逻辑持否定意见的读者
乘车费用问题——兼顾完整性和排他性
车费规则
命题及其真假
有没有“遗漏”
有没有“重复”
画一根数轴辅助思考
注意边界值
兼顾完整性和排他性
使用if语句分解问题
逻辑的基本是两个分支
建立复杂命题
逻辑非——不是A
逻辑与——A并且B
逻辑或——A或者B
异或——A或者B(但不都满足)
相等——A和B相等
蕴涵——若A则B
囊括所有了吗
德·摩根定律
德·摩根定律是什么
对偶性
卡诺图
二灯游戏
首先借助逻辑表达式进行思考
学习使用卡诺图
三灯游戏
包含未定义的逻辑
带条件的逻辑与(&&)
带条件的逻辑或(II)
三值逻辑中的否定(!)
三值逻辑的德·摩根定律
囊括所有了吗
本章小结
第3章余数——周期性和分组
本章学习内容
星期数的思考题(1)
思考题(100天以后是星期几)
思考题答案
运用余数思考
余数的力量——将较大的数字除一次就能分组
星期数的思考题(2)
思考题(10100天以后是星期几)
提示：可以直接计算吗
思考题答案
发现规律
直观地把握规律
乘方的思考题
思考题(1234567987654321)
提示：通过试算找出规律
思考题答案
回顾：规律和余数的关系
通过黑白棋通信
思考题
提示
思考题答案
奇偶校验
奇偶校验位将数字分为两个集合
寻找恋人的思考题
思考题(寻找恋人)
提示：先试算较小的数
思考题答案
回顾
铺设草席的思考题
思考题(在房间里铺设草席)
提示：先计算一下草席数
思考题答案
回顾
一笔画的思考题
思考题(哥尼斯堡七桥问题)
提示：试算一下
提示：考虑简化一下
提示：考虑人口和出口
思考题答案
奇偶校验
本章小结
第4章数学归纳法——如何征服无穷数列
本章学习内容
高斯求和
思考题(存钱罐里的钱)
思考一下
小高斯的解答
讨论一下小高斯的解答
归纳
数学归纳法——如何征服无穷数列
0以上的整数的断言
高斯的断言
什么是数学归纳法
试着征服无穷数列
用数学归纳法证明高斯的断言
求出奇数的和——数学归纳法实例
奇数的和
通过数学归纳法证明
图形化说明
黑白棋思考题——错误的数学归纳法
思考题(黑白棋子的颜色)
提示：不要为图所惑
思考题答案
编程和数学归纳法
通过循环表示数学归纳法
循环不变式
本章小结
第5章排列组合——解决计数问题的方法
本章学习内容
计数——与整数的对应关系
何谓计数
注意“遗漏”和“重复”
植树问题——不要忘记0
植树问题思考题
加法法则
加法法则
乘法法则
乘法法则
置换
置换
归纳一下
思考题(扑克牌的摆法)
排列
排列
归纳一下
树形图——能够认清本质吗
组合
组合
归纳一下
置换、排列、组合的关系
思考题练习
重复组合
也要善于运用逻辑
本章小结
第6章递归——自己定义自己
本章学习内容
汉诺塔
思考题(汉诺塔)
提示：先从小汉诺塔着手
思考题答案
求出解析式
解出汉诺塔的程序
找出递归结构
再谈阶乘
阶乘的递归定义
思考题(和的定义)
递归和归纳
斐波那契数列
思考题(不断繁殖的动物)
斐波那契数列
帕斯卡三角形
什么是帕斯卡三角形
递归定义组合数
组合的数学理论解释
递归图形
以递归形式画树
实际作图
谢尔平斯基三角形
本章小结
第7章指数爆炸——如何解决复杂问题
本章学习内容
什么是指数爆炸
思考题(折纸问题)
指数爆炸
倍数游戏——指数爆炸引发的难题
程序的设置选项
不能认为是“有限的”就不假思索
二分法查找——利用指数爆炸进行查找
寻找犯人的思考题
提示：先思考人数较少的情况
思考题答案
找出递归结构以及递推公式
二分法查找和指数爆炸
对数——掌握指数爆炸的工具
什么是对数
对数和乘方的关系
以2为底的对数
以2为底的对数练习
对数图表
指数法则和对数
对数和计算尺
密码——利用指数爆炸加密
暴力破解法
字长和安全性的关系
如何处理指数爆炸
理解问题空间的大小
四种处理方法
本章小结
第8章不可解问题——不可解的数、无法编写的程序
本章学习内容
反证法
什么是反证法
质数思考题
反证法的注意事项
可数
什么是可数
可数集合的例子
有没有不可数的集合
对角论证法
所有整数数列的集合是不可数的
所有实数的集合是不可数的
所有函数的集合也是不可数的
不可解问题
什么是不可解问题
存在不可解问题
思考题
停机问题
停机
处理程序的程序
什么是停机问题
停机问题的证明
写给尚未理解的读者
不可解问题有很多
本章小结
第9章什么是程序员的数学——总结篇
本章学习内容
何为解决问题
认清模式，进行抽象化
由不擅长催生出的智慧
幻想法则
程序员的数学

.　　人类不擅长重复劳动，很容易厌倦，有时还会出错，但人类擅长解决问题。与此相对，计算机擅长重复劳动，但不能自行解决问题。
　　于是，人机合力，如虎添翼。
　　遇到难题，光靠人类不能解决，光靠计算机也不能解决。而人机合力就能解决问题。
　　这也是本书要传达的主旨之一。
　　不过，编写程序也非易事，无论人类和计算机如何齐心合力，总有解决不了的问题。
　　本书也对人类和计算机的极限进行了分析。
　　希望你在读完本书后能对以程序为媒介的人机合作有更深刻的理解。
　　本书面向的读者
　　本书主要面向的读者是程序员。不过若你对编程或数学感兴趣，读起来也会一样有意思。
　　你不需要精通数学。书中不会出现Σ和等很难的算式，因此自认为数学不太好的读者也完全可以阅读。阅读本书只需具备四则运算（＋－ ×÷）和乘方（23=2×2×2）等基础知识。除此以外的知识在书中皆有说明。
　　如果你对数字和逻辑感兴趣，可能会更喜欢本书。
　　你也不需要精通编程。不过如果稍有一些编程经验，可能会更容易理解本书内容。书中有个别例子是用C 语言写的程序，不过即使不懂C 语言也不妨碍理解。
　　本书结构
　　本书各章内容可以按任意顺序阅读，但笔者推荐从第1 章开始按顺序阅读。
　　第1 章对0 进行讨论。以按位计数法为核心，学习如何用0 来简化规则，并对“无即是有”的意义进行了思考。
　　第2 章学习使用逻辑来整理繁琐的内容。介绍逻辑表达式、真值表、德·摩根定律、三值逻辑、卡诺图等。
　　第3 章讨论余数。我们要记住“余数就是分组”的观点。对于一些难题，有时只要找到周期性规律就能解决。
　　第4 章学习数学归纳法。数学归纳法只需要两个步骤就能证明无穷的断言。本章还会举例介绍使用循环不变式写出正确的循环。
　　第5 章学习排列组合等计数方法。计数的关键在于“认清对象的性质”。
　　第6 章学习自己定义自己的递归。通过汉诺塔、斐波那契数列、分形图形等，练习从复杂事物中发现递归结构。
　　第7 章学习指数爆炸。计算机也很难解决含有指数爆炸的问题。我们将在这里思考研究如何将指数爆炸为我所用，解决大型问题。另外本章还将以二分法检索为例，学习将问题空间一分为二的意义。
　　第8 章以停机问题为例，来说明许多程序上的问题是计算机如何发展都解决不了的。
　　本章也会学到反证法和对角论证法。
　　第9 章回顾本书学习内容，思考人类全面把握结构的能力对解决问题有多大帮助，以及人机协作具有何种意义。
　　致谢
　　首先要感谢马丁·伽德纳。小时候我痴迷于阅读您所著的《数学游戏》，至今仍记忆犹新。
　　此外，还要感谢支持我的广大读者和为我祈祷的基督教朋友们。以下各位为本书提出了宝贵建议并给予了极大帮助，在此深表谢意（按日语五十音图顺序）：天野胜、石井胜、岩泽正树、上原隆平、佐藤勇纪、武笠夏子、前原正英、三宅喜义。
　　特别感谢在本书编写过程中给予我极大关怀和支持的SoftBank 出版有限公司的野泽喜美男主编。
　　感谢一直鼓励我的爱妻和两个儿子。
　　本书献给在餐桌上教我方程式乃至微积分的父亲。父亲，谢谢您！
　　2005 年2 月
　　结城 浩
　　

.　　思考一下
　　本题要求算出第100 天时存钱罐的总金额。要求出第100 天的金额，只要计算1 + 2 + 3+ … + 100 的值就行了。那么，具体应如何计算呢？
　　一般来说，最先想到的肯定是机械地将它们逐个相加。1 加2，再加3，再加4，…再加99，再加100。只要这样加起来就能得出答案了吧。如果说笔算比较花时间的话，也可以使用计算器或编程来计算。
　　不过，德国数学家高斯在9 岁时遇到了同样的问题，却马上得出了答案。当时他既没用计算器也没用电脑。那么，他究竟是如何做到的呢？
　　小高斯的解答
　　小高斯是这么考虑的。
　　1 + 2 + 3 + …+ 100 顺次计算的结果和100 + 99 + 98 + …+ 1 逆向计算的结果应该是相等的。那么，就将这两串数字像下面那样纵向地相加。
　　如此一来，就变成了101 + 101 + 101 + …+ 101 那样100 个101 相加的结果。这样的计算就非常简单了。只要将101 乘以100 即可，结果为10100。不过10100 是要求的数的2 倍，因此还得除以2，答案为5050。
　　答案：5050 元。
　　讨论一下小高斯的解答
　　小高斯的方法可谓绝妙非凡!
　　为了便于大家理解，我们将高斯的方法用图来表示。求1 + 2 + 3 + …+ 100 的结果，相当于计算图4-1 所示的排列成阶梯型的瓷砖块数。
　　图4-1 将高斯的方法图形化
　　高斯则又做了一个一模一样的阶梯，并将两者合二为一，组成了一个长方形。
　　图4-2 将2个阶梯组合成1个长方形
　　由2 个阶梯组合而成的长方形，纵向有101 块瓷砖，横向有100 块瓷砖。因此，该长方形由101×100 = 10100 块瓷砖构成。而所求的瓷砖块数就是10100 的一半，即5050。
　　我们来说一说高斯的计算效率。使用他的方法不需要花费力气逐个相加。只要将两端的1 和100 相加，结果乘以100 再除以2 就行了。
　　现在，假设我们不是从1 加到100，而是从1 加到10000000000（100 亿）。这次我们就不能采用逐一相加的方法了。因为即使计算器1 秒能完成1 次加法计算，加到100 亿也得花300 年以上的时间。
　　不过，如果使用高斯的方法，那么从1 加到100 亿也只要1 次加法、1 次乘法、1 次除法运算即可完事。我们来实际计算一下。
　　高斯（Karl Friedrich Gauss, 1777 - 1855）后来成为了历史上著名的数学家。
　　归纳
　　高斯运用了以下等式。
　　这里，使用变量n，将"1 到100"归纳为"1 到n"。这样，上面的等式就变为如下形式
　　那么，这个等式对于0 以上的任意整数n 都成立吗？即n 为100、200，或者100 万、100 亿时该等式也都成立吗？如果成立的话，又如何来证明呢？
　　这种时候就要用到数学归纳法了。数学归纳法是证明"断言对于0 以上的所有整数n都成立"的方法。
　　学生："对于所有整数n"，总觉得这种说法别扭。
　　老师：别扭？
　　学生：会感觉头脑中充满了整数。
　　老师：那么，改为"对于任一整数n"怎么样？
　　学生：啊！那样感觉稍微舒服些。
　　老师：其实说的是一回事呢！
　　数学归纳法-- 如何征服无穷数列
　　本节，我们就来讨论一下数学归纳法的相关内容。首先，从"0 以上的整数的断言"开始学起，然后使用数学归纳法来证明高斯的断言 。
　　0以上的整数的断言
　　0 以上的整数n 的断言"，就是能够判定0，1，2…等各个整数为"真"或"假"的断言。这样说明或许难以理解，下面就举几个例子。.
　　● 例1
　　o 断言A (n ) ：n ×2 为偶数。
　　A(n)，即"n×2 为偶数"的断言。由于n 为0 时，0×2 = 0 为偶数，所以A(0) 为真。
　　A(1) 又怎么样呢？因为1×2 = 2 为偶数，所以A(1) 也为真。
　　那是否可以说断言A(n)，对于0 以上的所有整数n 都为真（对于0 以上的任意整数n都成立）呢？
　　对！可以这么说。因为0 以上的任意整数乘以2 的结果都为偶数，所以对于0 以上的所有整数，断言A(n) 都为真。
　　● 例2
　　o 断言B (n ) ：n ×3 为奇数
　　那么，断言B(n) 又将如何呢？该断言对于0 以上的所有整数n 都成立吗？
　　例如，假设n 为1，则断言B(1) 就是"1×3 为奇数"，这个结果为真。但不能说对于0以上的所有整数n，断言B(n) 都为真。因为假设n 为2，则n×3 的值为2×3 = 6。而6 是偶数，所以断言B(2) 不为真（为假）。
　　n = 2 是推翻"断言B(n) 对于0 以上的所有整数n 都成立"的反例。
　　● 其他例子
　　那么请思考一下，在下面4 个断言中，对于0 以上的所有整数n 都成立的有哪些。
　　o 断言C (n ) ：n +1 为 0 以上的整数。
　　o 断言D (n ) ：n -1 为 0 以上的整数。
　　o 断言E (n ) ：n ×2 为 0 以上的整数。
　　o 断言F (n ) ：n ÷2 为 0 以上的整数。
　　断言C(n)，对于0 以上的所有整数n 都成立。因为若n 为0 以上的整数，则n + 1 肯定是0 以上的整数。
　　断言D(n)，对于0 以上的所有整数n 不成立。例如，断言D(0) 为假。因为0 -1 = -1，不是0 以上的整数。n = 0 是唯一的反例。
　　断言E(n)，对于0 以上的所有整数n 都成立。
　　断言F(n)，对于0 以上的所有整数n 不成立。因为当n 为奇数时，n÷2 的结果不是整数。
　　高斯的断言
　　在讨论了" 0 以上的整数n 的断言"之后， 我们将话题转回高斯的断言。
　　可以使用下述有关n 的断言形式来表现高斯的观点。
　　o 断言G(n) ：0 到n 的整数之和为 。
　　接下来要证明的是，"G(n) 对于0 以上的所有整数n 都成立"。可以通过描画前面的阶梯状的图（图4-1）来证明，但是有人可能会有这样的疑问：0 以上的整数有0, 1, 2, 3，…等无穷个数字，而图中表现的只是其中一种情况。 当G(1000000) 时也成立吗？
　　确实，0 以上的整数有无穷个。这就要通过引入"数学归纳法"来证明了。使用数学归纳法能够进行0 以上的所有整数的相关证明。
　　什么是数学归纳法
　　数学归纳法是证明有关整数的断言对于0 以上的所有整数（0、1、2、3…）是否成立时所用的方法。
　　假设现在要用数学归纳法来证明"断言P（n）对于0 以上的所有整数n 都成立"。
　　数学归纳法要经过以下两个步骤进行证明。这是本章的核心内容，请大家仔细阅读。
　　o 步骤1 ：
　　证明"P (0) 成立"。
　　o 步骤2 ：
　　证明不论k 为0 以上的哪个整数，"若P (k ) 成立，则P (k +1) 也成立"
　　在步骤1 中，要证明当k 为0 时断言P(0) 成立。我们将步骤1 称作基底（base）。
　　在步骤2 中，要证明无论k 为0 以上的哪个整数，"若P( k ) 成立，则P (k+1) 也成立"。
　　我们将步骤2 称作归纳(induction)。该步骤证明断言若对于0 以上的某个整数成立，则对于下一个整数也成立。
　　若步骤1 和步骤2 都能得到证明，就证明了"断言P (n) 对于0 以上的所有整数n 都成立"。
　　以上就是数学归纳法的证明方法。
　　试着征服无穷数列
　　数学归纳法通过步骤1（基底）和步骤2（归纳）两个步骤，证明断言P(n) 对于0 以上的所有整数n 都成立。
　　为什么只通过两个步骤的证明，就能证明无穷的n 呢？请作如下思考。
　　o 断言P (0) 成立。
　　理由：步骤1 中已经证明。
　　o 断言P (1) 成立。
　　理由：P (0) 已经成立，并且步骤2 中已证明若P (0) 成立，则P (1) 也成立。
　　o 断言P (2) 成立。
　　理由：P (1) 已经成立，并且步骤2 中已证明若P (1) 成立，则P (2) 也成立。
　　o 断言P (3) 成立。
　　理由：P (2) 已经成立，并且步骤2 中已证明若P (2) 成立，则P (3) 也成立。
　　这样循环往复，可以说断言P(n) 对于任意数字n 都成立。无论n 为多大的数字都没关系。因为即使设n 为10000000000000000，经过机械式地反复执行步骤2，终究可以证明P（10000000000000000）成立。
　　这种数学归纳法的思路可以比喻为"推倒多米诺骨牌"。
　　假设现在有很多多米诺骨牌排成一列。只要保证以下两个步骤，那么无论多米诺骨牌排得有多长最终都能倒下。
　　o 步骤1
　　确保让第0 个多米诺骨牌（排头的多米诺骨牌）倒下。
　　o 步骤2
　　确保只要推倒第k 个多米诺骨牌，那么第k + 1 个多米诺骨牌也会倒下。推倒多米诺骨牌的两个步骤和数学归纳法的两个步骤一一对应。
　　数学归纳法并不像"推倒多米诺骨牌"那样关注用时。数学归纳法和编程不同，往往使用的是忽略时间的方法。这就是数学和编程之间最大的差异。
　　用数学归纳法证明高斯的断言
　　下面我们就以证明高斯的断言G(n) 为例具体看看数学归纳法。首先讨论断言G(n)。
　　o 断言G(n) ：0 到n 的整数之和与 相等。
　　使用数学归纳法就需要通过步骤1（基底）和步骤2（归纳）来证明。
　　● 步骤1 ：基底的证明
　　证明G(0) 成立。
　　G(0) 就是"0 到0 的整数之和与 相等"。
　　这可以通过直接计算证明。0 到0 的整数之和是0，
　　至此，步骤1 证明完毕。
　　● 步骤2 ：归纳的证明
　　证明当k 为0 以上的任一整数时，"若G(k) 成立，则G(k + 1) 也成立"
　　现假设G(k) 成立。即假设"0 到k 的整数之和与 相等"。这时，以下等式成立。
　　假设成立的等式G(k)
　　下面，我们来证明G(k + 1) 成立。
　　要证明的等式G(k+1)
　　G(k + 1) 的左边使用假设的等式G(k) 可以进行如下计算。
　　而G(k + 1)的右边可以进行如下计算。
　　G(k + 1) 的左边和右边的计算结果相同。
　　由此，从G(k) 到G(k + 1) 推导成功，步骤2 得到了证明。
　　至此，通过数学归纳法的步骤1 和步骤2 都证明了断言G(n)。也就是说通过数学归纳法证明了断言G(n) 对于0 以上的任意整数n 都成立。
　　求出奇数的和--数学归纳法实例
　　本节，我们使用数学归纳法来证明另一个断言。
　　奇数的和
　　请证明以下断言Q(n) 对于1 以上的所有整数n 都成立。
　　o 断言Q (n ) ：1 + 3 + 5 + 7 + … +（2 × n -1） = n2
　　Q(n) 是比较有意思的断言。按从小到大的顺序将n 个奇数相加，得到n2，即平方数n ×n。
　　这对吗？在证明之前，先通过较小的数n = 1、2、3、4、5 判断Q(n) 的真假。
　　o 断言Q (1) ：1 = 12
　　o 断言Q (2) ：1 + 3 = 22
　　o 断言Q (3) ：1 + 3 + 5 = 32
　　o 断言Q (4) ：1 + 3 + 5 + 7 = 42
　　o 断言Q (5) ：1 + 3 + 5 + 7 + 9 = 52
　　通过以上计算发现断言确实是成立的。
　　……
　　
　　

.　　下面介绍 10进制计数法。
　　什么是 10进制计数法
　　我们平时使用的是 10进制计数法。
　　使用的数字有0、1、2、3、4、5、6、7、8、9共 10种 a。
　　数位有一定的意义，从右往左分别表示个位、十位、百位、千位……
　　
　　以上规则在小学数学中都学到过，日常生活中也一直在用，是众所周知的常识。在此权当复习，后面我们将通过实例来了解一下 10进制计数法。
　　分解 2503
　　首先，我们以 2503这个数为例。 2503表示的是由 2、5、0、3这 4个数字组成的一个称作 2503的数。
　　
　　这样并排的数字，因数位不同而意义相异。
　　2表示“1000的个数”。
　　5表示“100的个数”。
　　0表示“10的个数”。
　　3表示“1的个数”。
　　
　　a这里的 “种”指的是数字的种类，用来说明 10进制和 2进制中数字复杂程度的差异。如 2561中包含四种数字，而 1010中只包含两种数字。 ——译者注
　　综上所述， 2503这个数是 2个 1000、5个 100、0个 10和 3个 1累加的结果。用数字和语言来冗长地说明有些无趣，下面就用图示来表现。
　　2×1000 + 5×100 + 0×10 + 3×1
　　如图，将数字的字体大小加以区别，各个数位上的数字 2、5、0、3的意义便显而易见了。 1000是 10×10×10，即 10（310的 3次方）， （10的 2次方）
　　100是 10×10，即 102。因此，也可以写成如下形式（请注意箭头所示部分）。
　　2×103
　　 + 5×102
　　 + 0×10 + 3×1
　　再则， 10是 101（10的 1次方），1是 100(10的 0次方 )，所以还可以写成如下形式。
　　2×103 + 5×102 + 0×101
　　 + 3×100
　　
　　千位、百位、十位、个位，分别可称作 103的位、 102的位、 101的位、 100的位。 10进制计数法的数位全都是 10n的形式。这个 10称作 10进制计数法的基数或底。基数 10右上角的数字 ——指数，是 3、2、1、0这样有规律地顺次排列的，这点请记住。
　　
　　3210
　　2×103 + 5×102 + 0×101 + 3×100
　　
　　2进制计数法
　　下面讲解 2进制计数法。
　　什么是 2进制计数法
　　计算机在处理数据时使用的是 2进制计数法。从 10进制计数法类推，便可很快掌握它的规则。
　　??使用的数字只有0、1，共 2种。
　　??从右往左分别表示 1位、2位、4位、8位……
　　用 2进制计数法来数数，首先是 0，然后是 1，接下去 ……不是 2，而是在 1上面进位变成 10，继而是 11，100，101……
　　表 1-1展示了 0到 99的数的 10进制计数法和 2进制计数法。
　　 0到 99的数的 10进制计数法和 2进制计数法
　　
　　分解 1100
　　在此，我们以 2进制表示的 1100（2进制数的 1100）为例来探其究竟。
　　
　　和 10进制计数法一样，并排的数字，各个数位都有不同的意义。从左往右依次为：
　　1表示“8的个数”。
　　1表示“4的个数”。
　　0表示“2的个数”。
　　0表示“1的个数”。
　　
　　也就是说， 2进制的 1100是 1个 8、1个 4、0个 2和 0个 1累加的结果。这里出现的 8、 4、2、1，分别表示 23、22、21、20。即 2进制计数法的 1100，表示如下意思。
　　
　　3210
　　1×23 + 1×22 + 0×21 + 0×20
　　如此计算就能将 2进制计数法的 1100转换为 10进制计数法。
　　3 1×22+0×21+0×20
　　1×2 + 1×8+1×4+0×2+0×1 8+4+0+0 12
　　由此可以得出， 2进制的 1100若用 10进制计数法来表示，则为 12。
　　基数转换
　　接下来我们试着将 10进制的 12转换为 2进制。这需要将 12反复地除以 2（12除以 2，商为 6；6再除以 2，商为 3；3再除以 2……），并观察余数为 “1”还是 “0”。余数为 0则表示 “除完了 ”。随后再将每步所得的余数的列（ 1和 0的列）逆向排列，由此就得到 2进制表示了。
　　 用2进制表示12
　　
　　
　　同样地，我们试将 10进制的 2503转换为 2进制计数法。
　　
　　我们从图 1-2可以知道 2503用 2进制表示为 100111000111。各个数位的权重如下：
　　1×211+0×210+0×29+1×28+1×27+1×26+0×25+0×24 +0×23+1×22+1×21+1×20
　　在 10进制中，基数为 10，各个数位是以 10n的形式表现的。而 2进制中，基数为 2，各个数位是以 2n的形式表现的。从 10进制计数法转换为 2进制计数法，称作 10进制至 2进制的基数转换。
　　计算机中为什么采用 2进制计数法
　　计算机中一般采用 2进制计数法，我们来思考一下原因。计算机在表示数的时候，会使用以下两种状态。
　　开关切断状态
　　开关连通状态
　　
　　虽说是开关，但实际上并不需要机械部件，你可以想象成是由电路形成的 “电子开关”。总之，它能够形成两种状态。这两种状态，分别对应 0和 1这两个数字。
　　…0
　　…1
　　
　　1个开关可以用 0或 1来表示，如果有许多开关，就可以表示为许多个 0或 1。你可以
　　想象这里排列着许多开关，各个开关分别表示 2进制中的各个数位。这样一来，只要增加
　　开关的个数，不管是多大的数字都能表示出来。
　　当然，做成能够表示 0～ 9这 10种状态的开关，进而让计算机采用 10进制计数法，
　　这在理论上也是可能的。但是，与 0和 1的开关相比，必定有更为复杂的结构。另外，请比较一下图 1-3和图 1-4所示的加法表。 2进制的表比 10进制的表简单得多吧。
　　若要做成 1位加法的电路，采用 2进制要比 10进制更为简便。
　　不过，比起 10进制， 2进制的位数会增加许多，这是它的缺点。例如，在 10进制中
　　2503只有 4位，而在 2进制中要表达同样的数则需要 100111000111共 12位数字。这点从
　　表 1-2中也显而易见。
　　人们觉得 10进制比 2进制更容易处理，是因为 10进制计数法的位数少，计算起来不
　　容易发生错误。此外，比起 2进制，采用 10进制能够简单地通过直觉判断出数值的大小。
　　人的两手加起来共有 10个指头，这也是 10进制更容易理解的原因之一。
　　
　　 10进制的加法表
　　
　　2进制的加法表
　　
　　不过，因为计算机的计算速度非常快，位数再多也没有关系。而且计算机不会像人类那样发生计算错误，不需要靠直觉把握数字的大小。对于计算机来说，处理的数字种类少、计算规则简单就最好不过了。
　　让我们来总结一下。
　　10进制计数法中，位数少，但是数字的种类多。
　　→对人类来说，这种比较易用。
　　2进制计数法中，数字的种类少，但是位数多。
　　→对计算机来说，这种比较易用。
　　
　　鉴于上述原因，计算机采用了 2进制计数法。
　　人类使用 10进制计数法，而计算机使用 2进制计数法，因此计算机在执行人类发出的任务时，会进行 10进制和 2进制间的转换。计算机先将 10进制转换为 2进制，用 2进制进行计算，再将所得的 2进制计算结果转换为 10进制。
　　
　　 人类使用计算机进行计算的情形
　　转换为2进制
　　转换为10进制
　　10101+10011
　　
　　使用2进制进行计算
　　
　　101000
　　
　　
　　按位计数法
　　下面来介绍按位计数法。
　　什么是按位计数法
　　我们学习了 10进制和 2进制两种计数法，这些方法一般称作按位计数法。除了 10进制和 2进制以外，还有许多种类的按位计数法。在编程中，也常常使用 8进制和 16进制计数法。
　　8进制计数法
　　8进制计数法的特征如下：
　　使用的数字有0、1、2、3、4、5、6、7共 8种。
　　80的位、81的位、82的位、83的位……（基数是8）
　　
　　21+19
　　40
　　16进制计数法
　　16进制计数法的特征如下：
　　使用的数字有0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F共 16种。
　　160的位、161的位、162的位、163的位……（基数是16）
　　
　　在 16进制计数法中，使用 A、B、C、D、E、F（有时也使用小写字母 a、b、c、d、e、
　　f）来表示 10以上的数字。
　　 N进制计数法
　　一般来说， N进制计数法的特征如下：
　　使用的数字有0，1，2，3，…， N-1，共 N种。
　　N 0的位、N 1的位、N 2的位、N 3的位……（基数是 N）
　　
　　例如， N进制计数法中， 4位数 a3a2a1a0为
　　a3× N3+ a2× N2+ a1× N1+ a0× N0（a3、a2、a1、a0是0～N-1中的数字。）
　　不使用按位计数法的罗马数字
　　按位计数法在生活中最为常见，因此人们往往认为这种方法是理所当然的。实际上，
　　在我们身边也有不使用按位计数法的例子。例如，罗马计数法。罗马数字至今还常常出现在钟表表盘上。
　　 使用罗马数字的钟表表盘
　　
　　还有，在电影最后放映的演职员名单中，也会出现表示年号的 MCMXCVIII等字母。这也是罗马数字。罗马计数法的特征如下：
　　数位没有意义，只表示数字本身
　　0
　　使用I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000)来记数
　　将并排的数字加起来，就是所表示的数。
　　
　　例如， 3个并排的 I（III）表示 3，并排的 V和 I（VI）表示 6，VIII表示 8。罗马数字的加法很简单，只要将罗马数字并排写就可以得到它们的和。比如，要计算 1+2，只要将表示 1的 I和表示 2的 II并排写作 III就行了。但是，数字多了可就不太简单了。
　　例如，计算 3+3并不是把 III和 III并排写作 IIIIII，而是将 5单独拿出来写作 V，所以 6就应该写作 VI。CXXIII（123）和 LXXVIII（78）的加法，也不能仅仅并排写作 CXXIIILXXVIII，而必须将 IIIII转换为 V，VV转换为 X，XXXXX转换为 L，再将 LL转换为 C，如此整理最后得到 CCI（201）。在 “整理 ”罗马数字的过程中，必须进行与按位计数法的进位相仿的计算。
　　罗马计数法中还有 “减法规则 ”。例如 IV，在 V的左侧写 I，表示 5-1，即 4（在钟表表盘上，由于历史原因也有将 4写作 IIII的）。让我们试着将罗马数字的 MCMXCVIII用 10进制来表示。
　　MCMXCVIII=（M）+（CM）+（XC）+（V）+（III） =（1000）+（1000-100）+（1000-10）+（5）+（3） = 1998
　　可以发现， MCMXCVIII表示的就是 1998。罗马数字真是费劲啊！
　　
　　指数法则
　　10的 0次方是什么
　　在 10进制的说明中，我们讲过 “1是 100（10的 0次方） ”，即 100=1。
　　也许有些读者会产生以下疑问吧。
　　102是“2个 10相乘 ”，那么 100不就是 “0个 10相乘 ”吗？这样的话，不应该是 1，而是 0吧？
　　这个问题的核心在哪里呢？我们来深入思考一下。问题在于 “10n是 n个 10相乘 ”这部分。在说 “n个 10相乘 ”时，我们自然而然会把 n想作 1，2，3…。因此，在说 “0个 10相乘 ”时，却不知道应该如何正确理解它的意义。
　　那么，暂且抛却 “n个 10相乘 ”这样的定义方式吧。我们从目前掌握的知识来类推，看看如何定义 10 0比较妥当。
　　众所周知， 103是 1000，102是 100，101是 10。
　　将这些等式放在一起，寻找它们的规律。
　　
　　103 =1000 102 =100 101 =10 100 =?
　　
　　
　　
　　1??10 1??10 1??10
　　
　　每当 10右上角的数字（指数）减 1，数就变为原先的 10分之 1。因此， 100就是 1。综上所述，在定义 10n（n包括 0）的值时可以遵循以下规则：
　　指数每减1，数字就变为原来的 10分之1。
　　10-1是什么
　　不要将思维止步于 100之处。对于 10-1（10的 -1次方），让我们同样套用这一规则（指数每减 1，数字就变为原来的 10分之 1）。
　　
　　100 ˙ 1 1
　　10_1˙
　　10 110_2˙
　　100 110_3˙ 1000
　　…
　　
　　1??10 1??10 1??10
　　规则的扩展
　　
　　首先让我们做一个小结。我们学习了 10n计数法的相关内容。起初，我们把 n为 1，2，3…时，即 101，102，103 …想作 “1个 10相乘 ”、“2个 10相
　　乘”、“3个 10相乘 ”……然后，我们抛却了 “n个 10相乘 ”的思维，寻找到了一个扩展规则：对于 10n，n每减 1，就变成原来的 10分之 1。
　　当 n为 0时，若套用 “10n为 n个 10相乘 ”的规则，着实比较费解。于是我们转而求助于 “n每减 1，就变成原来的 10分之 1”的规则 ”，定义出 100是 1（因为 101的 10分之 1就是 1）。
　　同样地， 10-1，10-2，10-3 …的值（即 n为 -1，-2，-3…时），也适用于这个扩展规则。
　　如此，对于所有的整数 n（…，-3，-2，-1，0，1，2，3，…），都能定义 10n的值。对于 10-3来说， “-3个 10相乘 ”的思维并不直观。但倘若套用扩展规则，即使 n是负数，也能 “定义出 ”10的 n次方的值。
　　对20进行思考
　　让我们用思考 100的方法，也思考一下 20的值吧。
　　25˙ 32
　　24
　　˙ 16
　　
　　23
　　˙ 8
　　
　　22
　　˙ 4
　　
　　21
　　˙ 2
　　
　　20
　　˙?
　　
　　由此可知，对于 2n来说， n每减 1，数值就变成原来的 2分之 1。 21的 2分之 1是 20，那么 20=1。在这里我想强调的是，不要将 20的值作为一种知识去记忆，我们更需要考虑的是，如
　　何对 20进行适当的定义，以期让规则变得更简单。这不是记忆力的问题，而是想象力的问题。请记住这种思维方式：以简化规则为目标去定义值。
　　1??2 1??2 1??2 1??2 1??2
　　2-1是什么
　　让我们参照 10-1的规则来思考 2-1。20除以 2，得到的是 2-1，即 2-1=12。
　　“2的 -1次方 ”在直觉上较难理解。鉴于规则的简单化和一致性， 2的 -1次方可以定
　　义为 2-1=21。同理， 2-2=212，2-3=213。
　　综上所述，可以总结出如下等式：
　　10+5 = 1×10×10×10×10×10 10+4 = 1×10×10×10×10 10+3 = 1×10×10×10 10+2 = 1×10×10 10+1 = 1×10 100 = 1 10-1 = 1÷10 10-2 = 1÷10÷10 10-3 = 1÷10÷10÷10 10-4 = 1÷10÷10÷10÷10 10-5 = 1÷10÷10÷10÷10÷10
　　2+5 = 1×2×2×2×2×2 2+4 = 1×2×2×2×2 2+3 = 1×2×2×2 2+2 = 1×2×2 2+1 = 1×2
　　20
　　= 1 2-1 = 1÷2 2-2 = 1÷2÷2 2-3 = 1÷2÷2÷2 2-4 = 1÷2÷2÷2÷2 2-5 = 1÷2÷2÷2÷2÷2
　　看了上面的等式之后，你应该就更能体会 100和 20为什么都等于 1了吧。
　　到这里，我们给之前所说的 “规则 ”取名为 “指数法则”。指数法则的表达式为
　　=Na+b
　　Na×Nb
　　即“N的 a次方乘以 N的 b次方，等于 N的 a+b次方 ”法则（但 N ≠ 0）。有关指数
　　法则的内容，在第 7章也会谈到。
　　0所起的作用
　　0的作用：占位
　　这节我们来讨论 0的作用。例如，用 10进制表示的 2503，它当中的 0起到了什么作用呢？ 2503的 0，表示十位 “没有 ”。虽说 “没有 ”，但这个 0却不能省略。因为如果省略了 0，写成 253，那就变成另一个数了。
　　在按位计数法中，数位具有很重要的意义。即使十位的数 “没有 ”，也不能不写数字。这时就轮到 0出场了，即 0的作用就是占位。换言之， 0占着一个位置以保证数位高于它的数字不会产生错位。
　　正因为有了表示 “没有 ”的 0，数值才能正确地表现出来。可以说在按位计数法中 0是不可或缺的。
　　0的作用：统一标准，简化规则
　　在按位计数法的讲解中，我们提到了 “0次方 ”，还将 1特意表示成 100。使用 0，能够将按位计数法的各个数位所对应的大小统一表示成
　　10n
　　否则，就必须特别处理 “1”这个数字。 0在这里起到了标准化的作用。
　　如果从高到低各个数位的数字依次为 an，an-1，an-2，…，a2，a1，a0，那么 10进制的按位计数法就能用以下表达式来表示：
　　
　　_
　　a2×102
　　_
　　a1×101
　　_
　　a0×100
　　按位计数法的各个数位也能统一写作
　　ak ×10k
　　请注意： ak右下角的 k和 10k的指数 k是一致的。在上述表达式中，设 n=3，a3=2，a2=5，a1=0，a0=3，最后的结果是 2503。
　　通过 0来明示 “没有 ”，能够使规则简单化。在许多情况下，规则是越简单越好的。当你在面对问题的时候，是否也可以借助 0来使问题简单化呢？请想一想吧。
　　日常生活中的 0
　　在我们的日常生活中，有时也会遇到像 0那样表示 “没有 ”的情况。
　　没有计划的计划
　　我们常常使用日程表来管理计划。在日程表中填入 “案头工作 ”、“出差 ”、“研讨会 ”
　　等计划。那么，和 “0”相当的计划是什么呢？
　　例如，我们可以将没有计划的状况设定成 “空计划 ”。通过在计算机的日程表中搜索 “空计划 ”，就能找到没有计划的日期。这样一来，我们就既能搜索已有的计划，又能搜索 “空计划 ”了。
　　还有，我们也可以将 “预计不安排计划（即，将该时间空出来） ”当作 0来考虑。在日
　　程表中先将 “预计不安排计划 ”的日程填写占位，然后再填写需要安排工作的日程。这样
　　就不至于引起混乱。这正好与按位计数法中的 0起到的占位作用相似。
　　没有药效的药
　　假设现在必须有规律地服用一种胶囊，每 4天停用 1次。也就是 3天服用， 1天停用， 3天服用， 1天停用，按照这种周期循环服药，有难度吧？灵机一动，妙法自然来。那就每天都吃药吧。只是，每 4粒中有 1粒是 “没有药效 ”的假胶囊。事先准备好标有日期的盒子，并在其中放入每天需要服用的药，不是更好吗？
　　事先将“假胶囊”放入标有日期的盒子里
　　＝胶囊＝假胶囊
　　这样一来，就无需判断 “今天是服药日还是停药日 ”了。正因为有了 “没有 ”药效的药，
　　才形成了 “每天服用 1粒胶囊 ”的简单规则。 a
　　由此可见，这时的假胶囊与按位计数法中 “0”所起的作用相同。