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

Question

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.

Answer 1

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]