轉換數字的最少位元翻轉

2220。轉換數字的最少位元翻轉

難度：簡單

主題： 位元操作

數字 x 的位元翻轉是在 x 的二進位表示中選擇一個位，然後翻轉它從 0 到 1 或 1 到 0。

• 例如，forx = 7，二進位表示為111，我們可以選擇任何位元（包括未顯示的任何前導零）並將其翻轉。我們可以翻轉右邊第一位得到 110，翻轉右邊第二位得到 101，翻轉右邊第五位（前導零）得到 10111，等等

給定兩個整數開始和目標，回傳將開始轉換為目標的最小位元翻轉次數。

範例1：

• 輸入：開始 = 10，目標 = 7
• 輸出： 3
• 說明：10和7的二進位表示分別是1010和0111。我們可以透過 3 個步驟將 10 轉換為 7：
  • 從右邊翻轉第一位：1010 -> 1011.
  • 翻轉右邊第三位：1011 -> 1111.
  • 翻轉右邊第四位：1111 -> 0111.
  • 可以證明，我們無法在不到 3 步的時間內將 10 轉換為 7。因此，我們返回 3。

範例2：

• 輸入：開始 = 3，目標 = 4
• 輸出： 3
• 說明：3和4的二進位表示分別是011和100。我們可以透過 3 個步驟將 3 轉換為 4：
  • 從右邊翻轉第一位：011 -> 010.
  • 翻轉右邊第二位：010 -> 000.
  • 翻轉右邊第三位：000 -> 100.
  • 可以證明，我們無法在不到 3 步的時間內將 3 轉換為 4。因此，我們返回 3。

約束：

• 0 9

提示：

1. 如果開始和目標中某個位元的值不同，那麼我們需要翻轉該位元。
2. 考慮使用 XOR 運算來決定哪些位元需要進行位元翻轉。

解：

我們需要確定開始和目標之間有多少位位置不同。這可以使用 XOR 運算 (^) 輕鬆實現，該運算為兩個數字不同的每個位元位置傳回 1。

步驟：

1. 在開始和目標之間執行異或運算。結果將是一個在開始和目標不同的位置都有 1 的數字。
2. 計算結果的二進位表示中有多少個 1（即漢明距離）。
3. 1 的數量將為我們提供所需的最少位元翻轉次數。

讓我們用 PHP 實作這個解：2220。轉換數字的最少位元翻轉

<?php
/**
 * @param Integer $start
 * @param Integer $goal
 * @return Integer
 */
function minBitFlips($start, $goal) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minBitFlips(10, 7);  // Output: 3
echo "\n";
echo minBitFlips(3, 4);   // Output: 3
?>

解釋：

1. ^（XOR）運算比較開始和目標的每一位。如果位不同，結果中對應的位元將為 1。
2. 然後我們計算結果中 1 的數量，這給出了不同位的數量，即所需的位元翻轉次數。
3. &1 操作檢查最後一位是否為 1，>>= 1 將數字右移以處理下一位。

時間複雜度：

• 時間複雜度為 (O(log N))，其中 (N) 是開始或目標中較大的一個，因為我們要檢查數字的每一位。在最壞的情況下，我們將循環遍歷 32 位元整數的所有位元（因為 PHP 5.6 根據系統使用 32 位元或 64 位元整數）。

輸出：

• 對於開始 = 10 和目標 = 7，輸出為 3。
• 對於開始 = 3 和目標 = 4，輸出為 3。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是轉換數字的最少位元翻轉的詳細內容。更多資訊請關注PHP中文網其他相關文章！