haskell - 在haskell中查找整数的位长

Question

我想在 Haskell 中找到 Integral 类型的位长(即最高设置位的索引)——就像 Java 中的相应方法一样或 Python .

我能想到的最好办法是使用右移进行二进制搜索，如下所示:

bitLength :: Bits a => a -> Int
bitLength x = fst $ until (\ (lo,hi) -> lo >= hi) bsIter (0, until test (*2) 1)
  where test n = shiftR x n == zeroBits
        bsIter (lo, hi)
          | test mid = (lo, mid)
          | otherwise = (succ mid, hi)
          where mid = (lo + hi) `div` 2

但这感觉就像是在重新发明轮子，而且对于非常大的 Integer 也可以通过利用底层表示的知识来提高效率。

(注意，提供的bitSize function更多是关于数字类型的最大位数，这不是我这里需要的。)

Answer 1

如果你想从 Integral 类型开始，这应该可以做到:

import Math.NumberTheory.Logarithms

bitLength :: Integral a => a -> Int
bitLength n = integerLog2 (fromIntegral n)

在ghci下测试:

 λ> 
 λ> bitLength 64
6
 λ> 
 λ> bitLength 127
6
 λ> 
 λ> bitLength 1
0
 λ> 
 λ> bitLength 0

*** Exception: Math.NumberTheory.Logarithms.integerLog2: argument must be positive
CallStack (from HasCallStack):
  error, called at src/Math/NumberTheory/Logarithms.hs:82:19 in integer-logarithms-1.0.3-L1fXvdNnENnEcLpMml0rI7:Math.NumberTheory.Logarithms
 λ> 

编辑:

关于您的评论，如果函数 bitLength 要名副其实，它必须返回 1-based，而不是从零开始的最高索引设置位。

因此 bitLength 的适当修正版本应该是这样的:

import  Math.NumberTheory.Logarithms  (integerLog2')

bitLength :: Integral a => a -> Int
bitLength n =
    if (n > 0) then (succ . integerLog2' . fromIntegral) $ n
               else  if (n == 0) then 0
                                 else error "bitLength: negative input !"

在ghci下重新测试:

 λ> 
 λ> bitLength 0
0
 λ> bitLength 1
1
 λ> bitLength 2
2
 λ> bitLength 120
7
 λ> bitLength (-1)
*** Exception: bitLength: negative input !
CallStack (from HasCallStack):
  error, called at bitLength.hs:25:39 in main:Main
 λ> 

注意:另一方面，Bits 接口(interface)(类)似乎没有提供一种简单的方法来转换项目hand into an Integer，可能是因为现有的库实例一开始就是Integer。