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

user_12069869 0
Viewed 1187

I want to do a simple test for if a number is a power of 2 in Haskell for a case guard I am making.

The purpose is to determine whether a number is even (and not a power of 2), whether a number is odd, or whether a number is to the power of 2.

I want to do something like:

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

I have looked at some threads but they all say to use the bitwise operator: 

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

However it says

Not in scope: ‘&’

when I try to do so, so am not sure if that is allowed in Haskell.

bitwise-operators haskell
2 Answers

Haskell has bitwise operations, but these have a slightly different name. Indeed, you can make a bitwise AND with the (.&.) :: Bits a => a -> a -> a function.

You thus can make such check with:

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

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

Note that your proposed solution will include zero as a power of two as well. Indeed, if we evaluate the first 1'000 numbers, we get:

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

One other way to do this would be to use the logBase function with base 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

Edit: OK before evaluating the code lets get the math behind it. The idea is simple. Any number which can be expressed as power of two means it's logarithm with respect to base 2 (logBase 2) is a whole number.

Accordingly we will use the logBase 2 function. If we check it's type

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

we see that the input number should be a member of the Floating type class. The logBase 2 function gets composed with the previous function which is;

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

Now if we forget about the applicative operator <*> this can be rephrased as 

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

Now if we check the type of round function

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

we see that the input also needs to be a member of RealFrac type class hence the (RealFrac b, Floating b) => constraint in the type declaration of the isPot function.

Now regarding applicative operator <*>, it's actually very handy when you have a two parameter function such as (==) and need to feed the left (first parameter) with x and right with g x. In other words f <*> g = \x -> f x (g x). The type signature of <*> is

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

I would advise you to read the Functors, Applicative Functors and Monoids part of the Learn You a Haskell book.

user_45432070
Related