白菜的博客

=====   真正强的东西来了！   =====

二进制中的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，第一次异或操作的结果如下：

阅读剩余部分...

什么是位运算？
    程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：
         110
AND 1011
----------
    0010  -->  2
    由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。

阅读剩余部分...

人有十个手指，用手指的伸屈来计数非常方便。但一旦对象的数目超过10个了，手指头就不够用了。当然，有人会想到还有脚趾头。搬弄脚趾头是不现实的，数手指头只需要站着比划一下就可以了，数脚趾头还需要坐下来慢慢研究。一种好的方法是每次数完了十个指头后在什么地方做一个标记，比如在地上放一个木棒。人们可以把这根木棒想像成一个“大指头”，它相当于十个指头。这样，我有37个MM就被表示成了地上3个木棒加上我7个手指头。哈哈，你的MM数只有两根木棒加4个手指头，于是我的MM比你的多。久而久之，人们就只接受0到9这十个数字了，再大的数就用几个数字合起来表示。这种“满十进一”的数字系统就叫做十进位制。
    如果人只有八个手指头又会怎样呢？那我们现在很可能正在使用八进制，数学发展起来后我们最终只接受八个数字，而大于8的数字就用更高一级的计量单位表示。代表这八个数字的很可能是些星际之门里的怪符号，这里为了便于叙述，我们仍然使用阿拉伯数字的0到7来表示。于是，人类数数的方式将变为：0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,...。这里，数字8被记作10，数字64则用100代替。在这个数学世界里，6+5=13，因为6+1得到的数已经是一位数中最大的了，再加的话只能“进一位”了。“满八进一”将成为数学运算的基本法则。
    如果人有12根手指，12进制将成为更难想像的事。在12进制中，人类会把10和11直接想成是一个“数字”。研究的进位制大于10时，大于9的数字我们习惯上用大写字母ABC来表示。这样，自然数序列里将多出两个符号A和B来，数数的方式变为...,8,9,A,B,10,11,12,...。

阅读剩余部分...