Haskell实现：求二进制数中连续零的最大个数

嘿，这个问题我之前也琢磨过！在Haskell里计算二进制表示中连续零的最大个数，有几种不同的实现思路，我给你拆解一下：

如果追求代码简洁、容易理解，我们可以先把数字转成二进制字符串，再分割成被1分隔的零片段，最后取最长的片段长度就行。

实现代码需要用到Numeric和Data.List.Split库：

import Numeric (showIntAtBase, intToDigit)
import Data.List.Split (splitOn)

maxConsecutiveZeros :: Integer -> Int
maxConsecutiveZeros n = maximum $ map length $ splitOn "1" $ showIntAtBase 2 intToDigit n ""

原理解释 #

1. showIntAtBase 2 intToDigit n ""：把整数n转换成二进制字符串，比如558745840会变成"100001010011011100100011110000"
2. splitOn "1"：按字符1分割字符串，得到所有连续零的片段（包括空字符串，对应两个相邻的1）
3. map length：计算每个片段的长度，空字符串长度为0
4. maximum：取所有长度中的最大值，就是我们要的结果

测试一下你的例子：maxConsecutiveZeros 558745840会返回4，完全符合预期。

如果追求性能（尤其是处理大数的时候），字符串转换会有额外开销，这时候直接用位运算操作数字本身更高效，而且不需要依赖额外库。

基础递归版本 #

maxConsecutiveZeros :: Integer -> Int
maxConsecutiveZeros 0 = 1  -- 特殊处理0的情况，二进制是单个0
maxConsecutiveZeros n = go 0 0 n
  where
    go currentMax currentZero 0 = currentMax
    go currentMax currentZero n
      | n `mod` 2 == 1 = go (max currentMax currentZero) 0 (n `div` 2)
      | otherwise = go currentMax (currentZero + 1) (n `div` 2)

优化的位运算版本 #

用Haskell的Data.Bits库提供的位运算函数，比div和mod更快：

import Data.Bits (shiftR, testBit)

maxConsecutiveZeros :: Integer -> Int
maxConsecutiveZeros 0 = 1
maxConsecutiveZeros n = go 0 0 n
  where
    go currentMax currentZero 0 = currentMax
    go currentMax currentZero n
      | n `testBit` 0 = go (max currentMax currentZero) 0 (n `shiftR` 1)
      | otherwise = go currentMax (currentZero + 1) (n `shiftR` 1)

原理解释 #

我们用辅助函数go跟踪两个状态：

• currentMax：目前找到的最长连续零个数
• currentZero：当前正在计数的连续零个数

每次循环检查数字的最后一位：

1. 如果最后一位是1：说明当前连续零的计数结束，更新currentMax为当前最大值和currentZero的较大者，然后重置currentZero为0，再把数字右移一位（去掉最后一位）
2. 如果最后一位是0：把currentZero加1，数字右移一位
3. 当数字变成0时，返回currentMax（此时currentZero已经被重置过，因为最后一个有效位是1，末尾的零已经被计数过了）

测试你的例子：maxConsecutiveZeros 558745840会正确返回4；如果输入8（二进制1000），会返回3，完全符合预期。

内容的提问来源于stack exchange，提问作者mathandtic