2005.10.13

一道经典的微软面试题，获取16或32位整数二进制表达中1的的个数。由于太过经典，现在不会再问了。有各种回答，从穷举法到查表法。我最喜欢的方案是

n   = 0;
while ( x )
{
    n++;
    x   = x & ( x - 1 );
}

scz:

说实话，这类题我一个也不会，我就不是这块料，所以后面的内容我懒得翻译了。

2005.10.14

当年我为NT 3.1实现网络文件系统，碰上一个需求，要用64位数除以32位数。那个时代编译器尚不支持64位数学运算，为了处理这类问题，有一些内部RTL函数可用，加、减、乘都有现成的函数，但没有除。

之前我从未研究过这块，于是我去问Dave Cutler，他什么都会。他告诉我数学原理后我便着手去实现他所说的算法。由于这段代码仅用于测试环境中某个特定场景，不太可能在别处使用，我没有专门花很多时间优化它。老老实实用C写的，有两个版本，一个处理64位除以64位，另一个处理64位除以32位。CPU支持后者，我本可以写一个汇编版本，但我们真地很注重可移植性，尤其当其并非被频繁调用时，于是我选择了更具可移植性的方案。题外话，有人警告过我，如果我用汇编语言写东西，他们会将我的拇指置于炽热的火炉上，慢慢烤熟。

做过足够的单元测试后，我提交了新的RTL API。这是我第一次做数值处理，开心。

当年NT团队的旧友们看到此处，已知接下来发生了什么。

后来我离开了NT团队，调到Exchange团队去了。大概三年后，我听说了一段离开后的故事。开发NT 3.5、NT 4时，Dave花了大量时间分析系统性能瓶颈，寻求更快的方案。某天，他注意到了我的除法函数。

某个系统核心组件需要做64位数除以32位数，我猜是GDI，但我不确定。编译器不支持啊，他们就在RTL API中翻，发现了我的实现，就这么用上了，在最内层的循环里。突然之间，为解决现实中永远不会出现的小问题而编写的愚蠢函数变成了操作系统性能敏感组件内层循环的一部分。

当Cutler找到瓶颈时，他审查了我的代码，暴跳如雷，不停地咒骂我。后来他用汇编重写了一版。

这个故事是想告诉大家，向系统库中提交代码时，务必确保其性能最优，因为你永远不知道谁会用到它，还是在内层循环中。

开发NT 3.1时犯了很多错。恕我直言，最大的错误是，有个关键团队决定用C++开发。不幸的是，当时没有原生的C++编译器，他们用cfront先将C++转成C，再交给C编译器。毋庸置疑，效果不佳。

我不想在此点名指责谁，除非是我本人的错误。我非常努力地不批评其他人的工作，尤其当我已经不在相关团队时。同样，我不想讨论Gordon和Dave之间的政治，我非常尊重他二位，我不能那样做。

MIPS无疑是NT在其上启动的第一个平台，但x86紧随其后。我很确定我们先在R4000上启动了NT。

评论区的内容

Dave带了大概十三四名前DEC员工加入微软。

Gordon Letwin是OS/2的架构师，与Cutler相处得并不好。