26八

计算机字、字节、字长之某腾讯面试题

归类于C/C++ | 算法分析 2 条评论

常常我们说机器是32位或者64位的，这里面具体有些什么重要的信息呢？以及我们经常挂在嘴边的字节具体是什么概念？还有经常被忽略的”字“、”字长“。

字

首先，我们了解这么一个知识点，计算机在处理或者运算的时候，是把数据分成一个个固定长度数据串来处理的，这些一个个的细小数据串就是计算机的字。通常，一个字包含若干个字节（每个字节通常是8位，即8个二进制数）。而且，在存储器中，每个单元存储一个字，每个字又是可以通过寻址的，字的长度是用用位来表示的，即一个字能容纳多少位二进制数，即下面的字长。

字长

计算机中每个字的位数（二进制数的个数）就叫字长。根据计算机不同，字长分为固定字长、可变字长。固定字长，即字长度不论什么情况都是固定不变的；可变字长，则在一定范围内，其长度是可变的。

计算机的字长代表计算机的处理能力，是指它一次可处理的二进制数字的数目，即一次可处理计算的数据大小。计算机处理数据的速率，自然和它一次能加工的位数以及进行运算的快慢有关。如果一台计算机的字长是另一台计算机的两倍，即使两台计算机的速度相同，在相同的时间内，前者能做的工作是后者的两倍。我们常说的32位、64位机器就是说这些机器的字长度。字长大的机器CPU，假如相同处理速度的条件下，CPU的处理数据量与字长度成正比。因此，64位机器是要比32位更强！

字节

在上面说到的字，每个字中包含若干个字节（通常一个字节占8位，8个二进制数），或者说字节是指一小组相邻的二进制数码，通常是8位（二进制数）作为一个字节。字节是构成信息的一个小单位，并作为一个整体来参加操作，比”字“小，是构成字的单位。

一个重要的信息：在计算机中，通常用多少字节来表示存储器的存储容量。例如，在C++的数据类型表示中，通常 char为1个字节，int为4个字节，double为8个字节。

有了上面的概念，我们来算算数据的存储。

1字节(byte) = 8 位(bit)   得到：

1kib = 2的10次方 bit = 1024 bit

即: 1kib=1024bit  或  1k字节(KiB,kilibyte) = 1024(字节)

同理，

1MiB=1024KiB

1M字节（MiB,Mebibyte）=1024K字节（2的20次方字节）

1GiB=1024MiB

1G字节（GiB,Gibibyte）=1024M字节（2的30次方字节）

1TiB=1024GiB

1T字节（TiB,Tebibyte）=1024G字节（2的40次方字节）

1PiB=1024TiB

1P字节（PiB,Pebibyte）=1024T字节（2的50次方字节）

1EiB=1024PiB

1 E字节（EiB,Exbibyte）=1024P字节（2的60次方字节）

…

