Basic idea:

- Every time we just cross off all the numbers with
`0 or 1`

at the`i-th`

bit under binary representation. - We just need to determine whether it's 0 or 1.

Example:`n=9=(1001)`

First iteration:`2, 4, 6, 8`

All the remaining numbers has`0`

at the least significant bit under binary representation

Second iteration:`2, 6`

All the remaining numbers has`1`

at the second least significant bit under binary representation

... - How to determine whether it's 0 or 1? Has something todo with:

`(i)`

whether we know all the numbers remaining has a common`1`

in some bits -- correspond to`pos`

in my solution

`(ii)`

whether we're crossing off numbers from the beginning or the end -- correspond to`flip`

in my solution

```
class Solution {
public:
int lastRemaining(int n) {
int ans = 0;
int flip = 0;
int power = 1;
while (n > 1) {
int pos = (ans > 0);
int tmp = n & 1;
ans |= (((1 ^ tmp) & flip) ^ pos) * power;
n >>= 1;
power <<= 1;
flip ^= 1;
}
if (!ans)
ans |= power;
return ans;
}
};
```