class Solution {
public:
int lastRemaining(int n) {
int tmp = 0x7FFFFFFF;
while(tmp >= n) tmp >>= 1;
return ((n0x55555555)&tmp) + 1;
}
};
Only 3 lines, C++, O(logN)


You can get that solution mentioned at the top by optimizing this solution:
class Solution { public: int lastRemaining(int n) { bool keepSingle = true; unsigned int res = 0; unsigned int mask = 1; while(n != 1) { if((n & 1) == 0) { res += mask * (keepSingle ? 1 : 0); } else { res += mask; } cout << res << " " << n << keepSingle << endl; keepSingle = !keepSingle; mask <<= 1; n >>= 1; } return res + 1; } };
You can optimize it by "vectorization".
So, the vectorized version ofkeepSingle
is 0x55555555. And here is my final solution:class Solution { public: int lastRemaining(int n) { unsigned int res = 0x55555555; unsigned int mask = 0; unsigned int m = n; while(n != 1) { mask <<= 1; mask = 1; n >>= 1; } return ((res  m) & mask) + 1; } };