Generating Powers of 2 mod n

Time: :

2r-1, 2r-2,...,23,22, 21 where r is the order* of 2 mod n =

Given the following relation:
a1 = (n+1)/2        given an odd n  
ai = ai-1/2              if ai-1 is even
ai = (ai-1-1)/2 + a1 if ai-1 is odd

* The order of 2 mod n is the smallest integer r such that 2r = 1 mod n