Matrix67 |
2007-08-06 13:53 | 
3x12=36
2x12=24
1x12=12
0x12=18
Aug
4
好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人，今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。
不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个二维数组。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果的那个4等于2*2+0*1：
下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵：
矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢？废话，交换过来后两个矩阵有可能根本不能相乘。为什么它又满足结合律呢？仔细想想你会发现这也是废话。假设你有三个矩阵A、B、C，那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（枚举所有的k和l）。
经典题目1 给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。
经典题目2 给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。
由于矩阵乘法具有结合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、A^6、A^3的值即可。根据这里的一些结果，我们可以在计算过程中不断取模，避免高精度运算。
经典题目3 POJ3233 (感谢rmq)
题目大意：给定矩阵A，求A + A^2 + A^3 + ... + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。
这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有：
A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。
经典题目4 VOJ1049
题目大意：顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。m<=10, k<2^31。
首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵的形式。例如，将1 2 3 4置换为3 1 2 4，相当于下面的矩阵乘法：
置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方，再乘以初始序列即可。做出来了别忙着高兴，得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟。
经典题目5 《算法艺术与信息学竞赛》207页（2.1代数方法和模型，[例题5]细菌，版次不同可能页码有偏差）
大家自己去看看吧，书上讲得很详细。解题方法和上一题类似，都是用矩阵来表示操作，然后二分求最终状态。
经典题目6 给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31
根据前面的一些思路，现在我们需要构造一个2 x 2的矩阵，使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵，这两个数就会多迭代一次。那么，我们把这个2 x 2的矩阵自乘n次，再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想，这个2 x 2的矩阵很容易构造出来：
经典题目7 VOJ1067
我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。
经典题目8 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。
经典题目9 用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果
我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。
经典题目10 POJ2778
题目大意是，检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n<=2 000 000 000。
下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n)，AC了。
最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：
Matrix67原创，转贴请注明出处。#include <cstdio>
#define SIZE (1<<m)
#define MAX_SIZE 32
using namespace std;
class CMatrix
{
public:
long element[MAX_SIZE][MAX_SIZE];
void setSize(int);
void setModulo(int);
CMatrix operator* (CMatrix);
CMatrix power(int);
private:
int size;
long modulo;
};
void CMatrix::setSize(int a)
{
for (int i=0; i<a; i++)
for (int j=0; j<a; j++)
element[i][j]=0;
size = a;
}
void CMatrix::setModulo(int a)
{
modulo = a;
}
CMatrix CMatrix::operator* (CMatrix param)
{
CMatrix product;
product.setSize(size);
product.setModulo(modulo);
for (int i=0; i<size; i++)
for (int j=0; j<size; j++)
for (int k=0; k<size; k++)
{
product.element[i][j]+=element[i][k]*param.element[k][j];
product.element[i][j]%=modulo;
}
return product;
}
CMatrix CMatrix::power(int exp)
{
CMatrix tmp = (*this) * (*this);
if (exp==1) return *this;
else if (exp & 1) return tmp.power(exp/2) * (*this);
else return tmp.power(exp/2);
}
int main()
{
const int validSet[]={0,3,6,12,15,24,27,30};
long n, m, p;
CMatrix unit;
scanf("%d%d%d", &n, &m, &p);
unit.setSize(SIZE);
for(int i=0; i<SIZE; i++)
for(int j=0; j<SIZE; j++)
if( ((~i)&j) == ((~i)&(SIZE-1)) )
{
bool isValid=false;
for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];
unit.element[i][j]=isValid;
}
unit.setModulo(p);
printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );
return 0;
}
Jul
24
===== 真正强的东西来了！ =====
二进制中的1有奇数个还是偶数个
我们可以用下面的代码来计算一个32位整数的二进制中1的个数的奇偶性，当输入数据的二进制表示里有偶数个数字1时程序输出0，有奇数个则输出1。例如，1314520的二进制101000000111011011000中有9个1，则x=1314520时程序输出1。var
i,x,c:longint;
begin
readln(x);
c:=0;
for i:=1 to 32 do
begin
c:=c + x and 1;
x:=x shr 1;
end;
writeln( c and 1 );
end.
但这样的效率并不高，位运算的神奇之处还没有体现出来。
同样是判断二进制中1的个数的奇偶性，下面这段代码就强了。你能看出这个代码的原理吗？var
x:longint;
begin
readln(x);
x:=x xor (x shr 1);
x:=x xor (x shr 2);
x:=x xor (x shr 4);
x:=x xor (x shr 8);
x:=x xor (x shr 16);
writeln(x and 1);
end.
为了说明上面这段代码的原理，我们还是拿1314520出来说事。1314520的二进制为101000000111011011000，第一次异或操作的结果如下：
00000000000101000000111011011000
XOR 0000000000010100000011101101100
---------------------------------------
00000000000111100000100110110100
得到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。对这个数进行第二次异或的结果如下：
00000000000111100000100110110100
XOR 000000000001111000001001101101
---------------------------------------
00000000000110011000101111011001
结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里有多少个1，这就是我们最终想要的答案。
计算二进制中的1的个数
同样假设x是一个32位整数。经过下面五次赋值后，x的值就是原数的二进制表示中数字1的个数。比如，初始时x为1314520（网友抓狂：能不能换一个数啊），那么最后x就变成了9，它表示1314520的二进制中有9个1。x := (x and $55555555) + ((x shr 1) and $55555555);
x := (x and $33333333) + ((x shr 2) and $33333333);
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF);
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);
为了便于解说，我们下面仅说明这个程序是如何对一个8位整数进行处理的。我们拿数字211（我们班某MM的生日）来开刀。211的二进制为11010011。
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数
+---+---+---+---+---+---+---+---+
| 1 0 | 0 1 | 0 0 | 1 0 | <---第一次运算后
+-------+-------+-------+-------+
| 0 0 1 1 | 0 0 1 0 | <---第二次运算后
+---------------+---------------+
| 0 0 0 0 0 1 0 1 | <---第三次运算后，得数为5
+-------------------------------+
整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100....，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。
二分查找32位整数的前导0个数
这里用的C语言，我直接Copy的Hacker's Delight上的代码。这段代码写成C要好看些，写成Pascal的话会出现很多begin和end，搞得代码很难看。程序思想是二分查找，应该很简单，我就不细说了。int nlz(unsigned x)
{
int n;
if (x == 0) return(32);
n = 1;
if ((x >> 16) == 0) {n = n +16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);
return n;
}
只用位运算来取绝对值
这是一个非常有趣的问题。大家先自己想想吧，Ctrl+A显示答案。
答案：假设x为32位整数，则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对值
x shr 31是二进制的最高位，它用来表示x的符号。如果它为0（x为正），则not (x shr 31) + 1等于$00000000，异或任何数结果都不变；如果最高位为1（x为负），则not (x shr 31) + 1等于$FFFFFFFF，x异或它相当于所有数位取反，异或完后再加一。
高低位交换
这个题实际上是我出的，做为学校内部NOIp模拟赛的第一题。题目是这样：
给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。
例如，数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。
当时几乎没有人想到用一句位操作来代替冗长的程序。使用位运算的话两句话就完了。var
n:dword;
begin
readln( n );
writeln( (n shr 16) or (n shl 16) );
end.
而事实上，Pascal有一个系统函数swap直接就可以用。
二进制逆序
下面的程序读入一个32位整数并输出它的二进制倒序后所表示的数。
输入： 1314520 （二进制为00000000000101000000111011011000）
输出： 460335104 （二进制为00011011011100000010100000000000）var
x:dword;
begin
readln(x);
x := (x and $55555555) shl 1 or (x and $AAAAAAAA) shr 1;
x := (x and $33333333) shl 2 or (x and $CCCCCCCC) shr 2;
x := (x and $0F0F0F0F) shl 4 or (x and $F0F0F0F0) shr 4;
x := (x and $00FF00FF) shl 8 or (x and $FF00FF00) shr 8;
x := (x and $0000FFFF) shl 16 or (x and $FFFF0000) shr 16;
writeln(x);
end.
它的原理和刚才求二进制中1的个数那个例题是大致相同的。程序首先交换每相邻两位上的数，以后把互相交换过的数看成一个整体，继续进行以2位为单位、以4位为单位的左右对换操作。我们再次用8位整数211来演示程序执行过程：
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数
+---+---+---+---+---+---+---+---+
| 1 1 | 1 0 | 0 0 | 1 1 | <---第一次运算后
+-------+-------+-------+-------+
| 1 0 1 1 | 1 1 0 0 | <---第二次运算后
+---------------+---------------+
| 1 1 0 0 1 0 1 1 | <---第三次运算后
+-------------------------------+
Copyright也很强writeln('Matrix' , 42 XOR 105 , '原创，转贴请注明出处');
Jul
23
去年年底写的关于位运算的日志是这个Blog里少数大受欢迎的文章之一，很多人都希望我能不断完善那篇文章。后来我看到了不少其它的资料，学习到了更多关于位运算的知识，有了重新整理位运算技巧的想法。从今天起我就开始写这一系列位运算讲解文章，与其说是原来那篇文章的follow-up，不如说是一个remake。当然首先我还是从最基础的东西说起。
什么是位运算？
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：
110
AND 1011
----------
0010 --> 2
由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。
Pascal和C中的位运算符号
下面的a和b都是整数类型，则：
C语言 | Pascal语言
-------+-------------
a & b | a and b
a | b | a or b
a ^ b | a xor b
~a | not a
a << b | a shl b
a >> b | a shr b
注意C中的逻辑运算和位运算符号是不同的。520|1314=1834，但520||1314=1，因为逻辑运算时520和1314都相当于True。同样的，!a和~a也是有区别的。
各种位运算的使用
=== 1. and运算 ===
and运算通常用于二进制取位操作，例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数.
=== 2. or运算 ===
or运算通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。
=== 3. xor运算 ===
xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。
xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a xor b) xor b = a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值，得到1314520，于是她就明白了我的企图。
下面我们看另外一个东西。定义两个符号#和@（我怎么找不到那个圈里有个叉的字符），这两个符号互为逆运算，也就是说(x # y) @ y = x。现在依次执行下面三条命令，结果是什么？x <- x # y
y <- x @ y
x <- x @ y
执行了第一句后x变成了x # y。那么第二句实质就是y <- x # y @ y，由于#和@互为逆运算，那么此时的y变成了原来的x。第三句中x实际上被赋值为(x # y) @ x，如果#运算具有交换律，那么赋值后x就变成最初的y了。这三句话的结果是，x和y的位置互换了。
加法和减法互为逆运算，并且加法满足交换律。把#换成+，把@换成-，我们可以写出一个不需要临时变量的swap过程(Pascal)。procedure swap(var a,b:longint);
begin
a:=a + b;
b:=a - b;
a:=a - b;
end;
好了，刚才不是说xor的逆运算是它本身吗？于是我们就有了一个看起来非常诡异的swap过程：procedure swap(var a,b:longint);
begin
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
=== 4. not运算 ===
not运算的定义是把内存中的0和1全部取反。使用not运算时要格外小心，你需要注意整数类型有没有符号。如果not的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用$0000到$FFFF依次表示的。下面的两个程序（仅语言不同）均返回65435。var
a:word;
begin
a:=100;
a:=not a;
writeln(a);
end.#include <stdio.h>
int main()
{
unsigned short a=100;
a = ~a;
printf( "%d\n", a );
return 0;
}
如果not的对象是有符号的整数，情况就不一样了，稍后我们会在“整数类型的储存”小节中提到。
=== 5. shl运算 ===
a shl b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，那么100 shl 2 = 400。可以看出，a shl b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。
通常认为a shl 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。
定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 - 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用shl来定义Max_N等常量。
=== 6. shr运算 ===
和shl相似，a shr b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用shr 1来代替div 2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的mod运算，效率可以提高60%。
位运算的简单应用
有时我们的程序需要一个规模不大的Hash表来记录状态。比如，做数独时我们需要27个Hash表来统计每一行、每一列和每一个小九宫格里已经有哪些数了。此时，我们可以用27个小于2^9的整数进行记录。例如，一个只填了2和5的小九宫格就用数字18表示（二进制为000010010），而某一行的状态为511则表示这一行已经填满。需要改变状态时我们不需要把这个数转成二进制修改后再转回去，而是直接进行位操作。在搜索时，把状态表示成整数可以更好地进行判重等操作。这道题是在搜索中使用位运算加速的经典例子。以后我们会看到更多的例子。
下面列举了一些常见的二进制位的变换操作。
功能 | 示例 | 位运算
----------------------+---------------------------+--------------------
去掉最后一位 | (101101->10110) | x shr 1
在最后加一个0 | (101101->1011010) | x shl 1
在最后加一个1 | (101101->1011011) | x shl 1+1
把最后一位变成1 | (101100->101101) | x or 1
把最后一位变成0 | (101101->101100) | x or 1-1
最后一位取反 | (101101->101100) | x xor 1
把右数第k位变成1 | (101001->101101,k=3) | x or (1 shl (k-1))
把右数第k位变成0 | (101101->101001,k=3) | x and not (1 shl (k-1))
右数第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1))
取末三位 | (1101101->101) | x and 7
取末k位 | (1101101->1101,k=5) | x and (1 shl k-1)
取右数第k位 | (1101101->1,k=4) | x shr (k-1) and 1
把末k位变成1 | (101001->101111,k=4) | x or (1 shl k-1)
末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1)
把右边连续的1变成0 | (100101111->100100000) | x and (x+1)
把右起第一个0变成1 | (100101111->100111111) | x or (x+1)
把右边连续的0变成1 | (11011000->11011111) | x or (x-1)
取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1
去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1))
最后这一个在树状数组中会用到。
Pascal和C中的16进制表示
Pascal中需要在16进制数前加$符号表示，C中需要在前面加0x来表示。这个以后我们会经常用到。
整数类型的储存
我们前面所说的位运算都没有涉及负数，都假设这些运算是在unsigned/word类型（只能表示正数的整型）上进行操作。但计算机如何处理有正负符号的整数类型呢？下面两个程序都是考察16位整数的储存方式（只是语言不同）。var
a,b:integer;
begin
a:=$0000;
b:=$0001;
write(a,' ',b,' ');
a:=$FFFE;
b:=$FFFF;
write(a,' ',b,' ');
a:=$7FFF;
b:=$8000;
writeln(a,' ',b);
end.#include <stdio.h>
int main()
{
short int a, b;
a = 0x0000;
b = 0x0001;
printf( "%d %d ", a, b );
a = 0xFFFE;
b = 0xFFFF;
printf( "%d %d ", a, b );
a = 0x7FFF;
b = 0x8000;
printf( "%d %d\n", a, b );
return 0;
}
两个程序的输出均为0 1 -2 -1 32767 -32768。其中前两个数是内存值最小的时候，中间两个数则是内存值最大的时候，最后输出的两个数是正数与负数的分界处。由此你可以清楚地看到计算机是如何储存一个整数的：计算机用$0000到$7FFF依次表示0到32767的数，剩下的$8000到$FFFF依次表示-32768到-1的数。32位有符号整数的储存方式也是类似的。稍加注意你会发现，二进制的第一位是用来表示正负号的，0表示正，1表示负。这里有一个问题：0本来既不是正数，也不是负数，但它占用了$0000的位置，因此有符号的整数类型范围中正数个数比负数少一个。对一个有符号的数进行not运算后，最高位的变化将导致正负颠倒，并且数的绝对值会差1。也就是说，not a实际上等于-a-1。这种整数储存方式叫做“补码”。
最后还有两句话
Matrix67原创
转贴请注明出处
Jul
7
C++语言是C语言的扩展。你把C源码的扩展名改成cpp通常都可以直接编译。从语法上看，C语言是C++语言的子集，个别地方除外。这篇日志专门收集C和C++语法上的不同，指出C和C++的极个别不兼容的地方，让大家在学习C语言后可以尽快写出正确的C++代码。这篇日志需要众牛过目并补充。
系统保留字
C++多出了很多功能，因此系统保留字比C更多。如果你的C源码中的变量名或函数名正好是C++的系统保留字，此时将不能通过C++的编译。
void*类型赋值
在C++中你不能把void*类型直接赋值给其它任何类型。下面这句代码在C中可以通过编译，但在C++中则不能通过编译。你需要使用类型转换后再赋值。int *x = malloc(sizeof(int) * 10);
指针的初始化和释放
在C语言中，对指针的初始化和释放通常这样写：int *x = malloc( sizeof(int) );
int *x_array = malloc( sizeof(int) * 10 );
free( x );
free( x_array );
但在C++中，这些操作通常使用new和delete运算符完成：int *x = new int;
int *x_array = new int[10];
delete x;
delete[] x_array;
结构的声明
C语言中声明结构变量需要在结构名前面加一个struct。在C++中那个struct可以省略。
也就是说，在C语言中你需要这样写：struct date
{
int year;
int month;
int day;
};
struct date now;
但在C++中，你可以写成这样：struct date
{
int year;
int month;
int day;
};
date now;
函数声明与调用
C++中严格禁止先调用后声明。你可以把函数声明写在前面或使用向前引用。下面的程序代码在C中是合法的，但是在C++中无法通过编译。#include <stdio.h>
int main()
{
printfDomain();
return 0;
}
int printfDomain()
{
printf("matrix67.com");
}
bool类型
C语言中使用bool类型需要包含stdbool.h文件。C++本身提供了bool类型。
主程序返回值
C语言中，你需要在主函数结束前加一句return 0。C++中主函数自动返回0，因此你可以不写return 0。放心，不写return 0在编译时连个警告都没有。
C++的新特性
这不属于本文的讨论范围。这是我们以后着重要讨论的东西。如果你不急着用C++的新特性，了解上面的东西后你就已经可以写出正确的C++程序了。
做人要厚道
转贴请注明出处
Jun
29
预处理指令
以一个井号开头的行都叫做预处理指令。除了#include指令外，我们还经常用到#define指令。#define指令可以告诉编译器，编译时把代码中出现的特定标识当作什么来处理。例如，我们可以这样写：#define NAME_OF_MY_POTENTIAL_GF "ZPR"
这样，编译器会在编译前把代码中出现NAME_OF_MY_POTENTIAL_GF的地方全部替换成"ZPR"。这种替换是无条件的，但是有一个例外：当指定的标识属于某个字符串（被引号引起来）时替换不会发生。例如，下面两行代码会输出NAME_OF_MY_POTENTIAL_GF defined as: ZPRprintf("NAME_OF_MY_POTENTIAL_GF defined as: ");
printf(NAME_OF_MY_POTENTIAL_GF);
其中，后面那个NAME_OF_MY_POTENTIAL_GF被自动替换为"ZPR"。如果哪一天ZPR不要我了，我就可以非常方便地让整个程序适用于另一个MM。
C语言中通常会用#define代替const。例如，下面的代码假设了输入数据n<=2000。#include <stdio.h>
#define MAX 2000
int main()
{
int f[MAX][MAX];
int i,j,n;
scanf("%d",&n);
for ( i=0; i<n; i++ )
{
for ( j=0; j<=i; j++ )
{
f[i][j] = j ? (f[i-1][j] + f[i-1][j-1]) % 10000 : 1;
printf( "%5d" , f[i][j] );
}
printf("\n");
}
return 0;
}
下面的这些指令也是合法的：#define begin {
#define end }
#define and &&
#define or ||
#define定义的指令允许带参数。例如，下面的定义也是合法的：#define sqr(x) x*x
观察下面的这个程序：#include <stdio.h>
#define begin {
#define end }
#define writeln(num) printf("%d\n",num)
#define sqr(x) x*x
int main()
begin
writeln(sqr(100));
writeln(sqr(10+2));
end
程序输出：10000
32
为什么第二个输出的数是32不是144？不要忘了sqr中的x不是一个变量，编译器仅仅是把x替换为10+2，因此sqr(10+2)的结果是10+2*10+2，当然是32咯。为了避免这种情况，这样写就没问题了：#define sqr(x) ( (x) * (x) )
下面这个定义很常用：#define MAX(a,b) ( ((a) > (b)) ? (a) : (b) )
如果你想写出一个很有个性的C代码，反复使用#define是一个不错的选择。例如，这段代码就极具个性，一个光棍的形象跃然于屏幕上。然而，真正把#define发挥得淋漓尽致的，还是要数这段代码。
static声明
在函数中的变量声明前加一个static可以使这个变量具有“记忆性”。观察下面的程序：#include <stdio.h>
void printNum()
{
int a=1;
static int b=1;
printf("%d %d\n", a++, b++);
}
int main()
{
int i;
for ( i=1; i<=5; i++ )
printNum();
return 0;
}
程序输出：1 1
1 2
1 3
1 4
1 5
short类型和int类型的范围
最初我们列出的C语言类型和Pascal类型的对比只能提供一个参考。事实上不同的编译器中short和int的范围可能不同。你可以查一下前面说过的limits.h来确定这些类型的实际范围。通常short是16位整数，long是32位整数。在Windows下Dev-C++中int类型是32位。
对64位整型的处理
和Free Pascal一样，对64位整数类型的处理总是比较麻烦。
首先，对long long赋值很可能会发生错误，你可以在常数后添加一个LL表明这是long long类型。其次，C语言中有些函数是要区分数据类型的，你需要根据数据类型选用恰当的函数。最后，long long类型的输出很可能也有问题，此时你可以用"%lld"来替换"%d"，表明输出的是一个long long类型。在Windows下总要装点怪，我在Windows编译时非要用"%I64d"才行。
下面的程序代码在Windows下Dev-C++中一切正常。#include <stdio.h>
#include <stdlib.h>
int main()
{
long long a;
a = -5841314520LL;
a = llabs(a);
a = a + 1;
printf("%I64d",a);
return 0;
}
查漏补缺
这个系列到这里就结束了。还有我没有说到的语法点吗？欢迎大家补充。
后记
C语言速成手册到这里就结束了。这很可能是网上现有的原创C语言教材中讲解最快，篇幅最短的，因为它只适合已经学过其它语言，了解程序设计基础知识的人。这一系列的文章略过了大量的概念讲解、示例代码和习题，你可以自己在网上阅读一些C语言程序作为补充。以后我可能还会写一些类似的文章介绍其它语言。下一步我计划写C与C++的区别，对象和类的介绍以及C++的新特性。再以后我可能会向Java或者Ruby的方向发展。
祝各位努力转C的OIer暑假愉快。
Matrix67原创
转贴请注明出处
Jun
17
条件运算符
条件运算符的格式如下：表达式1 ? 表达式2 : 表达式3
它表示：若表达式1为真（非0），则返回表达式2，否则返回表达式3。
下面的函数返回两个数中较小的一个：long min( long a, long b)
{
return (a<b)?a:b;
}
很多地方都可能用到条件运算符。再比如求平均数时你可能会这样写：average = (n>0) ? sum/n : 0;
自加、自减
a=a+1可以写成a++或++a，a=a-1可以写成a--或--a 。例如，你会经常看到这样的写法：for ( i=1; i<=10; i++ )
{
}
如果自加自减不是单独成句，而是放在其它语句中的话，那么a++和++a是有区别的。a++表示“用了后再加”，++a表示“加了后再用”。a--和--a的区别同理。下面的代码输出0 1 1 1。int a=0;
printf("%d ",a++);
printf("%d ",a);
int b=0;
printf("%d ",++b);
printf("%d",b);
其它运算符
下面所有的a和b均为整型，则：
C语言 | Pascal语言
-------+-------------
a & b | a and b
a | b | a or b
a ^ b | a xor b
a << b | a shl b
a >> b | a shr b
简写 | 含义
-------+-------------
a += b | a = a + b
a -= b | a = a - b
a *= b | a = a * b
a /= b | a = a / b
a %= b | a = a % b
a &= b | a = a & b
a |= b | a = a | b
a ^= b | a = a ^ b
a <<= b| a = a << b
a >>= b| a = a >> b
各种标准输入输出函数
下列函数都是stdio.h提供的。stdio.h还提供了一个EOF常量（其实就是-1），用来标识输入数据结束。
函数 | 用途
-----------------------------+----------------------------------------------------------
int scanf(str,arg1,...,argn) | 按指定格式读入数据，返回成功被赋值的变量个数。如果已无输入或出错则返回EOF
int printf(str,arg1,...,argn)| 按指定格式输出数据，返回成功输出的字符个数。
int getchar() | 返回标准输入的下一个字符，如果已无输入或出错则返回EOF。
int putchar(c) | 向屏幕输出一个字符c，同时返回这个字符，如果出错则返回EOF。
char *gets(str) | 把这一行输入数据存入字符串str并返回该字符串，如果已无输入或出错则返回NULL
int puts(str) | 输出字符串并自动输出一个换行符，如果出错则返回EOF。
内存输入输出操作
stdio.h中提供的sscanf和sprintf两个函数可以把一个字符串当作输入输出对象，其用法与scanf和printf差不多，只不过要多一个参数。你需要把目标字符数组作为函数的第一个参数。
使用sscanf和sprintf可以方便地进行数字和字符串互转，并实现各种字符串操作。看下面的程序代码：#include <stdio.h>
int main()
{
char st[80]="5:43:04";
int h,m,s;
sscanf(st, "%d:%d:%d", &h, &m, &s);
printf("Hour:%d Minute:%d Second:%d\n", h, m, s);
sprintf(st, "My birthday is %d-%d-%d", 1988, 5, 16);
printf("%s",st);
return 0;
}
输出为：Hour:5 Minute:43 Second:4
My birthday is 1988-5-16
文件输入输出操作
stdio.h还提供了FILE类型，用于定义文件指针。例如，下面的语句定义了两个待操作的文件：FILE *in, *out;
打开一个文件使用fopen函数，该函数的参数为两个字符串。前一个参数指定文件名，后一个参数指定打开模式("r"=读, "w"=写, "a"=在已有文件后继续写 )。函数返回一个文件指针作为此文件的标识供以后使用。
和文件操作相关的函数有：
函数 | 用途
-----------------------------------+----------------------------------------------------------
int fscanf(file,str,arg1,...,argn) | 从file指针对应的文件中读入数据，具体行为同scanf
int fprintf(file,str,arg1,...,argn)| 向file指针对应的文件中输出数据，具体行为同printf
int fgetc(file) | 从file指针对应的文件中读入数据，具体行为同getchar
int fputc(c,file) | 向file指针对应的文件中输出数据，具体行为同putchar
char *fgets(str,n,file) | 从file指针对应的文件中读入数据到str字符串，读到第n个字符为止
int fputs(str,file) | 向file指针对应的文件中输出数据，具体行为同puts
int fflush(file) | 立即写入文件，同Pascal中的flush
int feof(file) | 文件是否结束，同Pascal中的eof
int fclose(file) | 关闭文件，同Pascal中的close
下面的程序是文件操作版A+B问题，你可以看到文件操作具体的实现方法。#include <stdio.h>
int main()
{
FILE *in, *out;
long a, b;
in = fopen("test.in","r");
fscanf(in, "%d%d", &a, &b);
fclose(in);
out = fopen("test.out","w");
fprintf(out, "%d", a+b);
fclose(out);
return 0;
}
整型上下限
Pascal可以用maxlongint来表示longint类型的最大值。C语言中也有类似的定义可以直接使用。使用C语言中的相关定义需要在程序代码前加上#include <limits.h>。
定义 | 表示
-----------+-----------------------------
CHAR_MAX | char类型大小上限
CHAR_MIN | char类型大小下限
SHRT_MAX | short类型的大小上限
SHRT_MIN | short类型的大小下限
USHRT_MAX | unsigned short类型的大小上限
INT_MAX | int类型的大小上限
INT_MIN | int类型的大小下限
UINT_MAX | unsigned int类型的大小上限
LONG_MAX | long类型的大小上限
LONG_MIN | long类型的大小下限
ULONG_MAX | unsigned long类型的大小上限
LLONG_MAX | long long类型的大小上限
LLONG_MIN | long long类型的大小下限
ULLONG_MAX | unsigned long long类型的大小上限
常用数学函数
使用下面的函数需要在程序代码前加上#include <math.h>。
函数 | 用途
--------------------+-----------------
double sin(x) | 正弦
double cos(x) | 余弦
double tan(x) | 正切
double asin(x) | 反正弦
double acos(x) | 反余弦
double atan(x) | 反正切
double sqrt(x) | 开平方
double pow(x,y) | x的y次方
double exp(x) | e的x次方
double exp2(x) | 2的x次方
double log(x) | 以e为底的对数
double log2(x) | 以2为底的对数
double log10(x) | 以10为底的对数
double fabs(x) | x的绝对值
double fmod(x,y) | 小数版的mod
double floor(x) | 小于等于x的最大整数
double ceil(x) | 大于等于x的最小整数
double trunc(x) | 舍弃小数部分
double round(x) | 小数部分四舍五入
long lround(x) | 小数部分四舍五入，返回long
long long llround(x)| 小数部分四舍五入，返回long long
常用字符串函数
使用以下函数需要在程序代码前加上#include <string.h>。
参数s1和s2总是两个字符串，参数c总是一个字符。
函数 | 用途
-----------------------+-----------------------------
int strlen(s1) | 返回s1的长度
char *strcpy(s1,s2) | 把s2赋值给s1，返回s1
char *strcat(s1,s2) | 将s2连接到s1后面，返回s1
int strcmp(s1,s2) | 比较两字符串，s1小则返回负数，相等返回0，s1大返回正数
char *strchr(s1,c) | 寻找s1第一次出现c的位置，找到则返回指向该位置的指针，没找到则返回NULL
char *strstr(s1,s2) | 寻找s2第一次出现在s1的位置，找到则返回指向该位置的指针，没找到则返回NULL
char *strpbrk(s1,s2) | 寻找s2中的任意字符第一次出现在s1的位置，找到则返回指向该位置的指针，没找到则返回NULL
观察下面的程序：#include <stdio.h>
#include <string.h>
int main()
{
char st[80]="matrix67";
strcat(st,".com");
printf( "%s\n", st );
printf( "%d\n", strlen(st) );
printf( "%d\n", strcmp(st,"my blog") );
printf( "%c\n", *strchr(st,'i') );
printf( "%s\n", strpbrk(st,"3.1415927") );
printf( "%d\n", strstr(st,"x6")-st );
return 0;
}
输出为：matrix67.com
12
-1
i
7.com
5
内存操作函数
下面的一些函数主要用于字符串操作，因此属于string.h 。假设m1和m2都是void *类型。
函数 | 用途
-----------------------------+-----------------------------------
int memcmp (m1, m2, n) | 比较m1和m2的头n个字节，相同返回0，m1小返回负数，m2小返回正数
void *memmove (m1, m2, n) | 把m2的前n个字节复制到m1的位置，相当于Pascal中的move
void *memset (m1, c, n) | 把m1的前n个字节全部设为c，相当于Pascal中的fillchar
下面这段代码的结果是把st字符串变成了"Matrix67, I love UUUUUUUUUUUU..."。char st[80]="Matrix67, I love someone else...";
memset(st+17,'U',12);
当然memset更常用的是初始化数组。例如动态规划前初始化f数组：long f[1000][1000];
memset( f, 0, sizeof(f) );
stdlib.h提供的其它函数
函数 | 用途
-------------------------+-------------------------------------------------
int abs(n) | 取绝对值，适用于int
long labs(n) | 取绝对值，适用于long
long long llabs(n) | 取绝对值，适用于long long
double atof(str) | 把字符串str转化为数字，返回double类型
int atoi(str) | 把字符串str转化为数字，返回int类型
long atol(str) | 把字符串str转化为数字，返回long类型
long long atoll(str) | 把字符串str转化为数字，返回long long类型
void exit(n) | 退出程序，返回的错误代码为n（0=正常），相当于Pascal的halt
int rand() | 产生一个随机数，范围在stdlib.h中指定（通常最小为0，最大为int的上限）
void srand(n) | 设置随机数发生器的种子为n
void qsort(arr,n,size,fn)| 快排，四个参数分别为数组，长度，类型大小，比较函数。
比较函数的格式应该为int 函数名(const void *参数1, const void *参数2)
如果参数1小于参数2，则该函数返回负数，等于则返回0，大于则正数。因此，你可以自己给“大小”下定义。
下面的程序合法地调用了qsort函数。注意随机函数后的取余运算，这是生成某个范围内的随机数的常用手段。#include <stdlib.h>
int comp(const void *i, const void *j)
{
return *(long *)i - *(long *)j;
}
int main()
{
long n=1000, i, a[n];
for (i=0; i<n; i++) a[i]=rand()%10000;
qsort(a, n, sizeof(long), comp);
return 0;
}
利用assert帮助调试
assert可以在程序不满足某个条件时输出错误信息并立即终止运行，这对调试很有帮助。使用assert语句需要包含头文件assert.h。观察下面的程序代码：#include <stdio.h>
#include <assert.h>
int main()
{
int n;
scanf("%d",&n);
assert(n!=0);
printf("%f",1.0/n);
return 0;
}
当读入的数是0时，程序执行printf前就会提前终止，并且输出错误信息。这可以保证后面的语句正常执行，避免异常错误。这显然比用if语句排除异常错误更好一些。在每一个潜在的异常错误前加上assert，当程序出错时你可以很快确定是哪里的问题。
Matrix67原创
转贴请注明出处
Jun
13
指针的定义
定义一个指针的方法如下：类型名 *指针名;
例如，下面的语句定义了一个指针：int *pointer;
这样，pointer就是一个指针，它指向的是一个int类型的数据。
一个指针可以是一个合法的内存地址，也可以为0（通常写成NULL）。
你可以用printf语句输出一个指针，对应的标识为"%p"。下面的代码可以输出上面定义的指针指向的地址。printf("%p",p);
取地址与引用
假如a是一个变量，p是一个指针，那么&a返回该变量的地址，*p返回该指针所指的内容（称做“引用”）。
阅读下面的代码片段：int *p;
int a = 520;
p = &a;
printf( "%p -> %d\n", p, *p );
*p = 1314;
printf( "%p -> %d\n", p, *p );
printf( "a = %d", a );
程序输出如下。当执行了p=&a后，存取*p就相当于是存取变量a了。0022FF78 -> 520
0022FF78 -> 1314
a = 1314
动态内存分配
首先介绍sizeof函数（准确地说是一个运算符），它的参数为一个变量名或类型名，返回的是它所占内存空间的大小。下面的代码输出1 8 800 4 1 。long long a;
double b[100];
_Bool *c;
printf( "%d " , sizeof(char) );
printf( "%d " , sizeof(a) );
printf( "%d " , sizeof(b) );
printf( "%d " , sizeof(c) );
printf( "%d " , sizeof(*c) );
下面介绍四种动态内存分配函数，使用它们前需要在程序最前面包含头文件stdlib.h。四种函数的格式分别为：void *malloc ( size );
void *calloc ( n, size );
void free ( pointer );
void *realloc( pointer, size );
函数malloc将在内存里寻找一个大小为size的连续空间，把分配到的内存地址作为一个指向void类型的指针（默认的无类型指针）返回。如果空间分配失败，函数返回NULL。
函数calloc将在内存里寻找一个大小为n * size的连续空间，并且把这段内存的数据全部清0，返回数据和malloc一样。如果空间分配失败，函数返回NULL。
函数free用于释放内存空间，释放后的空间被回收，可以用于以后的malloc或calloc操作。
函数realloc在保证已有数据不变的情况下改变已有指针的空间大小，返回重新分得的空间的内存地址（有可能和原来不同）。如果空间重新分配失败，函数返回NULL。
Pascal中的new语句可以用前两个函数代替，free语句则相当于Pascal中的dispose。
注意，malloc和calloc函数所返回的指针还没确定类型，理论上需要用类型转换。下面的程序合法地为p指针分配空间：int *p;
p = (int *) malloc( sizeof(int) );
*p = 520;
事实上，由于赋值时C语言自动转换类型，因此那个类型转换是没有必要的（去掉(int *)没有影响）。
指针与结构
一个指针可以指向一个结构，一个结构也可以包含一个指针。结构里包含一个指向结构的指针就构成了链表：struct node{
int value;
struct node *next;
}
这样，定义struct node *a，则(*a).next就是另一个指向node结构的指针。在C语言中，(*x).y的句型很常用，因此有一个专门的记号x->y来代替(*x).y这样繁杂的写法。
你可以从下面的程序中看到链表的使用。#include <stdio.h>
#include <stdlib.h>
struct node
{
int value;
struct node *next;
};
int main()
{
struct node *head = NULL;
int i;
for(i=1;i<=10;i=i+1)
{
struct node *newNode;
newNode = malloc( sizeof(struct node) );
newNode->value = i;
newNode->next = head;
head = newNode;
}
struct node *p = head;
while (p)
{
printf( "%d\n", p->value );
p = p->next;
}
return 0;
}
指针与函数
前面说过，C语言中的函数参数和变量只能够供该函数使用。
下面四个程序代码的输出分别是什么？
代码一：#include <stdio.h>
void swap( int a, int b )
{
int c = a;
a = b;
b = c;
}
int main()
{
int a = 520, b = 1314;
swap( a , b );
printf( "%d %d", a, b );
return 0;
}
代码二：#include <stdio.h>
int a = 520, b = 1314;
void swap( int a, int b )
{
int c = a;
a = b;
b = c;
}
int main()
{
swap( a , b );
printf( "%d %d", a, b );
return 0;
}
代码三：#include <stdio.h>
int a = 520, b = 1314;
void swap()
{
int c = a;
a = b;
b = c;
}
int main()
{
swap();
printf( "%d %d", a, b );
return 0;
}
代码四：#include <stdio.h>
void swap( int *a, int *b )
{
int c = *a;
*a = *b;
*b = c;
}
int main()
{
int a = 520, b = 1314;
swap( &a, &b);
printf( "%d %d", a, b );
return 0;
}
答案：前两个程序输出520 1314，后两个程序输出1314 520。
前两个程序中，待交换的两个数（即使是全局变量）作为参数传给了swap函数，该函数里的操作对函数外无影响。
第三个程序中，swap函数对全局变量直接进行操作，其影响是全局的。
最后一个程序巧妙地应用了指针来实现两数交换。函数的参数是指针类型，这个函数不能改变指针本身，但可以改变指针所指的内容。这是写此类函数通常所用的方法。
为了强调函数void swap( int *a, int *b )中的指针本身不发生改变，很多地方喜欢写成void swap(const int *a, const int *b ) 。
指针与数组
数组由内存的连续空间构成，因此可以用指针来访问。事实上，数组名本身就是一个指针。观察下列代码：int a[100];
printf("%p\n", &a[0]);
printf("%p\n", a);
printf("%d\n", a == &a[0] );
printf("%p\n", &a[1]);
printf("%p\n", a+1);
看看输出结果（自己运行），你会发现，数组名其实就是一个指向数组起始位置的指针，其作用相当于&a[0]。而指针本身可以进行加减运算（表示内存地址的加减，具体加多少减多少取决于指针所指的类型），其本质是在数组中进行定位。因此，下面的两个代码是完全等价的：int i, a[100];
for ( i=0; i<100; i=i+1 ) *(a+i)=i;int i, a[100];
for ( i=0; i<100; i=i+1 ) a[i]=i;
下面的程序输出0 1 2 3 4 0。函数init不能改变变量的值，但由于数组的实质是指针，因此它可以改变数组所储存的内容。#include <stdio.h>
void init( int a[5], int b )
{
int i;
for ( i=0; i<5; i=i+1 ) a[i]=i;
b = 5;
}
int main()
{
int i, a[5], b=0;
init( a, b );
for ( i=0; i<5; i=i+1 ) printf("%d ",a[i]);
printf( "%d\n", b );
return 0;
}
你甚至可以用指针来创建数组。使用函数calloc可以方便地得到指定长度并已全部初始化为0的数组。再加上realloc函数后，你就可以实现真正意义上的动态数组（长度可变）。示例程序如下：#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, *a;
a = calloc(sizeof(int),5);
for ( i=0; i<5; i=i+1 ) *(a+i)=i;
for ( i=0; i<5; i=i+1 ) printf("%d",a[i]);
a = realloc(a,sizeof(int)*10);
for ( i=5; i<10; i=i+1 ) a[i]=10-i;
for ( i=0; i<10; i=i+1 ) printf("%d",a[i]);
return 0;
}
上面的程序将输出012340123454321。
标准输入
之所以现在才来说读入操作，是因为读入函数需要用到指针知识，否则解释不清楚。
输入操作用scanf函数，和输出一样需要有stdio.h支持。
和输出操作一样，scanf函数的第一个参数也是一个字符串，读入同样采用匹配标识符的方法进行。所不同的是，读入函数的参数是需要随函数变化的，因此变量作为scanf的参数时需要加上取地址符号，作为指针代入函数才行。除了读入%c类型之外，所有读入操作均自动跳过空格。
看下面四个例子：
代码一：int a, b;
scanf( "%d%d" , &a , &b );
输入：8 2
则a为8，b为2。
===========性感的分割线===========
代码二：int a;
char b;
scanf( "%d%c" , &a , &b );
输入：8 2
则a为8，b为一个空格。
===========性感的分割线===========
代码三：int h, m, s;
scanf( "%d:%d:%d" , &h , &m, &s );
输入：20:19:02
则h为20，m为19，s为2。
输入：20:19-02
则h为20，m为19，s没有获得新的值（匹配失败）。
===========性感的分割线===========
代码四：char st[80];
scanf( "My favourite website is%s" , st );
输入：My favourite website is matrix67.com, I love it!
则st为"matrix67.com," 。
注意最后这个例子，st是数组，本质上是一个指针，因此不需要加&符号。
Matrix67原创
转贴请注明出处
