上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。
为了能够实现常数时间的排序，我们首先应该想想，怎样才能“一下子”比较出所有数两两之间的大小。想到我们的整数串可以要有多大就有多大，我们萌生了一个大胆的想法：把本来就装了n个数的整数串继续扩展，让每个整数串里面都扩展到n^2个数，为n^2对数的比较做好准备。我们希望有一个操作能够让0100 0111 0001 0010变成下面两个更大的整数串；
0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 …. (大整数串A)
0100 0100 0100 0100 0111 0111 0111 0111 0001 0001 0001 0001 0010 0010 0010 0010 …. (大整数串B)
这为以后并行比较n^2个数对创造了条件。大整数串A很好构造，让0100 0111 0001 0010乘以
0000 0000 0000 0001 0000 0000 0000 0001 0000 0000 0000 0001 0000 0000 0000 0001 …. (基本掩码)
即可。上面这个数又是怎么在常数时间内生成的呢？很简单，只需要用64个1除以16个1即可，正如十进制中999999/99 = 010101一样。而连续的1又可以通过左移后减一得到，因此整个数可以在常数时间内算出。我们把这样的串叫做“基本掩码”，以后将多次用到。
难就难在大整数串B。大整数串B又可以看作是
0000 0000 0000 0100 0000 0000 0000 0111 0000 0000 0000 0001 0000 0000 0000 0010 …. (1)
乘以0001 0001 0001 0001得到的结果。后面这个0001 0001 0001 0001的生成办法和前面一样，关键是前面这个等价于“加大定宽”的操作(1)该怎么做。我当初思考这个问题时就卡在这一步了。Michael Brand就是牛，他想到了这关键性的一步：要是“定宽”再大一点就好了。如果需要生成的大整数串是
0000 0000 0000 0000 0100 0000 0000 0000 0000 0111 0000 0000 0000 0000 0001 0000 0000 0000 0000 0010 …. (2)
的话就好办了，只需要把大整数串A
0000 0000 0000 0000 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010
与
0000 0000 0000 0000 1111 0000 0000 0000 0000 1111 0000 0000 0000 0000 1111 0000 0000 0000 0000 1111 …. (3)
进行and运算即可。上面的序列(3)可由基本掩码乘以1111获得。我们甚至可以实现“缩小定宽”的操作，只要新定宽和原定宽相差足够多（具体的说，新定宽×数的个数≤原定宽）。把(2)式对1111 1111 1111 1111取模，我们就可以重新得到0100 0111 0001 0010（这个取余操作相当于把原来的64位数截成4个16位数后求和，正如十进制中23000067 mod 9999 = 2367 = 2300 + 0067一样）。
有了“定宽扩展到充分大”和“定宽缩小到充分小”的操作，我们立即得到了大整数B的常数时间生成方法：先把原始整数串0100 0111 0001 0010的定宽加到足够大，然后再缩小到原定宽的n倍（例子中为4×4=16）。这两个操作都是常数级别的，因此总的操作也是常数级别的。乘以0001 0001 0001 0001后，我们就得到了大整数串B。
接下来，我们着手构造比较函数。我们希望能够同时比较两个整数串对应的16个数，并且返回新的大整数串来表明每一对数中哪个大哪个小。我们比较时采用的基本方法就是，如果a比b小，那么~a+b一定会越界。考虑一个中间情况就是，如果a=b话，~a+b正好就等于111…11，是该定宽下所能表示的最大数。如果a的值减小一些，~a的值就会增大一些，~a+b就溢出了；反之，如果a的值变大一些，~a的值反而会减小，~a+b就应该小于该定宽下的最大数。熟悉补码的朋友可能想到，这是受到了计算机做减法的办法的启发。为了能够让大整数串顺利接受溢出并返回结果，在最初取定宽时应该让定宽大小比最大数位数还多一位（相当于符号位）。即使当初没想到这一点，把整数串排的紧紧的，现在后悔也来得及——我们已经有了常数时间修改定宽的办法。整个大整数串取反后，我们用一个and运算把多出来的符号位归零。相加后再用and运算把符号位提取出来，通过右移获得比较结果。
0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 0100 0111 0001 0010 …. (大整数串A)
0100 0100 0100 0100 0111 0111 0111 0111 0001 0001 0001 0001 0010 0010 0010 0010 …. (大整数串B)
1011 1011 1011 1011 1000 1000 1000 1000 1110 1110 1110 1110 1101 1101 1101 1101 …. (大整数串B取反)
0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 0111 …. (掩码，可在常数时间里生成)
0011 0011 0011 0011 0000 0000 0000 0000 0110 0110 0110 0110 0101 0101 0101 0101 …. (上面两序列and后的结果)
0111 1010 0100 0101 0100 0111 0001 0010 1010 1101 0111 1000 1001 1100 0110 0111 …. (大整数串A与上一序列相加)
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 …. (掩码，可在常数时间里生成)
0000 1000 0000 0000 0000 0000 0000 0000 1000 1000 0000 1000 1000 1000 0000 0000 …. (上面两序列and后的结果)
0000 0001 0000 0000 0000 0000 0000 0000 0001 0001 0000 0001 0001 0001 0000 0000 …. (上一序列右移3位)
最后这个整数串中只有0和1两个数，1表示对应位置上B串的数比A串的小，0的意义则正好相反。如果最初读入的n个数没有重复的话，这里面应该恰好有n(n-1)/2个数字1（本例中则是6个）。
到这里，我们已经看到胜利的希望了。如果您真能一个字一个字的读到这里来，我向您表示深深的崇敬和膜拜。剩下的事情已经不多了，主要是统计和还原两个操作。
我们得到了一个表示出16个大小关系的整数串，现在我们想把它们合并回去，算出对于每一个给定的数，有多少个数比它小。换句话说，我们希望将比较结果中的每第四个数加起来，得到0010 0011 0000 0001，其中0010就是0000、0000、0001、0001四个数相加的结果，它表示输入数据中有两个数比输入的第一个数0100小，类似地其余的数也是由对应的四个值相加得到。实现这一点并不困难，只需要让比较结果对1111 1111 1111 1111取模即可，其原理与前面的缩小定宽操作是相同的。我们把这个序列叫做索引序列。
最后一个步骤便是按照索引0010 0011 0000 0001将0100 0111 0001 0010重新排列，使得Input[i] = Result[Index[i]]。这一步又是一大难关，我想即使我当初想到了改变定宽的方法，最终也会卡在这最后一步。为了实现顺序排列，我们需要强行建立一个有序索引。我们希望在常数时间内得到“计数序列”0000 0001 0010 0011，它将用于进一步的操作。计数序列的生成并不难，要想生成一个有n项的定宽为w的计数序列，我们仅仅需要找出一个等价于
0·2^(w(n-1)) + 1·2^(w(n-2)) + 2·2^(w(n-3)) + … + (n-1)·2^0
的公式来就行了。我们不用把时间浪费在寻找公式上，用Mathematica就可以得到我们想要的结果。从下图中可以看到一个好消息：公式是O(1)的，其复杂度不随变量增大而增大，并且所有计算都可以在O(1)的时间内完成。稍作验证可知，这个公式是正确的。
接下来我们要做的是，将索引序列与计数序列进行比较，比较的方法将再次套用上述从生成大整数串到并行比较n^2个数对的所有步骤。
0000 0000 0000 0000 0001 0001 0001 0001 0010 0010 0010 0010 0011 0011 0011 0011 …. (扩展的计数序列)
0010 0011 0000 0001 0010 0011 0000 0001 0010 0011 0000 0001 0010 0011 0000 0001 …. (扩展的索引序列)
0001 0001 0000 0001 0001 0001 0000 0000 0000 0001 0000 0000 0000 0000 0000 0000 …. (对应位置上计数序列较小)
0000 0000 0000 0000 0000 0000 0001 0000 0000 0000 0001 0001 0001 0000 0001 0001 …. (对应位置上索引序列较小)
同样地，上面两个比较结果中数字1各有6个，一共12个。另外还有4个位置，你也不比我小，我也不比你小，两次比较的结果都是“0”。显然，这4个位置所对应的数从左至右分别是前4个自然数。用or运算和xor运算提取出这四个位置，然后与最初的大整数串B进行and运算：
0001 0001 0000 0001 0001 0001 0001 0000 0000 0001 0001 0001 0001 0000 0001 0001 …. (上述两比较结果的or运算)
0000 0000 0001 0000 0000 0000 0000 0001 0001 0000 0000 0000 0000 0001 0000 0000 …. (上一序列与基本掩码进行异或)
0000 0000 1111 0000 0000 0000 0000 1111 1111 0000 0000 0000 0000 1111 0000 0000 …. (上一序列乘以1111)
0100 0100 0100 0100 0111 0111 0111 0111 0001 0001 0001 0001 0010 0010 0010 0010 …. (大整数串B)
0000 0000 0100 0000 0000 0000 0000 0111 0001 0000 0000 0000 0000 0010 0000 0000 …. (上面两个序列and后的结果)
最后这个序列满足这样的性质：数的出现顺序和输入数据相同，并且当你把它从左至右划分为n个n元组之后，输入数据中第i小的数恰好在它所在的n元组中的第i个位置。和上面一样，我们需要把每第四个元素合并在一起。将最后这个结果模1111 1111 1111 1111后，即得到0001 0010 0100 0111。这样，我们就在常数时间里完成了n个数的排序。
嗯，你真强大，竟然一路看到这里来了。不知道大伙儿看明白没，麻烦大家在下面留句话。或许大家会想，O(1)的排序算法……总算不能再牛B了吧？呵呵，你又错了，我们现在所看到的仍然太表层，真正牛B的还远没有挖掘出来呢！接下来，我们还会利用大整数的理想运算做一些更加牛B的事情。
沙发之
强.膜拜
囧rz…
看了2次才看明白.
最后那一步运算太精妙了.
痛苦地集中精力辨认0和1同时理解汉字中……
m年之后，计算机也发展到了2^n位的时代，这个玩意儿不是大显身手了
a~喜歡喵～
進化越來越低級了～
看完了。。。。。。。。看完到最后倒數第二個自然段。。。才發現。。。題目看錯了= =。。。。。。。。倒。。。。
不過MM你的英語好強啊～
然后实际一点的就是bitcount?
试着写了一个O(1)的1的个数
只能算32766以下的，而且速度不怎么样
那个是什么软件？
拜下matrix67…
二进制无比神奇……
太牛了..
当时做这题的时候我在定宽扩展那就卡住了
原来后面还有那么多巧妙的构造
谢谢M67的翻译.
近两期的solution
http://sites.google.com/site/uyhipchinese/
没给翻译..
还是一头雾水
有没有“汇编”代码？
Function Sort(X,W,C)
‘X=array,W=width,C=count
‘X=0100 0111 0001 0010
‘W=4 C=4
Dim A,B,R,WC
WC=W*C
B=X*[1 Shl WC-1]/(1 Shl W-1)
A=WidthTo(X,W,WC)*WidthTo(1 Shl C,1,W)
R=WidthTo[1 Shl(C*C)-1,1,W]Shr 1
A=A Or(R Shl W Shr 1-C)-B
A=A Shr(W-1)
A=A And C’A>B
A=A Mod(1 Shl WC-1)
Dim P,Q
Q=10001000100010001^2
…
输入
0111 0001 0101 0001，输出不是
0001 0001 0101 0111，是
0000 0010 0101 0111【脑补】对不对？
还是一头雾水来着
快速祛痘小妙招一： 保持良好的生活习惯
1、注意脸部清洁。
长痘痘很多时候都是因 祛痘小妙招 为油脂分泌过多堵塞毛孔造成的，因此做好清洁工作就十分必要啦！首先要选择弱酸性的肥皂或刺激性小的洗面奶，在低于体温的温水手中揉搓起泡后捧 快速祛痘小妙招重拾光滑肌 起来洗脸，轻柔的螺旋式按摩一分钟之后，即可用稍热（比体温高一点）的水冲洗干净了。每天洗2-3次，别忘了洗脸后上点化妆水，可以保湿并收缩毛孔哦！
2、保证充足的睡眠。
睡眠不足会导致肝功能下降，体内毒素无法及时排出，自然也就给了痘痘疯长的机会。想要消灭他们最好在十一点之前睡觉，实在不行也别熬过十二点，而且要睡饱八小时哦！ 藏宝教你这些祛痘妙招，轻松拥有嫩白美肌 特别是第二
祛痘前，双手一定要清洗干净，最好还要用化妆水擦一次。洗脸后，切记不能用收敛性的化妆 祛痘 水，否则会让毛 藏宝教你如何快速祛痘和痘印 孔收缩，更难挤出痘痘。青春棒一定要先用酒杯精或化妆水消毒干净。用青春棒挤痘痘时，所接触到范围较小，不会影响或伤害到痘痘旁边的正常皮肤,藏宝教你如何快速祛痘和痘印。不过要记得挤完一颗之后要用纸巾擦干净再进攻下一颗痘痘。若是忘记清洁，挤出来的痘痘留在上面的脓蔓延到 藏宝教你怎么祛痘 下一颗痘痘会很不卫生哦。
Step 2
挤痘痘前，可以先在痘痘的地方擦柔软角质化妆水，这样挤起痘痘来更容易。而对付那些顽强的粉刺时，柔软性角质化妆水同样能起到软化作用，而且这样在挤的时候疼痛感会稍稍减弱些。
Step 3
春季万物复苏，也是皮肤容易出现问 祛痘小妙招 题的时候，对于青春 藏宝教你祛痘小妙招,快速简单祛痘 期的少男少女来说，一定要知晓一些祛痘的妙招：
一、祛痘小妙招第一古方：莹肌如玉散。
目前中药里面祛痘的古方中最火的要算莹肌如玉散了，莹肌如玉散出自《普济方》，莹肌如玉散是以楮实、白芨、升麻、甘松、白芷、白丁香、砂仁、糯米末、皂角原料。将这些药材一起研磨成粉，混合均匀后， 祛痘产品 每天取少量涂脸，即可祛除痘痘，令颜面光洁如玉，因而得名莹肌如玉散。莹肌如玉散配方中不含绿豆，因为绿豆只清表面毒素，而不清皮下痘毒。而是采用了升麻等物，升麻不但能像绿豆一样有清热下火的效果，还能升发痘毒，所以祛痘之后一般不复发。莹肌如玉散
快速祛痘小妙招一： 保持良好的生活习惯
祛痘小妙招
1、注意脸部清洁。
长痘痘很多时候都是因为油脂分泌过多堵塞毛孔造成的， 藏宝教你怎么祛痘 因此做好清洁工作就十分必要啦！首先要选择弱酸性的肥皂或刺激性小的洗面奶，在低于体温的温水手中揉搓起泡后捧起来洗脸，轻柔的螺旋式按摩一分钟之后，即可用稍热（比体温高一点）的水冲洗干净了。每天洗2-3次，别忘了洗脸后上点化妆水，可以保湿并收缩毛孔哦,藏宝教你怎么祛痘！
2、保证充足的睡眠。
藏宝教你怎么祛痘
睡眠不足会导致肝功能下降，体内毒素无法及时排出,藏宝教你怎么祛痘，自然也就给了痘痘疯长的机会。想要消灭他们最好在十一点之前睡觉，实在不行也别熬过十
祛痘前，双手一定要清洗干净，最好还要用化妆水 祛痘 擦一次。洗脸后,，切记不能 祛痘8大食物内调祛痘见效快 用收敛性的化妆水，否则会让毛孔收缩，更难挤出痘痘。青春棒一定要先用酒杯精或化妆水消毒干净。用青春棒挤痘痘时，所接触到范围较小，不会影响或伤害到痘痘旁边的正常皮肤。不过要记得挤完一颗之后 妙招让你轻松祛痘 要用纸巾擦干净再进攻下一颗痘痘。若是忘记清洁，挤出来的痘痘留在上面的脓蔓延到下一颗痘痘会很不卫生哦,祛痘8大食物内调祛痘见效快。
Step 2
挤痘痘前，可以先在痘痘的地方擦柔软角质化妆水，这样挤起痘痘来更容易。而对付那些顽强的粉刺时，柔软性角质化妆水同样能起到软化作用，而且这样在挤的时候疼痛感会稍稍减弱些。
Step 3