因为硬盘生产商是以GB（十进制，即10的3次方=1000，如1MB=1000KB）计算的，而电脑（操作系统）是以GiB(2进制，即2的 10次方，如

1MiB=1024KiB）计算的，国内用户一般不分MB与Mib以及Kb与kib，直接把1MB=1000 KB为1Mib=1024kib，所以好多160GB的硬盘实际容量按计算机

实际的1MiB=1024KiB算都不到160GiB，这也可以解释为什么新买的硬盘“缺斤短两”并没有它所标示的那么大。

最后，我们来看一道传说腾讯的面试题目：

问题
在一个文件中有 10G 个整数，乱序排列，要求找出中位数，内存限制为 2G,多少次计算能找出中位数？
解答

假设整数为long，即长整形的，占8个字节，也就是8*8bit=64bit，因此这个long整数的取值范围是多少呢？就是无符号0~2^64-1次方或者有符号-2^63 ~ 2^63-1次方，好大好恐怖的数。

这个意思也就是说，假如无符号64bit的数，从0~2^64次方一个个存储在一起的话，会有多大呢？答案是：2^64 * 8kib>>1E数据量>>N个TB数据>>2G内存，也就是想说，2G的内存不可能放下从0~2^64次方的所有64bit数，当然，10G的文件也不可能存储完。

那么现在我把我们的问题重新描述下：数字区间是0~2^64次方中间的数，大概是10G数据是整个区间所有数据大小的几万分之一，然后需要你只用2G的内存，也就是说那个几万分之一再除以一个5，来计算出这10G数据中的中位数。

我们是不是可以继续这样描述问题？变成一个猜字游戏？

数字范围是1-1000的数，总共100个，你每次最多可以从1-1000中挑选20个数字来计算出这100个数字的中位数（而且每次可以读取20个数字），怎么来做从而得到这100个数字的中位数呢？我们把1-1000范围的均匀分成20个区间，0-50，50-100，100-150，150-200，…，然后每次读取20个数，遍历一次100个数后。比如一边执行计算逻辑是这样的，20个区间，哪个区间范围出现了数字的话，就记录下来，没出现的自然不记录，比如我们遍历一次的结果是这样几种情况。

  1. 最糟糕的，每个区间都有出现，那么我们可以确定中位数出现在450-500这个区间，那么我们第二次就是把450-500继续划分成20个区间，然后继续遍历，这一次，请注意，每个区间数字范围是多少呢？只有50/20，不到3个数字啦。这样，我们就可以继续这样操作，就能精确到1！！！！
  2. 其他情况都要比最糟糕情况好处理啦，哈哈哈

所以，问题重新回归到10G数据用2G内存处理：

64bit整数取值区间数据总数据量大小有2^64 * 8k(64bit)大小数据，也就是

  1. 2G内存能存储，也就是2G字节=2*2^30K = 2^31K
  2. 对64bit整数区间做2^31均匀划分，也就是2^64 除以 2^31等于2^33次方，再遍历10G数据
  3. 不论怎样处理情况，一次遍历总能确定是哪一个均匀区间，而且这个区间的长度为2^33次方大小，并且咱们只有2^31次方的处理能力。
  4. 因此，我们还得继续均匀划分，并处理下，这是第二次处理。第二次处理，我们剩余的区间长度就只有2^33 除以2^31等于2^2=4啦，也就能毫不费力的在第三次处理得出结果啦。
以上个人自以为是的分析，欢迎交流指正!
// -_-   larro

19七

计算机机器数原码、反码、补码、有符号数以及无符号数

归类于C/C++ 参与评论

学C语言时候，计算机二进制数以及有符号、无符号数的一些问题不是很清楚，刚才看到一个关于有/无符号数的问题就查了一下，现在清楚很多了。

这篇文章写得实在太好了，清楚明白容易理解，就不自己表达，贴过来好了。

负数在计算机中如何表示呢？

这一点，你可能听过两种不同的回答。

一种是教科书，它会告诉你：计算机用“补码”表示负数。可是有关“补码”的概念一说就得一节课，这一些我们需要在第6章中用一章的篇幅讲2进制的一切。再者，用“补码”表示负数，其实一种公式，公式的作用在于告诉你，想得问题的答案，应该如何计算。却并没有告诉你为什么用这个公式就可以和答案？

另一种是一些程序员告诉你的：用二进制数的最高位表示符号，最高位是0，表示正数，最高位是1，表示负数。这种说法本身没错，可是如果没有下文，那么它就是错的。至少它不能解释，为什么字符类型的-1用二进制表示是“1111 1111”(16进制为FF)；而不是我们更能理解的“1000 0001”。（为什么说后者更好理解呢？因为既然说最高位是1时表示负数，那1000 0001不是正好是-1吗？）。

让我们从头说起。

1、你自已决定是否需要有正负。

就像我们必须决定某个量使用整数还是实数，使用多大的范围数一样，我们必须自已决定某个量是否需要正负。如果这个量不会有负值，那么我们可以定它为带正负的类型。

在计算机中，可以区分正负的类型，称为有符类型，无正负的类型（只有正值），称为无符类型。

数值类型分为整型或实型，其中整型又分为无符类型或有符类型，而实型则只有符类型。

字符类型也分为有符和无符类型。

比如有两个量，年龄和库存，我们可以定前者为无符的字符类型，后者定为有符的整数类型。

2、使用二制数中的最高位表示正负。

首先得知道最高位是哪一位？1个字节的类型，如字符类型，最高位是第7位，2个字节的数，最高位是第15位，4个字节的数，最高位是第31位。不同长度的数值类型，其最高位也就不同，但总是最左边的那位（如下示意）。字符类型固定是1个字节，所以最高位总是第7位。

(红色为最高位)

单字节数： 1111 1111

双字节数： 1111 1111 1111 1111

四字节数： 1111 1111 1111 1111 1111 1111 1111 1111

当我们指定一个数量是无符号类型时，那么其最高位的1或0，和其它位一样，用来表示该数的大小。

当我们指定一个数量是无符号类型时，此时，最高数称为“符号位”。为1时，表示该数为负值，为0时表示为正值。

3、无符号数和有符号数的范围区别。

无符号数中，所有的位都用于直接表示该值的大小。有符号数中最高位用于表示正负，所以，当为正值时，该数的最大值就会变小。我们举一个字节的数值对比：

无符号数： 1111 1111   值：255 1* 27 + 1* 26 + 1* 25 + 1* 24 + 1* 23 + 1* 22 + 1* 21 + 1* 20

有符号数： 0111 1111   值：127         1* 26 + 1* 25 + 1* 24 + 1* 23 + 1* 22 + 1* 21 + 1* 20

同样是一个字节，无符号数的最大值是255，而有符号数的最大值是127。原因是有符号数中的最高位被挪去表示符号了。并且，我们知道，最高位的权值也是最高的（对于1字节数来说是2的7次方=128），所以仅仅少于一位，最大值一下子减半。

不过，有符号数的长处是它可以表示负数。因此，虽然它的在最大值缩水了，却在负值的方向出现了伸展。我们仍一个字节的数值对比：

无符号数：                       0 —————– 255

有符号数：        -128 ——— 0 ———- 127

同样是一个字节，无符号的最小值是 0 ，而有符号数的最小值是-128。所以二者能表达的不同的数值的个数都一样是256个。只不过前者表达的是0到255这256个数，后者表达的是-128到+127这256个数。

一个有符号的数据类型的最小值是如何计算出来的呢？

有符号的数据类型的最大值的计算方法完全和无符号一样，只不过它少了一个最高位（见第3点）。但在负值范围内，数值的计算方法不能直接使用1* 26 + 1* 25 的公式进行转换。在计算机中，负数除为最高位为1以外，还采用补码形式进行表达。所以在计算其值前，需要对补码进行还原。这些内容我们将在第六章中的二进制知识中统一学习。

这里，先直观地看一眼补码的形式：

以我们原有的数学经验，在10进制中：1 表示正1，而加上负号：-1 表示和1相对的负值。

那么，我们会很容易认为在2进制中（1个字节）： 0000 0001 表示正1，则高位为1后：1000 0001应该表示-1。

然而，事实上计算机中的规定有些相反，请看下表：

二进制值（1字节） 十进制值
1000 0000 -128
1000 0001 -127
1000 0010 -126
1000 0011 -125
… …
1111 1110 -2
1111 1111 -1

首先我们看到，从-1到-128，其二进制的最高位都是1（表中标为红色），正如我们前面的学。

然后我们有些奇怪地发现，1000 0000 并没有拿来表示 -0；而1000 0001也不是拿来直观地表示-1。事实上，-1 用1111 1111来表示。

怎么理解这个问题呢？先得问一句是-1大还是-128大？

当然是 -1 大。-1是最大的负整数。以此对应，计算机中无论是字符类型，或者是整数类型，也无论这个整数是几个字节。它都用全1来表示 -1。比如一个字节的数值中：1111 1111表示-1，那么，1111 1111 – 1 是什么呢？和现实中的计算结果完全一致。1111 1111 – 1 = 1111 1110，而1111 1110就是-2。这样一直减下去，当减到只剩最高位用于表示符号的1以外，其它低位全为0时，就是最小的负值了，在一字节中，最小的负值是1000 0000，也就是-128。

我们以-1为例，来看看不同字节数的整数中，如何表达-1这个数：

字节数 二进制值 十进制值
单字节数 1111 1111 -1
双字节数 1111 1111 1111 1111 -1
四字节数 1111 1111 1111 1111 1111 1111 1111 1111 -1

可能有同学这时会混了：为什么 1111 1111 有时表示255，有时又表示-1？所以我再强调一下本节前面所说的第2点：你自已决定一个数是有符号还是无符号的。写程序时，指定一个量是有符号的，那么当这个量的二进制各位上都是1时，它表示的数就是-1；相反，如果事选声明这个量是无符号的，此时它表示的就是该量允许的最大值，对于一个字节的数来说，最大值就是255。

原码、反码、补码

我们已经知道计算机中，所有数据最终都是使用二进制数表达。

我们也已经学会如何将一个10进制数如何转换为二进制数。

不过，我们仍然没有学习一个负数如何用二进制表达。

比如，假设有一 int 类型的数，值为5，那么，我们知道它在计算机中表示为：

00000000 00000000 00000000 00000101

5转换成二制是101，不过int类型的数占用4字节（32位），所以前面填了一堆0。

现在想知道，-5在计算机中如何表示？

在计算机中，负数以其正值的补码形式表达。

什么叫补码呢？这得从原码，反码说起。

原码：一个整数，按照绝对值大小转换成的二进制数，称为原码。

比如 00000000 00000000 00000000 00000101 是 5的 原码。

反码：将二进制数按位取反，所得的新二进制数称为原二进制数的反码。

取反操作指：原为1，得0；原为0，得1。（1变0; 0变1）

比如：将00000000 00000000 00000000 00000101每一位取反，得11111111 11111111 11111111 11111010。

称：11111111 11111111 11111111 11111010 是 00000000 00000000 00000000 00000101 的反码。

反码是相互的，所以也可称：

11111111 11111111 11111111 11111010 和 00000000 00000000 00000000 00000101 互为反码。

补码：反码加1称为补码。

也就是说，要得到一个数的补码，先得到反码，然后将反码加上1，所得数称为补码。

比如：00000000 00000000 00000000 00000101 的反码是：11111111 11111111 11111111 11111010。

那么，补码为：

11111111 11111111 11111111 11111010 + 1 = 11111111 11111111 11111111 11111011

所以，-5 在计算机中表达为：11111111 11111111 11111111 11111011。转换为十六进制：0xFFFFFFFB。

再举一例，我们来看整数-1在计算机中如何表示。

假设这也是一个int类型，那么：

1、先取1的原码：00000000 00000000 00000000 00000001

2、得反码：     11111111 11111111 11111111 11111110

3、得补码：     11111111 11111111 11111111 11111111

可见，－1在计算机里用二进制表达就是全1。16进制为：0xFFFFFF。

顶部