Gray code

今天練習的題目是 1611. Minimum One Bit Operations to Make Integers Zero，後來自己想出解法後去看官方解答才發現是在考 Gray code 的轉換。

我自己列出 16 轉換到 0 的所有 bits 的表現方式，然後仔細觀察後發現有某種規律，於是就猜想了一個方程式出來試試看，結果還真的可以解答，先聲明一下這不是最有效的方法，只是眾多解法中的其中一種而已。

設 $p_1, p_2, \dots, p_j$ 為 $n$ 的二進位中所有 1 的 0-based 索引，且 $p_1 > p_2 > \dots > p_j$ ($p_1$ 是 MSB)。
$$f(n) = \sum_{i=1}^{j} (-1)^{i-1} \cdot (2^{p_i+1} - 1)$$

這是我初始第一個版本

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0)
            return 0;
        int k = 32 - __builtin_clz(n);
        int ans = 0;
        bitset<30> arr(n);
        int sign = 1;
        for (int i = k; i > 0; --i) {
            if (arr[i - 1]) {
                ans += sign * ((1 << i) - 1);
                sign *= -1;
            }
        }
        return ans;
    }
};

簡化後的第二個版本

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0)
            return 0;
        int k = 32 - __builtin_clz(n);
        int ans = 0;
        int sign = 1;
        for (int i = k; i > 0; --i) {
            if (n & (1 << (i - 1))) {
                ans += sign * ((1 << i) - 1);
                sign *= -1;
            }
        }
        return ans;
    }
};

再進一步簡化後的第三個版本

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0)
            return 0;
        int ans = 0;
        int sign = 1;
        while (n) {
            int k = 32 - __builtin_clz(n);
            ans += sign * ((1 << k) - 1);
            sign *= -1;
            n ^= (1 << (k-1));
        }
        return ans;
    }
};

有用 Gemini AI 幫忙寫了一份解答分享在 LeetCode 上面 Using a Math Formula 這樣