如何判断一个数是不是2的幂？

Question

我想做一个简单的测试，看看我正在制作的 Haskell 中的数字是否是 2 的幂。

目的是确定一个数是否为偶数（而不是 2 的幂）、一个数是否为奇数或一个数是否为 2 的次方。

我想做类似的事情：

function n
  | n `mod` 2 == 1 = 1
  | if n is to the power of 2 = 2
  | otherwise = 0

我看过一些帖子，但他们都说要使用按位运算符：

(n & (n - 1)) == 0

然而它说

Not in scope: ‘&’

当我尝试这样做时，我不确定 Haskell 是否允许这样做。

Answer 1

Haskell 有按位运算，但它们的名称略有不同。实际上，您可以使用 (.&.) :: Bits a => a -> a -> a 函数进行按位与运算。

因此您可以通过以下方式进行此类检查：

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

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

请注意，您提出的解决方案也将包括零作为 2 的幂。实际上，如果我们评估前 1'000 个数字，我们会得到：

Prelude Data.Bits> filter isPower2 [0 .. 1000]
[0,1,2,4,8,16,32,64,128,256,512]

Answer 2

另一种方法是将 logBase 函数与基数 2.

一起使用

isPot :: (RealFrac b, Floating b) => b -> Bool
isPot = ((==) <*> (fromInteger . round)) . logBase 2

Prelude> isPot 2048
True
Prelude> isPot 1023
False
Prelude> isPot 1
True

编辑： 好的，在评估代码之前让我们先了解一下它背后的数学原理。这个想法很简单。任何可以表示为 2 的幂的数字表示它以 2 为底的对数 (logBase 2) 是一个整数。

因此我们将使用logBase 2函数。如果我们检查它的类型

Prelude> :t logBase 2
logBase 2 :: Floating a => a -> a

我们看到输入的数字应该是 Floating 类型 class 的成员。 logBase 2 函数与前一个函数组成；

(==) <*> (fromInteger . round)

现在如果我们忘记应用运算符 <*> 这可以改写为

\n -> n == (fromInteger. round) n

现在如果我们检查 round 函数的类型

Prelude> :t round
round :: (RealFrac a, Integral b) => a -> b

我们看到输入也需要是 RealFrac 类型 class 的成员，因此 isPot 函数的类型声明中的 (RealFrac b, Floating b) => 约束。

现在关于应用运算符 <*>，当你有一个双参数函数如 (==) 并且需要用 x 和对 g x。换句话说 f <*> g = \x -> f x (g x)。 <*> 的类型签名是

Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

我建议您阅读 Learn You a Haskell 一书的 Functors, Applicative Functors and Monoids 部分。

如何判断一个数是不是2的幂？

How to test if a number is a power of 2?

haskell

bitwise-operators