Как проверить, является ли число степенью 2? - PullRequest
Новая
       17

Как проверить, является ли число степенью 2?

4 голосов
/ 21 октября 2019

Я хочу провести простой тест на предмет того, является ли число степенью 2 в Haskell для охранника, который я делаю.

Цель состоит в том, чтобы определить, является ли число четным (а не степенным). из 2), является ли число нечетным, или является ли число степенью 2.

Я хочу сделать что-то вроде: 

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

Я смотрел на некоторые темы, новсе они говорят, что нужно использовать побитовый оператор: 

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

Однако он говорит

Недопустимо: '&'

, когда я пытаюсьсделайте это, поэтому я не уверен, разрешено ли это в Haskell.

Ответы [ 2 ]

10 голосов
/ 21 октября 2019

Haskell имеет побитовые операции, но они имеют немного другое имя. Действительно, вы можете сделать побитовое И с помощью функции (.&.) :: Bits a => a -> a -> a.

Таким образом, вы можете выполнить такую ​​проверку с помощью: 

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

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

Обратите внимание, что предложенное вами решение также будет содержать ноль в виде степени двойки. Действительно, если мы оценим первые 1 000 чисел, мы получим: 

Prelude Data.Bits> filter isPower2 [0 .. 1000]
[0,1,2,4,8,16,32,64,128,256,512]
2 голосов
/ 21 октября 2019

Еще один способ сделать это - использовать функцию 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

Редактировать: OK, прежде чем оценивать код, давайте получим математику. за этим. Идея проста. Любое число, которое может быть выражено как степень двух, означает, что его логарифм по отношению к основанию 2 (logBase 2) является целым числом.

Соответственно, мы будем использовать функцию logBase 2. Если мы проверим его тип 

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

, мы увидим, что входной номер должен быть членом класса типа Floating. Функция logBase 2 состоит из предыдущей функции; 

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

Теперь, если мы забудем о аппликативном операторе <*>, это можно перефразировать как 

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

Теперь, еслимы проверяем тип round function 

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

и видим, что входные данные также должны быть членами класса RealFrac, следовательно, ограничение (RealFrac b, Floating b) => в объявлении типа isPotfunction.

Теперь, что касается аппликативного оператора <*>, на самом деле это очень удобно, когда у вас есть двухпараметрическая функция, такая как (==), и вам нужно подать влево (первый параметр) с помощью x и вправо с g x. Другими словами f <*> g = \x -> f x (g x). Подпись типа <*>: 

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

Я бы посоветовал вам прочитать Функторы, Аппликативные Функторы и Моноиды часть книги «Изучите вас на Хаскеле».

...