Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2220.html
2220. Minimum Bit Flips to Convert Number (Easy)
A bit flip of a number x
is choosing a bit in the binary representation of x
and flipping it from either 0
to 1
or 1
to 0
.
 For example, for
x = 7
, the binary representation is111
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 get110
, flip the second bit from the right to get101
, flip the fifth bit from the right (a leading zero) to get10111
, etc.
Given two integers start
and goal
, return the minimum number of bit flips to convert start
to goal
.
Example 1:
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 > 1011.  Flip the third bit from the right: 1011 > 1111.  Flip the fourth bit from the right: 1111 > 0111. It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.
Example 2:
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 > 010.  Flip the second bit from the right: 010 > 000.  Flip the third bit from the right: 000 > 100. It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.
Constraints:
0 <= start, goal <= 10^{9}
Similar Questions:
Solution 1.
XOR sets the bits that are different between start
and goal
, and unsets bits that are the same.
__builtin_popcount(mask)
counts the 1
s in mask
.
Example:
Expression  Value
Welcome to Subscribe On Youtube
–
start 0011010
goal 0101100
start^goal 0110110
__builtin_popcount(start^goal)  4

// OJ: https://leetcode.com/problems/minimumbitflipstoconvertnumber/ // Time: O(1) // Space: O(1) class Solution { public: int minBitFlips(int start, int goal) { return __builtin_popcount(start ^ goal); } };

class Solution: def minBitFlips(self, start: int, goal: int) > int: t = start ^ goal ans = 0 while t: ans += t & 1 t >>= 1 return ans ############ # 2220. Minimum Bit Flips to Convert Number # https://leetcode.com/problems/minimumbitflipstoconvertnumber/ class Solution: def minBitFlips(self, start: int, goal: int) > int: a = start ^ goal count = 0 while a: count += a & 1 a >>= 1 return count

class Solution { public int minBitFlips(int start, int goal) { int t = start ^ goal; int ans = 0; while (t != 0) { ans += t & 1; t >>= 1; } return ans; } }

func minBitFlips(start int, goal int) int { t := start ^ goal ans := 0 for t != 0 { ans += t & 1 t >>= 1 } return ans }

function minBitFlips(start: number, goal: number): number { let tmp = start ^ goal; let ans = 0; while (tmp !== 0) { ans += tmp & 1; tmp >>= 1; } return ans; }

impl Solution { pub fn min_bit_flips(start: i32, goal: i32) > i32 { let mut tmp = start ^ goal; let mut ans = 0; while tmp != 0 { ans += tmp & 1; tmp >>= 1; } ans } }
Discuss
https://leetcode.com/problems/minimumbitflipstoconvertnumber/discuss/1907384/