如何 $\Theta(1)$ 求highbit

学术版

ppip @ 2022-05-21 09:31:32

rt。我知道__builtin_clz是 \Theta(1) 的，我想知道具体实现。

by 望月Asta @ 2022-05-21 09:38:30

用汇编语言 逆向位扫描指令 bsr 实现的。

by MartingaleConverge @ 2022-05-21 09:38:56

一种方法是按位分块，每块预处理

by _Life_ @ 2022-05-21 09:45:22

刻在指令集里的

by StillEmpty @ 2022-05-21 09:47:10

我想提个问题哈，其实非要说，值域 2^w 的加法也是 O(w) 的（例如 unsigned int 的 w = 32。我们称二进制加法是 O(1) 的是因为计算机在处理二进制加法时是并行计算的。

by 蒟酱 @ 2022-05-21 14:16:39

@ppip 刻在指令集里的

by Cat_shao @ 2022-05-21 17:28:41

@ppip

确实是指令集，但是 clz 也有不用指令集的实现

https://zhuanlan.zhihu.com/p/70950198

|