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。
約束：
提示：
- 如果開始和目標中某個位元的值不同，那麼我們需要翻轉該位元。
- 考慮使用 XOR 運算來決定哪些位元需要進行位元翻轉。
解：
我們需要確定開始和目標之間有多少位位置不同。這可以使用 XOR 運算 (^) 輕鬆實現，該運算為兩個數字不同的每個位元位置傳回 1。
步驟：
- 在開始和目標之間執行異或運算。結果將是一個在開始和目標不同的位置都有 1 的數字。
- 計算結果的二進位表示中有多少個 1（即漢明距離）。
- 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
?>
登入後複製
解釋：
- ^（XOR）運算比較開始和目標的每一位。如果位不同，結果中對應的位元將為 1。
- 然後我們計算結果中 1 的數量，這給出了不同位的數量，即所需的位元翻轉次數。
- &1 操作檢查最後一位是否為 1，>>= 1 將數字右移以處理下一位。
時間複雜度：
- 時間複雜度為 (O(log N))，其中 (N) 是開始或目標中較大的一個，因為我們要檢查數字的每一位。在最壞的情況下，我們將循環遍歷 32 位元整數的所有位元（因為 PHP 5.6 根據系統使用 32 位元或 64 位元整數）。
輸出：
- 對於開始 = 10 和目標 = 7，輸出為 3。
- 對於開始 = 3 和目標 = 4，輸出為 3。
聯絡連結
如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！
如果您想要更多類似的有用內容，請隨時關注我：
以上是轉換數字的最少位元翻轉的詳細內容。更多資訊請關注PHP中文網其他相關文章！
