转换数字的最少位翻转

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中文网其他相关文章！