白菜的博客

下面分享的是我自己写的三个代码，里面有些题目也是我自己出的。这些代码都是在我的Pascal时写的，恕不提供C语言了。代码写得并不好，我只是想告诉大家位运算在实战中的应用，包括了搜索和状态压缩DP方面的题目。其实大家可以在网上找到更多用位运算优化的题目，这里整理出一些自己写的代码，只是为了原创系列文章的完整性。这一系列文章到这里就结束了，希望大家能有所收获。
    Matrix67原创，转贴请注明出处。

阅读剩余部分...

今天我们来看两个稍微复杂一点的例子。

n皇后问题位运算版
    n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。
procedure test(row,ld,rd:longint);
var
      pos,p:longint;
begin

阅读剩余部分...

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

二进制中的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没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。

阅读剩余部分...

1 下面四个选项中有几个是错误的？
   A. 1个            B. 2个
   C. 3个            D. 4个

2.
   A. 123456         B. 234567
   C. 345678         D. 456789

（1）如果48=0，那么84等于什么？
   A.1 B.T C.--）D.00
（2） 这道题的题目是什么？
   A. 关于递归运算的题目
   B. 关于线性规划的题目
   C. 关于汇编语言的题目
   D. 关于郭晶晶的一切

    昨天晚上半夜三更，一个PHP群里有人问起大数阶乘的计算。我忙于看书，再者我一向秉持大晚上的讨论技术不吉利的观念，也就没有回答了。对于比较小的数，可以用定义计算
$num=range(1,100);
echo array_product($num);
这个谁都会，但是当N比较大的时候，就是DOUBLE类型也无法保存计算结果了。有人说。拆开来，一段一段的算，这是错的。你想过没，你即使拆成了很多段，但是到最后，还是不得不把中间结果相乘，又卡在了超大数相乘的地方了。
在你要计算大数阶乘的时候，我先介绍一个数学公式
①n!=10^{^}m(^表示幂，这一步大家应该都能理解，我就只是个把阶乘表示成幂指数的一个等式，这里我要算M的值)
②对两边取10为底的对数。log₁₀n!=log₁₀ 10^{^}m=m，这一步我们就把M求出来了。
③左边利用对数的积化和公式，有
log₁₀n!=log₁₀n*(n-1)*(n-2)*(n-3)...*2*1=log₁₀n+log₁₀(n-1)+....log₁₀3+og₁₀2=M
到这里，我们就把M求出来了，那M有啥用呢？M实际上就是n!的精确位数，对于强类型语言，可以用M来开辟内存空间，对于弱类型语言，不像C那样数组大小必须指定，但是我们可以判断大概多大的数运算后位数是多少，如果位数不超过其所能表示的最大数值范围，就用内置的函数或定义来直接计算。就如PHP，直接用array_product来计算成乘积。（我看到群里的那个同学用的range(1,172)做例子，我估计他是一步一步测出来的，到了172的阶乘就溢出无法表示了）N比较大了，就只能模拟乘法了。
在小学的时候，我们都学过乘法，149*7，我们是这么做的：
①9*7=63 进6写3，7*9/10=6,7*9%10=3
②4*7=28，加6等于34，进3写4；
③1*7=7,7+3=10，进1写0
最终结果就是1043
小学生都会吧，反正我们小学就是教我们这么做的，口诀也是这么背的。
你让小学生计算465768233434545*1112574233，小学生都会计算，只是比较耗时间而已。
对的，我们就是要做一回小学生，来模拟这个过程。
a*b%10 就是我们每一步乘法的个位，而a*b/10就是每一步的进位，也就是10位（每一位对于数相乘结果最大为9*9=81，不超过两位）
下一位的结果加上进位，求出个位，求出进位。。。循环执行。
只不过这个阶乘比较麻烦，两个乘数都大一1位，149*7我们会了，那149*34567，运用小学数学的思维，先149*7，再149*6.。。嵌套循环而已。1000！那最大的运算也不过1000*999，其中真正最大的无非是999*998，最大的乘法是999*9，太小了，10000000！最大的乘法单步骤也不过是9999999*9，太小了！还有什么我们计算不出来的。只不过循环次数多了，慢一点而已。
这就是大数相乘，模拟成单步相乘，那就简单了。其实也就是模拟成字符串。我们把所有的数字都放在数组里，一个一个取出来运算。如果你还看不懂，那就先直接去看看大数相乘的原理吧。
代码我就不贴了，百度一对堆，不过原理你得清楚。比如说把C语言写的转成PHP，我看好你。

项目中碰到 PHP 和数据库之间，计算存在时间计算误差。大致的情况为根据段时间字符串，例如

2012-12-14 00:00:00 UTC

使用 MySQL 的 UNIX_TIMESTAMP 函数以及 PHP 的 strtotime 计算得出的时间戳，大概有半分钟（差不多有28秒）的误差。

同时，比较‘诡异’的是直接使用当前时间（MySQL 中 UNIX_TIMESTAMP 不带参数，同时 PHP 直接使用 time 函数），却不存在误差（测试脚本）。

排除了 PHP 和 MySQL 之间因为时区设置造成的时间误差 -- 根据经验，如果是时区设置造成的时间误差，应该有几个小时不会那么少。

搜索解决问题期间扫了下这篇帖子，觉得应该是‘闰秒’这玩意造成的问题。搜索 PHP 闰秒相关的配置似乎没有相关的，不过在这里似乎找到了些答案。

You also can experience this behavior if your system timezone

is with leap seconds. To avoid the problem in this case please

run query UPDATE mysql.time_zone SET Use_leap_seconds='N' 

and restart the server. Please inform us if this helps.

按照上述的步骤执行，解决了问题。

回过头来，我在工作机（Windows）上测试，发现并不起作用。研究了下，原来闰秒也需要操作系统的支持：

1、对于大多数新的 Linux 内核，在设计时它们都是支持闰

   秒的，这一点在 REHL4/5 的 2.6.x 内核中得到肯定。 

2、如果 Linux 系统没有配种某种时间同步机制（比如NTP），

   那么和闰秒无关，唯一导致的结果只是系统时间会比 UTC

   时间快一秒。 

3、Window Time Service 不支持闰秒，包括服务器和客户端。

回过头来考虑项目中碰到的这种情况，直接使用时间戳存储时间点会更精确些。最后，提供下相关的测试脚本，看看你的环境是否也会有类似的问题。