Return to Blog entry

- O(log n) memory, O(log n) time algorithm Alexey Romanov 3rd November, 2008 14:25 (UTC)
Start with 1, double it and compare with n until you find a power of 2 greater than n. This is O(log n). Now you have the list of all powers of 2 which are less than n, so you can get the binary digits of n by the simple greedy algorithm. This is O(log n). If the last digit is 1, n is odd, otherwise n is even.

In Haskell:

`powersOf2 n list@(x:xs) | n > x = powersOf2 n (x*2 : list) | otherwise = list reduce n [] = n reduce n (x:xs) | n >= x = reduce (n - x) xs | otherwise = reduce n xs isOdd n = reduce n (powersOf2 n [2]) == 1`

**Edit by Kirit**: Edited to add formatting to source code

kirit.com