Return to Blog entry
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.
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 ) == 1
Edit by Kirit: Edited to add formatting to source code