2进制算法详细讲解 编程基础，漫淡数制码制

数制、码制、位、字节、字长及内存对齐等概念具有一定的相关性：

人类最常用的便是10进制了，然后还有计时的60进制，月份的12进制。

计算机使用的是2进制，以及辅助的16进制与8进制，16和8进制与2的乘幂相关。3个二进制位对位一个8进制位，4个二进制位对应一个16进制位。

对于n进制，有如下规则：

符号数量：n-1个；

2进制：0,1;8进制：0，1，2，3，4，5，6，7；10进制：0，1，2，3，4，5，6，7，8，9；16进制：0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F；

如何表示n呢？需要两位，也就是10来表示n进制的n，n就是n进制的模数，当某一个数m与n进行求模运算时，其结果都会小于n，如m%n的结果小于n。

我们知道，计算机采用二进制，是因为其逻辑元件最容易实现，具有最佳的稳定性。其理论原理来自于布尔代数和香农提出的布尔代数在开关电路的实现。0和1可以用继电器、晶体管的开关或电容电信号的有无来实现，且通过门电路（与门、或门、非门等）实现布尔代数。

如果单就数字组合来说，哪一种进制的效率最高？先问一个问题：

假设a*b=N

当a取什么值时，a^b的值最大？（a,b可以是小数）。

设f(x)=x^(K/x)，x>0，K是大于0的常数。对f求导，即可得x=e时f取极大值，也是最大值。

e＝2.71828……

与e最接近的整数不是2而是3。

二进制存储的计算机，一个32位的的机器使用了32个1和0，也就是64个元素，可以表达2^32=4.29*10^9个精度的数字。同样是64个元素，假设表达成3^21.3=1.45*10^10，即使是3^21也有1.05*10^10个精度，也就是说，如果用三进制，可以有更多的组合，而四进制呢？组合数又变小了（其实e进制有最多的组合数）。

但3进制的硬件却比较难以实现，而二进制的组合效率仅次于三进制，而硬件实现最简单和稳定，所以二进制是天然的计算机最佳数制了，正如黄金是天然的货币一样。

前苏联曾搞过的三进制计算机：在一般情况下，命题不一定为真或假，还可能为未知。在三进制逻辑学中，符号1代表真；符号-1代表假；符号0代表未知。三进制逻辑电路的电压存在着三种状态：正电压（1）、零电压（0）和负电压（-1）。

一个以上的符号通过组合规则便可以描述和表示复杂的信息了，如摩斯密码或电码，英文的字母、中文的汉字。

计算中的底层不管是数据还是指令，都是二进制的0、1，硬件实现为晶体管的开关或电容中电信号的有无。

数的编码：包括正整数的原码、负整数的补码、浮点数的IEEE754码制（包括阶码的移码）；

字符的编码：如ASCII码、utf-8的unicode码，GBK码等，用不同长度的二进制位来表示。

位图的编码：位图像素的数字化；

声明的编码：声波振幅、频率采样的数字化；

前面说了，用晶体管或电容可以实现一个二进制位，或0或1。

一个二进制位包含的信息量称为一 比特 。

从门电路到集成电路，从简单到复杂的关键在于组合。

后面会提到，计算机中以8个位组合成一个字节，做为基本的寻址单位，但也可以进行位层面的计算，这就是位运算。

计算机中以8个位组合成一个字节，做为基本的寻址和运算单位。不同的数据类型使用长度不同的内存单元（字节数不同）。

在ASCII码中，用一个字节来表示一个字符。不同的字符集的字符（如宽字符、多字符）需要不同数量的字节数。

对于现在的电脑来时，其内部实现都是串行操作的（可以利用电脑速度快和人类感官速度慢的特点，通过快速切换的串行来模拟人类表面感觉的并行），单个访问字节效果太低了，电脑可以一次访问多个字节，如32机就是一次可以访问32个位，4个字节，64机一次可以访问8个字节。

一次性处理事务的一个固定长度的位（bit）的位数叫字长。计算机中大多数寄存器的大小是一个字长。计算机处理的典型数值（如int）也可能是以字长为单位。CPU和内存之间的数据传送单位也通常是一个字长。还有而内存中用于指明一个存储位置的地址也经常是以字长为单位的。现代计算机的字长通常为32、64位。内部数据的表示或处理通常是字长的位数或分数。

考虑到计算机按字长处理数据的特点，对于复合数据类型，如结构体、类、共用体，都会考虑通过内存对齐来提供数据操作（读写）效率。每个特定平台上的编译器都有自己的默认“对齐系数”(也叫对齐模数)。比如32位windows平台下，VC默认是按照8bytes对齐的(VC->Project->settings->c/c ->Code Generation中的truct member alignment 值默认是8)，程序员可以通过预编译命令#pragma pack(n)，n=1,2,4,8,16来改变这一系数，其中的n就是你要指定的“对齐系数”。

内存对齐规则：

1、数据成员对齐规则：结构(struct)(或联合(union)或类(class))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员的对齐按照#pragma pack(n)指定的数值和这个数据成员自身长度中，比较小的那个进行。

成员对齐系数 = min(数据成员类型, n)

