# Minimum Bit Flips to Convert Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-bit-flips-to-convert-number)
Canonical: https://scaleengineer.com/dsa/problems/minimum-bit-flips-to-convert-number
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [persistent systems](https://scaleengineer.com/companies/persistent-systems)
---
## Problem
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 is `111` 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 `110`, flip the second bit from the right to get `101`, flip the fifth bit from the right (a leading zero) to get `10111`, 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 <= 109`

**Note:** This question is the same as [461: Hamming Distance.](https://leetcode.com/problems/hamming-distance/description/)

# Approaches
## Brute Force using String Conversion
This approach first calculates the bitwise XOR of `start` and `goal`. The result of this operation is a number where each set bit (1) represents a position where the original numbers' bits differ. The problem then becomes counting the set bits in this new number. This approach converts the number to its binary string representation and then iterates through the string to count the occurrences of the character '1'.
**Time:** O(log N), where N is the value of `start ^ goal`. The time is dominated by converting the number to a string and iterating over it, and the length of the binary string is proportional to `log N`. · **Space:** O(log N), where N is the value of `start ^ goal`. This space is required to store the binary string representation.
**Pros:** Conceptually simple and easy to understand for beginners.; Leverages built-in string conversion, making the initial implementation straightforward.
**Cons:** Inefficient in terms of both time and space due to the creation of an intermediate string.; String operations are generally slower than bitwise manipulations.
### Explanation
The fundamental insight is that the minimum number of bit flips to convert `start` to `goal` is equal to the number of positions at which their binary representations differ. The bitwise XOR operation (`^`) is perfect for this, as `start ^ goal` produces a number where a bit is set to 1 if and only if the corresponding bits in `start` and `goal` were different.

This approach proceeds as follows:
1.  Compute `int xorResult = start ^ goal;`.
2.  Convert `xorResult` to a binary string: `String binaryString = Integer.toBinaryString(xorResult);`.
3.  Iterate through this string and count the number of '1's. This count is the number of differing bits, which is our answer.

```java
class Solution {
    public int minBitFlips(int start, int goal) {
        int xorResult = start ^ goal;
        String binaryString = Integer.toBinaryString(xorResult);
        int flips = 0;
        for (char c : binaryString.toCharArray()) {
            if (c == '1') {
                flips++;
            }
        }
        return flips;
    }
}
```
### Algorithm
- Calculate `xorResult = start ^ goal`.
- Convert `xorResult` to its binary string representation.
- Initialize a counter `flips = 0`.
- Iterate through each character of the binary string.
- If a character is '1', increment the `flips` counter.
- Return `flips`.

## Iterative Bitwise Check
This method avoids the overhead of string conversion by directly working with the bits of the number. After calculating the XOR of `start` and `goal`, it iteratively checks each bit of the result. A loop runs until the number becomes zero, and in each step, it checks the least significant bit (LSB) and then right-shifts the number to process the next bit.
**Time:** O(k), where `k` is the number of bits in an integer (e.g., 32). The loop runs `k` times in the worst case for a `k`-bit integer. · **Space:** O(1), as it only uses a few variables for calculation, regardless of the input size.
**Pros:** More efficient than the string conversion method as it avoids creating intermediate data structures.; Operates directly on bits, which is generally faster.; Constant space complexity.
**Cons:** The number of iterations is proportional to the total number of bits in the integer type (e.g., 32), not the actual number of set bits. It will always loop about 32 times for a large number, even if only one bit needs to be flipped.
### Explanation
This approach improves upon the string conversion method by eliminating the need for an intermediate string, thus saving space and time. It works by repeatedly checking the last bit of the number and then shifting the bits to the right.

1.  Calculate the XOR result: `int n = start ^ goal;`.
2.  Initialize a counter `flips = 0`.
3.  Use a `while` loop that continues as long as `n` is greater than 0.
4.  Inside the loop, use the bitwise AND operator (`&`) to check if the last bit is a 1: `(n & 1) == 1`. If it is, we increment our `flips` counter.
5.  Right-shift `n` by one bit (`n = n >> 1;`) to discard the last bit and expose the next one.
6.  The loop terminates when all bits have been shifted out and `n` becomes 0.

```java
class Solution {
    public int minBitFlips(int start, int goal) {
        int n = start ^ goal;
        int flips = 0;
        while (n > 0) {
            // Add the last bit to the count
            flips += (n & 1);
            // Right shift to check the next bit
            n = n >> 1;
        }
        return flips;
    }
}
```
### Algorithm
- Calculate `n = start ^ goal`.
- Initialize `flips = 0`.
- Loop while `n > 0`:
  - Check the least significant bit (LSB) of `n` using `(n & 1)`.
  - If the LSB is 1, increment `flips`.
  - Right-shift `n` by one position to process the next bit (`n = n >> 1`).
- Return `flips`.

## Optimized Bit Counting (Brian Kernighan's Algorithm)
This is a clever optimization over the simple iterative approach, known as Brian Kernighan's algorithm. Instead of checking every single bit, this algorithm repeatedly finds and removes the rightmost set bit. The number of times this operation can be performed is exactly equal to the number of set bits. This significantly reduces the number of loop iterations if the number of set bits is small.
**Time:** O(m), where `m` is the number of set bits (i.e., differing bits). In the worst case, this is `O(k)` where `k` is the total number of bits, but it's much faster on average. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Highly efficient. The number of loop iterations is equal to the number of set bits, not the total number of bits.; Constant space complexity.; Significantly faster than the previous approaches when the number of differing bits is small.
**Cons:** The logic `n & (n - 1)` might be less intuitive for beginners compared to a simple bit check and shift.
### Explanation
Brian Kernighan's algorithm provides an efficient way to count set bits. The key insight is that for any number `n`, the operation `n & (n - 1)` unsets the rightmost set bit of `n`. By repeatedly applying this operation and counting how many times we can do it before the number becomes 0, we can find the total number of set bits.

1.  Calculate the XOR result: `int n = start ^ goal;`.
2.  Initialize a counter `flips = 0`.
3.  Use a `while` loop that continues as long as `n` is not zero.
4.  Inside the loop, we increment `flips` and then update `n` with `n & (n - 1)`.
5.  The loop will execute exactly as many times as there are set bits in the initial `n`.

```java
class Solution {
    public int minBitFlips(int start, int goal) {
        int n = start ^ goal;
        int flips = 0;
        while (n > 0) {
            // This operation removes the rightmost set bit
            n = n & (n - 1);
            flips++;
        }
        return flips;
    }
}
```
### Algorithm
- Calculate `n = start ^ goal`.
- Initialize `flips = 0`.
- Loop while `n > 0`:
  - Apply the operation `n = n & (n - 1)`. This unsets the rightmost '1' bit.
  - Increment `flips`.
- Return `flips`.

## Using Built-in Function
The most efficient and simplest approach is to use the language's built-in function for counting set bits (also known as population count or Hamming weight). These functions are typically implemented using highly optimized machine code instructions, making them extremely fast.
**Time:** O(1). The `Integer.bitCount` method is often mapped to a hardware instruction which takes a constant number of cycles. · **Space:** O(1).
**Pros:** The most efficient method, often implemented using a single CPU instruction (like POPCNT).; Extremely concise and readable code.; Guaranteed to be correct and highly optimized by the platform.
**Cons:** Abstracts away the underlying bit manipulation logic, which might not be ideal for learning purposes or in environments where such functions are not available.
### Explanation
Modern programming languages and hardware provide optimized ways to perform common bitwise operations. Counting the number of set bits is one such operation. In Java, the `Integer` wrapper class provides the `bitCount()` static method for this purpose.

The solution becomes a one-liner:
1.  Calculate the bitwise XOR of `start` and `goal` to get a number representing the differing bits.
2.  Pass this result to `Integer.bitCount()`.
3.  Return the value.

This approach is not only the most performant but also the most readable and least error-prone.

```java
class Solution {
    public int minBitFlips(int start, int goal) {
        // 1. XOR finds the bits that are different.
        // 2. bitCount counts the number of set bits (1s).
        return Integer.bitCount(start ^ goal);
    }
}
```
### Algorithm
- Calculate `n = start ^ goal`.
- Return the result of a built-in function to count set bits in `n` (e.g., `Integer.bitCount(n)` in Java).

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number} start * @param {number} goal * @return {number} */ var minBitFlips =
  function (start, goal) {
    return bitCount(start ^ goal);
  };
function bitCount(i) {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}

```

### CPP

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

```

### Python

```python
class Solution:
    def minBitFlips(self, start: int, goal: int) -> int: t = start ^ goal ans = 0 while t: ans += t & 1 t >>= 1 return ans

```