时间戳

首页 > 解决方案 > 在haskell中查找整数的位长

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

问题描述

我想在 Haskell 中找到一种类型的位长（即最高设置位的索引） - 就像Java或PythonIntegral中的相应方法一样。

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

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通过利用底层表示的知识，对于非常大的 s 也可能更有效。

（注意，提供的bitSize 函数更多的是关于数字类型中的最大位数，这不是我这里需要的。）

标签： haskell

解决方案

如果你想从一个 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 的索引，而不是最高设置位的从零开始的索引。

所以一个适当更正的版本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接口（class）似乎没有提供将手头的项目转换为 的简单方法Integer，可能是因为现有的库实例Integral要开始。

推荐阅读