finding the first set bit in a machine word can all be O(lg(n))

luckysir

这是  从小工到专家 这本书里边在说到二分法的时间复杂度时说的
如果是你的话，你会咋实现？

有个问题不明白，作者在这里是仅就二分法举一个例子呢，还是在实际应用中都这么用，因为一个机器字好像也不会太长，

塑料袋

阿贝尔大师说过：应该阅读大师的而不是他们的门徒的著作

那本书的作者好像连门徒都算不上吧

luckysir

回复 2# 塑料袋

说的在理，可是门徒也比俺要高大诶，门徒离俺比较近，所以完全遮挡住了大师，


哎老了，我觉得我现在的进步速度像蜗牛

OwnWaterloo

回复 1# luckysir

应该仅仅是作为二分的一个例子。

实际使用上可以将这个作为保底的手段。对机器、编译器(暂时)不知情时至少有一段可以工作的C代码。

然后当必要时去找更好的手段。
比如如果知道机器是x86，就可以用bsr指令。
如果知道机器使用ieee754浮点格式，就可以利用它的指数部分。
如果知道编译器是vc或者gcc，就可以利用它们提供的扩展，名字我忘了……

fanasy

回复 2# 塑料袋


    级别不到，看看门徒写的好书也不错， 不过楼主这本书，我翻了一下就没兴趣了，没有阅读快感

塑料袋

回复 5# fanasy


其实我灰常不明白，学习那些O(1),O(2)......O(100)之类的算法有个鸟用，包括哪些什么语言的窍门，编程的技巧.....都是雕虫小技而已，上不得台面。一句话：耍小聪明。

上的了台面的东西，一定是系统的，有组织的，能产生积累效应。而且越上的了台面的东西，一定是越需要基础强大的。

哥们大概4，5年前，去google面过一次，上来那边扯淡什么怎么有效率的算32bit里有多少个1，哥们直接一句话打回去：hweight64,hweight32，kernel这俩函数就是算这个的，现成的死路子；然后接着又问什么咬疯狗，说谎话的，越来越不着边，我就日的。我巨恶心这种面试，耍小聪明。

三月廿七

回复 6# 塑料袋
我也是特别恶心这样的题目，
我第一次面试时遇到都是这类题目，结果那家公司现在已经灭了
而我后来去的公司，就问了一个简单的结构体问题，反而却是最大的xxx公司

我发现越是牛B的公司，题目出的越是简单~
就是那种山寨货特别喜欢装B～～

塑料袋

回复 7# 三月廿七


哥们现在也面了不少人了，两项最重要：

1) 性格：坐得住，塌的下心
2) 基础：只要不太差强人意就可。

塑料袋

三月廿七 发表于 2012-03-27 23:16
回复 6# 塑料袋
我发现越是牛B的公司，题目出的越是简单~.

某些时候，你要真是以为简单，那就上套了。

哥们一个同事，面试别人时，总是问一个问题，memcpy，自己实现。

就这个问题，肯定地说，水要多深就有多深。

三月廿七

回复 9# 塑料袋

你说说怎么个深的？ 我觉得这是个特别浅的问题啊