3.1.23

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

这里的右移操作可以理解为 「小数点前移一位」
即数字依次向右退一位,个位上的数字被舍弃。
对于十进制,小数点前移一位会使 $ n $ 变为 $ \lfloor n / 10 \rfloor $。
同样对于二进制就会使 $ n $ 变为 $ \lfloor n / 2 \rfloor $。
当需要除以 $ 2 $ 的 $ k $ 次幂的时候,可以用右移 $ k $ 位代替并减少时间开销。
同理可以用左移 $ k $ 位来代替乘以 $ 2 $ 的 $ k $ 次幂。
注:
这样会降低程序可读性,
并且某些语言(C / C++)的编译器已经可以自动执行这项优化了。
请充分考虑你的代码受众之后再决定是否采用这种写法。

二分查找的最大查找次数 = $ \lg N + 1$ (见 3.1.20 的证明 3.1.20
一个数最多被左移的次数也正好等于 $ \lfloor \lg N \rfloor + 1 $
(任意正整数都能被表示为 $ 2 ^ k + m $ 的形式,即 $ k +1 $ 位二进制数)
因此一次二分查找所需的最大比较次数正好是 $ N $ 的二进制表示的位数。

上一题 下一题