# C++ O(log n) non-recursive solution using bitwise operation

• 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;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.