如何使用 C 查找数字中零的前导数

Question

例如，如果我有数字 64，那么它的二进制表示将是 0000 0000 0000 0000 0000 0000 0100 0000 所以前导零的数量是 25。记住我必须在 O(1) 时间内计算这个。

请告诉我正确的方法。即使您的复杂度>O(1)，也请发布您的答案。谢谢

Answer 1

因为以 2 为底的对数粗略地表示表示数字所需的位数，因此它可能在答案中有用：

irb(main):012:0> 31 - (Math::log(64) / Math::log(2)).floor()
=> 25
irb(main):013:0> 31 - (Math::log(65) / Math::log(2)).floor()
=> 25
irb(main):014:0> 31 - (Math::log(127) / Math::log(2)).floor()
=> 25
irb(main):015:0> 31 - (Math::log(128) / Math::log(2)).floor()
=> 24

当然，使用它的一个缺点log(3)是它是一个浮点例程。可能有一些非常聪明的位技巧来查找整数中前导零位的数量，但我想不出其中的一个......