A surprisingly simple de Bruijn sequence construction

Pick any length nn binary string b1b2⋯bnb1b2⋯bn and remove the first bit b1b1. If b2b3⋯bn1b2b3⋯bn1 is a necklace, then append the complement of b1b1 to the end of the remaining string; otherwise append b1b1. By repeating this process, eventually all 2n2n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)O(1)-amortized time per bit.