This algorithm runs in log(n) time, does it not?
Update (an hour or so later): Hmm… in this case, it appears to take 2 lisp programmers to solve this one…. Oh well. That’s what I get for not trying to “break” my code by testing the ambiguous cases…. The only change here is to make the ‘=’ into ‘<=’ and also to rename the local function per Zach’s suggestion:
(defun round-up (number) (labels ((round-iter (n p) (if (<= n (expt 2 p)) (expt 2 p) (round-iter n (+ p 1))))) (round-iter number 0)))
Update (another hour or so later): Here’s Zach’s solution:
(defun round-up (value) (cond ((zerop value) 1) ((zerop (logand value (1- value))) value) (t (expt 2 (integer-length value))))) ***
Update (another hour or so later): Here’s Chuck’s solution:
(defun next-power-of-2 (n) (expt 2 (ceiling (/ (log n) (log 2)))))