2、结构(或联合)的整体对齐规则：在数据成员完成各自对齐之后，结构(或联合)本身也要进行对齐(数据成员后的内存单元是否需要填充)，对齐将按照#pragma pack指定的数值和结构(或联合)最大数据成员长度中，比较小的那个进行。

整体对齐系数 = min((max(最大数据成员长度), 8)

3、结合1、2推断：当#pragma pack的n值等于或超过所有数据成员长度的时候，这个n值的大小将不产生任何效果。

如果没有通过pragma pack(m) 指定数值，VC规定各成员变量存放的起始地址相对于结构的起始地址的偏移量必须为该变量的类型所占用的字节数的倍数。

下面列出常用类型的对齐方式(vc6.0,32位系统)。

类型 对齐方式（变量存放的起始地址相对于结构的起始地址的偏移量）

char 偏移量必须为sizeof(char)即1的倍数

Short 偏移量必须为sizeof(short)即2的倍数

int 偏移量必须为sizeof(int)即4的倍数

float 偏移量必须为sizeof(float)即4的倍数

double 偏移量必须为sizeof(double)即8的倍数

各成员变量在存放的时候根据在结构中出现的顺序依次申请空间，同时按照上面的对齐方式调整位置，空缺的字节VC会自动填充。同时VC为了确保结构的大小为结构的字节边界数（即该结构中占用最大空间的类型所占用的字节数）的倍数，所以在为最后一个成员变量申请空间后，还会根据需要自动填充空缺的字节,也就是说：结构体的总大小为结构体最宽基本类型成员大小的整数倍，如有需要编译器会在最末一个成员之后加上填充字节（trailing padding）。

例1：

struct Node1{double m1;char m2；int m3;};

为上面的结构Node1分配空间的时候，VC根据成员变量出现的顺序和对齐方式，

1 先为第一个成员m1分配空间，其起始地址跟结构的起始地址相同（刚好偏移量0刚好为sizeof(double)的倍数），该成员变量占用sizeof(double)=8个字节；

2 接下来为第二个成员m2分配空间，这时下一个可以分配的地址对于结构的起始地址的偏移量为8，是sizeof(char)的倍数，所以把m2存放在偏移量为8的地方满足对齐方式，该成员变量占用 sizeof(char)=1个字节；

3 接下来为第三个成员m3分配空间，这时下一个可以分配的地址对于结构的起始地址的偏移量为9，不是sizeof (int)=4的倍数，为了满足对齐方式对偏移量的约束问题，VC自动填充3个字节（这三个字节没有放什么东西）；

4 最后要考虑整体对齐规则，这时下一个可以分配的地址对于结构的起始地址的偏移量为12，刚好是sizeof(int), 由于8 4 4 = 16恰好是结构体中最大空间类型double(8)的倍数，所以sizeof(Node1) =16.

例2：

struct Node2{char a;int b;char c;};

再来分析一下Node2，

1 成员a占一个字节，所以a放在了第1位的位置；

2 第二个变量b占4个字节，为保证起始位置是4(sizeof(b))的倍数，所以需要在a后面填充3个字节，也就是b放在了从第5位到第8位的位置；

3 然后就是c放在了9的位置，此时4 4 1=9。

4 接下来考虑字节边界数，9并不是最大空间类型int(4)的倍数，应该取大于9且是4的的最小整数12，所以sizeof(Node2) = 12.

例3：

typedef struct{char a;char b;int c;}Node3;

同样的方法我们要计算出sizeof(Node3) = 8;

例4：

struct node4 {char c1;Node3 n3;char c2};

n3的最宽简单成员的类型为int，n3在考虑最宽简单类型成员时是将Node3“打散”看的，所以n3的最宽简单类型为int，这样，通过n3定义的变量，其存储空间首地址需要被4整除，整个sizeof(n3)的值也应该被4整除。

1 c1的偏移量为0；

2 n3的偏移量呢？这时n3是一个整体，它作为结构体变量也满足前面三个准则，所以其大小为8，偏移量为4，c1与n3之间便需要3个填充字节；

3 而c2与n3之间就不需要了，所以c2的偏移量为12；

4 考虑整体偏移，算上c2的大小为13，13是不能被4整除的，这样末尾还得补上3个填充字节。最后得到sizeof(S3)的值为16。

通过上面的叙述，我们可以得到一个公式：

结构体的大小等于最后一个成员的偏移量加上其大小再加上末尾的填充字节数目，即：

sizeof( struct ) = offsetof( last item ) sizeof( last item ) sizeof( trailing padding )

再来实一个整体实例：

#include <iostream>using namespace std;//预编译命令#pragma pack(n)，n=1,2,4,8,16来改变这一系数，其中的n就是你要指定的“对齐系数”。#pragma pack(8)typedef struct people{ double weight; char sex; // 8 1 short age; // 9 1 2 int money; // 12 4 char flag; // 16 1 7 }strtSize;//}__attribute__((packed)) strtSize;/让GCC编译器取消结构在编译过程中的优化对齐void main(){ cout<<sizeof(double)<<endl; // 8 cout<<sizeof(strtSize)<<endl; // 24}

-End-