Haskell如何筛选指定区间内指数为奇数的2的幂值

实现方案 #

你需要筛选的是满足 2^k 且k为奇数的数值，可直接基于原有逻辑扩展位运算判断，完整实现如下：

import Data.Bits(Bits, (.&.))

isPower2OddExponent :: (Bits i, Integral i) => i -> Bool
isPower2OddExponent n = n > 1 && isPower2 n && n .&. 0xAAAAAAAA == n
  where
    isPower2 n = n .&. (n - 1) == 0

逻辑说明

• 首先通过 n>1 排除0和1：0不是2的正整数次幂，1对应2^0，指数0为偶数，都不符合要求
• 保留原有isPower2逻辑判断数值是否为2的幂
• 新增的n .&. 0xAAAAAAAA == n利用位运算特性判断指数是否为奇数：0xAAAAAAAA的二进制为10101010...，所有奇数位（从0开始计数）为1，指数为奇数的2的幂的二进制1正好落在奇数位，按位与后结果等于自身。

测试效果

执行filter isPower2OddExponent [0 .. 1000]，输出结果为[2,8,32,128,512]，完全符合你的预期。

如果需要兼容任意位数的整数类型，不想用固定掩码，也可以用递归移位的方式实现：

import Data.Bits(Bits, (.&.), shiftR)

isPower2OddExponent :: (Bits i, Integral i) => i -> Bool
isPower2OddExponent n
  | n <= 1 = False
  | n == 2 = True
  | otherwise = isPower2OddExponent (shiftR n 2)

该实现每次将数值右移2位（等价于除以4），最终如果能得到2就说明指数为奇数。

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