Matrix67 |
2007-07-25 0:30 | 
Bless All NOIers...
现在大家差不多该上路了吧，祝大家考前一路顺利，考场上超常发挥，评测时RP++，最后满载而归！
现在闲的厉害，不知道大家报名前或考完后有没有自发组织什么活动的，有的话我想过来玩玩，瞻仰一下各位大牛
刚才没事看了一下NOI笔试题，有些题目笑死我了……
Jul
25
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
16
5. TMMLPTEALPAITAFNFAL语言 http://p-nand-q.com/humor/programming_languages/tmmlpteal.html
你没看错，上面这一排毫无意义的字母是一个语言的名称。它是The Multi-Million Language Project To End All Language Projects And Isn't That A Fine Name For A Language的缩写。TMMLPTEALPAITAFNFAL语言没有固定的语法规则，每一天都是不同的语法。例如，2000年10月13日你可以使用DIV但不能使用MOD；到了10月14日时你可以使用MOD了但DIV又不能用了。因此，你今天写的程序运行起来完全正常，但是到了明天就无法编译了。下面是一个TMMLPTEALPAITAFNFAL的Hello World程序，当然现在已经无法编译了。 DECLARE CELL 100 AS READPOS
DECLARE 10 AS NEWLINE
WRITE CHAR NEWLINE
COPY "Hello, World" TO CELL 0
COPY 0 TO READPOS
WHILE READPOS INDIRECT DO GOSUB 300
WRITE CHAR NEWLINE
RETURN
LINE 300: WRITE CHAR READPOS INDIRECT
ADD 1 TO READPOS
RETURN
4. l33t语言 http://web.archive.org/web/20050329085620/http://electrod.ifreepages.com/l33t.htm
Leetspeak是国外网络上曾经流行的一种字母书写方式，就像这个样子。很多电影和美剧的名字也是Leetspeak，比如se7en、numb3rs、s1m0ne等等。l33t程序的代码故意仿照这种风格。它的代码中只有0到9这九个数字是有意义的，其它的字符都没用。因此，你可以先写好一篇文章，然后依次把里面出现的字母替换成你的l33t代码，让一段Leetspeak文字中隐藏一个小程序。下面就是一个Hello World示例程序： // "Hello World" by Stephen McGreal.
// Note that the views expressed in this source code do not necessarily coincide with those of the author :o)
Gr34t l33tN3$$?
M3h...
iT 41n't s0 7rIckY.
l33t sP33k is U8er keWl 4nD eA5y wehn u 7hink 1t tHr0uGh.
1f u w4nn4be UB3R-l33t u d3f1n1t3lY w4nt in 0n a b4d4sS h4xX0r1ng s1tE!!!;p
w4r3Z c0ll3cT10n2 r 7eh l3Et3r!
Qu4k3 cL4nS r 7eh bE5t tH1ng 1n teh 3nTIr3 w0rlD!!!
g4m3s wh3r3 u g3t to 5h00t ppl r 70tAl1_y w1cK1d!!
I'M teh fr4GM4stEr aN I'lL t0t41_1Ly wIpE teh phr34k1ng fL00r ***j3d1 5tYlE*** wItH y0uR h1dE!!!!L0L0L0L!
t3lEphR4gG1nG l4m3rs wit mY m8tes r34lLy k1kK$ A$$
l33t hAxX0r$ CrE4t3 u8er- k3wL 5tUff lIkE n34t pR0gR4mm1nG lAnguidGe$...
s0m3tIm3$ teh l4nGu4gES l00k jUst l1k3 rE41_ 0neS 7o mAkE ppl Th1nk th3y'r3 ju$t n0rMal lEE7 5pEEk but th3y're 5ecRetLy c0dE!!!!
n080DY unDer5tAnD$ l33t SpEaK 4p4rT fr0m j3d1!!!!!
50mE kId 0n A me$$4gEb04rD m1ghT 8E a r0xX0r1nG hAxX0r wH0 w4nT2 t0 bR34k 5tuFf, 0r mAyb3 ju5t sh0w 7eh wAy5 l33t ppl cAn 8E m0re lIkE y0d4!!! hE i5 teh u8ER!!!!
1t m1ght 8E 5omE v1rus 0r a Pl4ySt4tI0n ch34t c0dE.
1t 3v3n MiTe jUs7 s4y "H3LL0 W0RLD!!!" u ju5t cAn'T gu3s5.
tH3r3's n3v3r anY p0iNt l00KiNg sC3pT1c4l c0s th4t, be1_1Ev3 iT 0r n0t, 1s whAt th1s 1s!!!!!
5uxX0r5!!!L0L0L0L0L!!!!!!!
3. Java2K语言 http://p-nand-q.com/humor/programming_languages/java2k.html
Java2K是一种非确定性的语言，程序正常运行是有一定概率的。很多时候程序并不能按照你的意愿去运行，即使是系统函数也不会总是去做它该做的事。所有的函数都有两种不同的解释，程序运行时会随机选择一个作为实际调用的函数。
几乎所有的系统函数返回正确结果都只有90%的可能性，因此程序运行的最终结果或多或少都和预期结果不同。写出正确率尽量高的Java2K程序是一个非常有趣的挑战。
2. Chef语言 http://www.dangermouse.net/esoteric/chef.html
一个完整的Chef程序代码分为三个部分：程序名、变量声明和一系列栈操作。所有的操作都写成食谱的样子。例如，Put x into the mixing bowl就表示把变量x压入栈中，而Stir for 2 minutes则表示把栈顶元素向下移两格。下面的程序打印出前100个Fibonacci数。Fibonacci Numbers with Caramel Sauce.
Ingredients.
100 g flour
250 g butter
1 egg
Method.
Sift the flour. Put flour into mixing bowl. Serve with caramel sauce. Stir for 2 minutes. Remove egg. Rub the flour until sifted. Stir for 2 minutes. Fold the butter into the mixing bowl. Pour contents of the mixing bowl into the baking dish.
Serves 1.
Caramel Sauce.
Ingredients.
1 cup white sugar
1 cup brown sugar
1 vanilla bean
Method.
Fold white sugar into mixing bowl. Put white sugar into mixing bowl. Fold brown sugar into mixing bowl. Clean mixing bowl. Put white sugar into mixing bowl. Remove vanilla bean. Fold white sugar into mixing bowl. Melt white sugar. Put vanilla bean into mixing bowl. Refrigerate. Heat white sugar until melted. Put white sugar into mixing bowl. Remove vanilla bean. Fold white sugar into mixing bowl. Caramelise white sugar. Put vanilla bean into mixing bowl. Refrigerate. Cook white sugar until caramelised. Put white sugar into mixing bowl. Serve with caramel sauce. Fold brown sugar into mixing bowl. Put white sugar into mixing bowl. Add vanilla bean. Serve with caramel sauce. Add brown sugar.
1. Shakespeare语言 http://shakespearelang.sourceforge.net/
在所有的另类语言中，Shakespeare语言可能是最搞笑的了，并且难以置信的是它居然是SourceForge.net的一个项目。Shakespeare的代码完全模仿莎士比亚的戏剧。它也是一个基于栈的程序语言，程序中出场的每一个人物都代表一个栈。Shakespeare的代码自由度很高，因此同一个程序你可以写出完全不同的代码出来。Shakespeare的Hello World代码如下：The Infamous Hello World Program.
Romeo, a young man with a remarkable patience.
Juliet, a likewise young woman of remarkable grace.
Ophelia, a remarkable woman much in dispute with Hamlet.
Hamlet, the flatterer of Andersen Insulting A/S.
Act I: Hamlet's insults and flattery.
Scene I: The insulting of Romeo.
[Enter Hamlet and Romeo]
Hamlet:
You lying stupid fatherless big smelly half-witted coward!
You are as stupid as the difference between a handsome rich brave
hero and thyself! Speak your mind!
You are as brave as the sum of your fat little stuffed misused dusty
old rotten codpiece and a beautiful fair warm peaceful sunny summer's
day. You are as healthy as the difference between the sum of the
sweetest reddest rose and my father and yourself! Speak your mind!
You are as cowardly as the sum of yourself and the difference
between a big mighty proud kingdom and a horse. Speak your mind.
Speak your mind!
[Exit Romeo]
Scene II: The praising of Juliet.
[Enter Juliet]
Hamlet:
Thou art as sweet as the sum of the sum of Romeo and his horse and his
black cat! Speak thy mind!
[Exit Juliet]
Scene III: The praising of Ophelia.
[Enter Ophelia]
Hamlet:
Thou art as lovely as the product of a large rural town and my amazing
bottomless embroidered purse. Speak thy mind!
Thou art as loving as the product of the bluest clearest sweetest sky
and the sum of a squirrel and a white horse. Thou art as beautiful as
the difference between Juliet and thyself. Speak thy mind!
[Exeunt Ophelia and Hamlet]
Act II: Behind Hamlet's back.
Scene I: Romeo and Juliet's conversation.
[Enter Romeo and Juliet]
Romeo:
Speak your mind. You are as worried as the sum of yourself and the
difference between my small smooth hamster and my nose. Speak your
mind!
Juliet:
Speak YOUR mind! You are as bad as Hamlet! You are as small as the
difference between the square of the difference between my little pony
and your big hairy hound and the cube of your sorry little
codpiece. Speak your mind!
[Exit Romeo]
Scene II: Juliet and Ophelia's conversation.
[Enter Ophelia]
Juliet:
Thou art as good as the quotient between Romeo and the sum of a small
furry animal and a leech. Speak your mind!
Ophelia:
Thou art as disgusting as the quotient between Romeo and twice the
difference between a mistletoe and an oozing infected blister! Speak
your mind!
[Exeunt]
Matrix67收集整理
转贴请注明出处
Jul
15
10. LOLCODE语言 http://lolcode.com/
国外流行一种lolcat图片，经常出现在论坛的头像和签名图里。lolcat图片里有一只很乖的小动物（通常是小猫），旁边写几句很可爱的话（比如故意的语法错误、拼写错误、近似发音或者网络缩略语）。很多web 2.0的宕机页面就是一张lolcat图片。LOLCODE就是用这种可爱的猫猫语言来写程序。LOLCODE的代码通俗易懂，写起来非常可爱，小MM一定会喜欢。比如看看下面这段代码：HAI
CAN HAS STDIO?
I HAS A VAR
GIMMEH VAR
IZ VAR BIGGER THAN 10?
YARLY
BTW this is true
VISIBLE "BIG NUMBER!"
NOWAI
BTW this is false
VISIBLE "LITTLE NUMBER!"
KTHX
KTHXBYE
9. BrainFuck语言 http://www.muppetlabs.com/~breadbox/bf
BrainFuck语言是最简单的程序语言之一，只有8个有效字符，每个字符都有一个特定的含义。这8个字符控制一个指针在线性表里进行移动、读写、循环等操作。所有其它的字符都当作注释处理。我的Blog里曾对BrainFuck有过专门的介绍。
我很喜欢这个语言，甚至下载了它的编译器，写出不少BrainFuck程序。例如，下面这段代码可以输出我的网站域名“matrix67.com”：++++++++++[>+++++++++++<-]>-.
<+++[>----<-]>.<+++++[>++++<-]>-.--.
<+++[>---<-]>.<+++++[>+++<-]>.
>+++++[>+++++++++++<-]>-.+.<+++[>---<-]>.<<
<+++++[>----<-]>-.<+++[>++++<-]>.--.
BrainFuck语言有很多扩展。用不同的单词来代替这8个符号可以得到更多好玩的程序语言，有一些语言竟是把BrainFuck程序编码成图片或音乐作为程序代码。
8. Malbolge语言 http://www.lscheffer.com/malbolge.shtml
Malbolge是最早的一个以代码丑陋为目标而设计出的程序语言，你几乎不可能读懂Malbolge的代码。它共有8条指令，所有运算都基于3进制，控制程序流的唯一指令是无条件跳转。它的Hello World程序如下： (=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<
7. Whitespace语言 http://compsoc.dur.ac.uk/whitespace/
很多语言在编译时都会自动忽略空格、换行和Tab，而Whitespace语言正好相反，这个语言的有效字符只有三个（就是前面提到的三个空白符号），其它字符一律当作注释处理。这个语言对于机密工作者尤其有用，你可以把一个完整的Whitespace程序插入到一篇普通的文章中，谁也不会知道这里面竟然隐藏了一个机密代码。Whitespace也可以防止别人打印出源代码盗走。Whitespace源码的扩展名为.ws，这里是一个Whitespace的Hello World程序。我的Blog里也曾经介绍过Whitespace。
6. Befunge语言 http://quadium.net/funge/spec98.html
Befunge的代码是二维的。它用 < > v ^ 这四个符号来控制一个指针在代码中移动，指针经过一个字符或数字则把它压入一个栈，四则运算符号的功能就是弹出栈顶两个元素进行计算后把结果压回去。用 _ 和 | 来表示有条件的方向选择：当栈顶元素为0时向右（上）走，否则向左（下）走。& 和 ~ 分别用于读入数字或字符并压入栈，句号和逗号分别表示将栈顶元素作为整数或字符输出。最后以一个@符号表示程序结束。Befunge代码的注释不需要任何符号标明，你可以把注释写在程序的任何地方，只要运行时指针不会经过它就行了。你甚至可以把注释写在程序正中间，然后写代码时绕开注释写成一圈。Befunge的Hello World程序如下： v
>v"Hello world!"0<
,:
^_25*,@
看一个复杂的例子。我找了一个算圆周率的Befunge程序，看起来非常壮观。aa* v +------------------------+
vp*9920p*9930< | Pi generator in Bef-97 |
>:09a*pa*3/1+19a*p09a*g:09b*v | |
v_@# g*b90 p*b910 < p< | 7/2/1997, Kevin Vigor |
>19a*g:+1-29b*p19a*g::09v +------------------------+
v*a90g*b90*g*b91: _v#p*9<
>g-#v_ 2a*+\$ v :$
>\1-aa*ga*+v p
v1:/g*b92p*991:< *
>9b*p29b*g*199*g\v9
v*b92p*aa-1g*990-<9
>g2-29b*p099*g1-:0^
v -9p*b92:%ag*991 <
>#v_ 299*g1+299*p> ^
>09b*g:#v_$v
v93p*b90-1<
>9*g199*ga/+.v
v:g*992 <p*9 92-<
v_29b*g399*p ^
>09b*g:#v_v 1
vp*b90-1 < $ g
>199*g9`#v_'9,v *
>'0, >' ,299^
通常认为Befunge是第一个基于“二维控制流”的语言，后来衍生出的一大批类似的语言都是受的Befunge影响。例如PingPong语言就是把Befunge的四种箭头符号换成正反斜杠，控制指针移动方向90度旋转，起一个反弹的作用。
Matrix67收集整理
转贴请注明出处
Jul
13
你是否还记得，今年的4月13日是黑色星期五。短短三个月后，黑色星期五再次现身！为什么这一天老是出现呢？
恐怕心理原因是最好的解释。人们对黑色星期五的出现记忆更深刻，给人一种黑色星期五常常出现的错觉。有趣的是，仔细算一算，你会发现13日是星期五的次数真的要多一些。
很多人以为现在实行的历法是4年一循环，这是不对的。现在实行的历法以400年为一个循环。大家很容易忽略整百年的问题。一个很有意思的智力题就是问一个人是否可能连续5年不过生日。有个笑话说文科MM感叹她等了她男友4年，整整1460天，学理科的好友脱口而出“难道你男友是1900年的”。我们可以算一下在这400年中共有多少天：365*303+366*97=146097。这个数正好能被7整除。换句话说，现在与400年后的星期数不变，日历完全相同。在这400年里一共有4800个月，利用Zeller公式（见这里的最后一小节）可以编程统计出13日是星期几的次数最多，这对于OIer们再熟悉不过了，因为USACO有一道题就是干这种无聊的事情。下面就是程序运行后的结果：
可以看到，事实上13日是星期五的概率确实是最高的。
另外，注意到了么，利用“400年一周期”这个结论我们可以对USACO的那个题进行扩展，出一个Friday the Thirteenth数据加强版。
做人要厚道，转贴不注明出处者将受到黑色星期五的诅咒。
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原创
转贴请注明出处
