main.cpp

class Solution {
   public:
    int minimumOneBitOperations(int n) {
        // 0: 000 : 2^0 - 1
        // 1: 001 -> 000 : 2^1 - 1 = 1
        // 2: 010 -> 011 -> 001 -> 000 : 2^2 - 1 = 3
        // 3: 011 -> 001 -> 000
        // 4: 100 -> 101 -> 111 -> 110 -> 010 -> 011 -> 001 -> 000 : 2^3 - 1 = 7
        //     4      5      7      6      2      3      1      0 
        // 5: 101 -> 111 -> 110 -> 010 -> 011 -> 001 -> 000 : - 1 + 7
        // 6: 110 -> 010 -> 011 -> 001 -> 000 : - 3 + 7
        // 7: 111 -> 110 -> 010 -> 011 -> 001 -> 000 : 1 - 3 + 7
        // 8: 1000 -> 1001 -> 1011 -> 1010 -> 1110 -> 1111 -> 1101 -> 1100 -> 0100 : 2^4 - 1 = 15
        //       8       9      11      10      14      15      13      12       4
        // 9 : 15 - 1 = 14
        // 10: 15 + 1 - 3 = 13

        int sign = 1;
        int b = 2;
        int result = 0;
        while (n > 0) {
            if (n & 1) {
                result += sign * (b - 1);
                sign = -sign;
            }
            b <<= 1;
            n >>= 1;
        }

        return sign < 0 ? result : -result;
    }
};