神秘常量复出！用0x077CB531计算末尾0的个数

2010 年 12 月 13 日 / 48 条评论

大家或许还记得 Quake III 里面的一段有如天书般的代码，其中用到的神秘常量 0x5F3759DF 究竟是怎么一回事，着实让不少人伤透了脑筋。今天，我见到了一段同样诡异的代码。
下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 0 。比如， 123 456 的二进制表达是 1 11100010 01000000 ，因此这个程序给出的结果就是 6 。

unsigned int v; // find the number of trailing zeros in 32-bit v int r; // result goes here static const int MultiplyDeBruijnBitPosition[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

熟悉位运算的朋友们可以认出， v & -v 的作用就是取出右起连续的 0 以及首次出现的 1 。当 v = 123 456 时， v & -v 就等于 64 ，即二进制的 1000000 。怪就怪在，这个 0x077CB531 是怎么回事？数组 MultiplyDeBruijnBitPosition 又是什么玩意儿呢？

用Mathematica寻找最相似的汉字

2010 年 3 月 8 日 / 89 条评论

Mathematica 提供了一个看上去毫无用途的无厘头函数 Rasterize ，它可以以图片的格式输出运算结果。比如，下面这个句子可以打印出 (x+1)^n 的展开式的“倒影”：

今天我突然想到，我们可以利用这个函数很方便地分析汉字在图象上的性质。函数 Binarize 可以把图象转换为单色单通道， ImageData 则可以把图象转换成数组的形式，以便我们定量分析。因此，下面这句话就可以把一个汉字转换成 12*12 的 01 矩阵：

满足xy恰有k个约数的(x,y)所组成的图形

2010 年 2 月 11 日 / 29 条评论

刚才在这里看到了如题所说的图像，立即想到用 Mathematica 验证一下。我选出了几个个人比较感兴趣的 k ，再用一句话便可输出所有对应 k 的图像：

kArray = {2, 3, 4, 6, 8, 10, 12, 14, 16, 18, 20, 36, 50}; For[i = 1, i <= Length[kArray], i++, Export["F:\" <> ToString[kArray[[i]]] <> ".png", ArrayPlot[Table[Boole[Length[Divisors[x*y]] == kArray[[i]]], {x, 1, 400}, {y, 1, 400}], PixelConstrained -> {1, 1}, Frame -> False]]];

当 k=2 时，由于只有素数才有两个约数，因此所有点都是形如 (p, 1) 或者 (1, p) 的点，其中 p 为某个素数：

IBM Ponder This史上最难谜题：给出谜底猜谜面

2009 年 4 月 9 日 / 25 条评论

2009年2月份IBM Ponder This的谜题可能是从98年谜题月赛开办以来最难的谜题。谜题发布一个月之后仍然没有任何人答对，主办人不得不宣布延迟一个月，并再三增加提示。最终，答对此题的仍然只有7个人。很久没有看到如此精彩的谜题了，有兴趣的网友不妨试一试。
题目非常有趣。传统的谜题是给出谜面求解谜底，但这个谜题则恰恰相反：下面这一串数字是某个问题的答案，你能猜出这个问题是什么吗？这串数字里有一个错误在哪里？

900F 80F0 8F00 80CA BE12 AA90 9400 0048 3E5B 8AC0 3400 00CB BC81 8A08 3C00 0050 BE43 00C0 3E00 A019 8059 BE13 2000 0092 BE9B 2A0B 2A00 8052 8841 04C0 3E00 840B 084B 0098 E000 8819 845A 8012 0300 0050 826F 0500 0600 846E 8264 0900 0A00 8065 0C00 0072 A054 8368 8569 4800 4400 8573 4200 4100 8349 8542 2800 2400 854D 2200 2100 9F00 E000 8888 8444 8000 0030 0DED 8222 0050 0060 8444 8222 0090 00A0 8000 00C0 0DED A000 8333 8555 4080 4040 8555 4020 4010 8333 8555 2080 2040 8555 2020 2010 8300 8500 8030 8050 0880 0840 8050 0820 0810 8030 8050 0480 0440 8050 0420 0410 8500 8030 8050 0280 0240 8050 0220 0210 8030 8050 0180 0140 8050 0120 0110 90F0 9F00 E000 8888 8444 8000 0003 0DED 8222 0005 0006 8444 8222 0009 000A 8000 000C 0DED A000 8333 8555 4008 4004 8555 4002 4001 8333 8555 2008 2004 8555 2002 2001 8300 8500 8003 8005 0808 0804 8005 0802 0801 8003 8005 0408 0404 8005 0402 0401 8500 8003 8005 0208 0204 8005 0202 0201 8003 8005 0108 0104 8005 0102 0101 9F00 8030 8050 8003 8005 0088 0084 8005 0082 0081 8003 8005 0048 0044 8005 0042 0041 8050 8003 8005 0028 0024 8005 0022 0021 8003 8005 0018 0014 8005 0012 0011 80FF 8F0F A333 8000 5000 0DED 8000 3000 0DED A333 C555 1800 1400 C555 1200 1100 8F0F A333 A555 1080 1040 A555 1020 1010 A333 A555 1008 1004 A555 1002 1001

追Geek MM小工具：IOCCC情书生成器v0.1

2009 年 3 月 22 日 / 52 条评论