WOw I think this is the optimal solution!

Let me explain the core idea:

We traverse from right to left, before you met the next bit that is 0, you should met Even number of 1s!

The rest part after the next bit of 0 are always valid:)

And we have assumption that the input always has bits[n-1] = 0:)