minimum-bit-flips-to-convert-number

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A bit flip of a number <code>x</code> is choosing a bit in the binary representation of <code>x</code> and flipping it from either <code>0</code> to <code>1</code> or <code>1</code> to <code>0</code>.

<ul>
	<li>For example, for <code>x = 7</code>, the binary representation is <code>111</code> and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get <code>110</code>, flip the second bit from the right to get <code>101</code>, flip the fifth bit from the right (a leading zero) to get <code>10111</code>, etc.</li>
</ul>

Given two integers <code>start</code> and <code>goal</code>, return the minimum number of bit flips to convert <code>start</code> to <code>goal</code>.

&nbsp;
Example 1:

<pre>
Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -&gt; 1011.
- Flip the third bit from the right: 1011 -&gt; 1111.
- Flip the fourth bit from the right: 1111 -&gt; 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.</pre>

Example 2:

<pre>
Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
- Flip the first bit from the right: 011 -&gt; 010.
- Flip the second bit from the right: 010 -&gt; 000.
- Flip the third bit from the right: 000 -&gt; 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= start, goal &lt;= 109</code></li>
</ul>

&nbsp;
Note: This question is the same as <a href="https://leetcode.com/problems/hamming-distance/description/" target="_blank">461: Hamming Distance.</a>

minBitFlips

Minimum Bit Flips to Convert Number

Minimum Flips to Make a OR b Equal to c

minimum-flips-to-make-a-or-b-equal-to-c

或运算的最小翻转次数

Minimum Number of Operations to Make Array XOR Equal to K

minimum-number-of-operations-to-make-array-xor-equal-to-k

使数组异或和等于 K 的最少操作次数

Smallest Number With All Set Bits

smallest-number-with-all-set-bits

仅含置位位的最小整数

Bit Manipulation

一次 位翻转&nbsp;定义为将数字&nbsp;<code>x</code>&nbsp;二进制中的一个位进行 翻转&nbsp;操作，即将&nbsp;<code>0</code>&nbsp;变成&nbsp;<code>1</code>&nbsp;，或者将&nbsp;<code>1</code>&nbsp;变成&nbsp;<code>0</code>&nbsp;。

<ul>
	<li>比方说，<code>x = 7</code>&nbsp;，二进制表示为&nbsp;<code>111</code>&nbsp;，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到&nbsp;<code>110</code>&nbsp;，或者翻转右边起第二位得到&nbsp;<code>101</code>&nbsp;，或者翻转右边起第五位（这一位是前导 0 ）得到&nbsp;<code>10111</code>&nbsp;等等。</li>
</ul>

给你两个整数&nbsp;<code>start</code> 和&nbsp;<code>goal</code>&nbsp;，请你返回将&nbsp;<code>start</code>&nbsp;转变成&nbsp;<code>goal</code>&nbsp;的&nbsp;最少位翻转&nbsp;次数。

&nbsp;

示例 1：

<pre>
输入：start = 10, goal = 7
输出：3
解释：10 和 7 的二进制表示分别为 1010 和 0111 。我们可以通过 3 步将 10 转变成 7 ：
- 翻转右边起第一位得到：1010 -&gt; 1011 。
- 翻转右边起第三位：1011 -&gt; 1111 。
- 翻转右边起第四位：1111 -&gt; 0111 。
我们无法在 3 步内将 10 转变成 7 。所以我们返回 3 。</pre>

示例 2：

<pre>
输入：start = 3, goal = 4
输出：3
解释：3 和 4 的二进制表示分别为 011 和 100 。我们可以通过 3 步将 3 转变成 4 ：
- 翻转右边起第一位：011 -&gt; 010 。
- 翻转右边起第二位：010 -&gt; 000 。
- 翻转右边起第三位：000 -&gt; 100 。
我们无法在 3 步内将 3 变成 4 。所以我们返回 3 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>0 &lt;= start, goal &lt;= 109</code></li>
</ul>

&nbsp;

注意：本题与&nbsp;<a href="https://leetcode.cn/problems/hamming-distance/">461. 汉明距离</a>&nbsp;相同。