| 112 | } |
| 113 | |
| 114 | std::string DeBruijnString(int n) { |
| 115 | CHECK_GE(n, 1); |
| 116 | CHECK_LE(n, 29); |
| 117 | const size_t size = size_t{1} << static_cast<size_t>(n); |
| 118 | const size_t mask = size - 1; |
| 119 | std::vector<bool> did(size, false); |
| 120 | std::string s; |
| 121 | s.reserve(static_cast<size_t>(n) + size); |
| 122 | for (size_t i = 0; i < static_cast<size_t>(n - 1); i++) |
| 123 | s += '0'; |
| 124 | size_t bits = 0; |
| 125 | for (size_t i = 0; i < size; i++) { |
| 126 | bits <<= 1; |
| 127 | bits &= mask; |
| 128 | if (!did[bits | 1]) { |
| 129 | bits |= 1; |
| 130 | s += '1'; |
| 131 | } else { |
| 132 | s += '0'; |
| 133 | } |
| 134 | CHECK(!did[bits]); |
| 135 | did[bits] = true; |
| 136 | } |
| 137 | CHECK_EQ(s.size(), static_cast<size_t>(n - 1) + size); |
| 138 | return s; |
| 139 | } |
| 140 | |
| 141 | } // namespace re2 |