Vultr DocsLatest Content

Minimum Bit Flips to Convert Number

Updated on 16 June, 2025
Minimum Bit Flips to Convert Number header image

Problem Statement

In computer science, operations on binary representations of numbers are quite common due to their efficiency and direct hardware interaction. A particular operation of interest is the bit flip, where a bit within the binary representation of a number x is switched from 0 to 1 or vice versa. For example, for a number represented as 111 in binary (which is 7 in decimal), flipping any of its bits or potentially an extra leading zero can result in numbers like 110, 101, or 10111.

Given two integers start and goal, the task is to determine the minimum number of bit flips required to transform the binary representation of start into that of goal. This problem is a computer science-centric challenge that delves into bit manipulation and binary arithmetic, offering insight into low-level data manipulation and optimization techniques.

Examples

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

Approach and Intuition

The task revolves around converting the binary form of one number to another through the simplest operations - bit flips. Here’s the intuition and steps involved in crafting a solution:

  1. XOR Operation: Use the XOR bitwise operation between start and goal. The XOR operation (^) between two bits returns 1 if the bits are different, otherwise 0. Therefore, applying this operation between start and goal will highlight (with a 1) all positions where the bits of start and goal differ.

  2. Count the 1s: Since each 1 in the result of the XOR operation represents a bit that needs to be flipped (from 0 to 1 or 1 to 0), counting the number of 1s gives the minimum flips required.

Highlights from Examples

  • Example 1 (start = 10, goal = 7): The binary forms are 1010 and 0111. The XOR result is 1101, indicating three differences (three 1s). Thus, three flips are required - flip the fourth (leading) bit, then the third, then the first from the right.

  • Example 2 (start = 3, goal = 4): The binaries are 011 and 100. The XOR result is 111, indicating all bits are different. Three flips are thus needed: one at each position from right to left.

This approach, driven by the bit-level manipulation concept, utilizes the efficiency of XOR operations to derive the number of differing bits efficiently, offering a direct route to calculating the answer. This method, thanks to its O(1) complexity regarding the bit-length of the numbers (since they are fixed by the constraints to maximum 30 bits), is both optimal and elegant.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int countFlips(int initial, int target) {
        int result = initial ^ target;
        int flipsCount = 0;
        while (result) {
            result &= (result - 1);
            flipsCount++;
        }
        return flipsCount;
    }
};

This C++ solution is designed to compute the minimum number of bit flips required to convert an initial integer to a target integer. The function countFlips takes two integers, initial and target, as input.

  • To find which bits are different between the two integers, perform a bitwise XOR operation between initial and target. This operation will set the bits that are different between the two numbers to 1.
  • Initialize flipsCount to zero. This variable will keep track of the number of flips required.
  • Employ a while loop to iterate as long as result is non-zero. In each iteration:
    • Apply the bitwise AND operation between result and result - 1. This operation turns off the lowest set bit of result, effectively counting that flip.
    • Increment flipsCount by one.
  • Once all differing bits are counted (i.e., when result is zero), return flipsCount as the minimum number of bit flips necessary to transform the initial number to the target number.

This approach efficiently counts the differing bits using a common technique that exploits properties of binary numbers, ensuring a solution that runs in a time complexity proportional to the number of differing bits, rather than the total number of bits in the numbers.

java 
class Solution {

    public int countMinFlips(int init, int target) {
        int diffBits = init ^ target;
        int flips = 0;
        while (diffBits != 0) {
            diffBits &= (diffBits - 1); // Remove the lowest set bit
            flips++;
        }
        return flips;
    }
}

The provided Java program solves the problem of finding the minimum number of bit flips required to convert an initial integer (init) to a target integer (target). The solution utilizes bitwise operations to efficiently determine the number of bit flips. Here's a concise breakdown of how the solution works:

  • Calculate the difference in bits between init and target using the XOR operation (^). Any differing bits between the two numbers will be set to 1 in the resultant diffBits.
  • Initialize a counter flips at zero to count the number of flips.
  • Use a while loop to count the number of set bits (bits that are 1) in diffBits. For each iteration:
    • Perform a bitwise AND between diffBits and diffBits - 1. This operation turns off the least significant set bit in diffBits.
    • Increment the flips counter as each set bit corresponds to a necessary flip.
  • Continue this process until all set bits are turned off (i.e., diffBits becomes 0).
  • Return the flips counter, which now contains the minimum number of flips required.

This method is both time-efficient and straightforward, leveraging bit manipulation to minimize computational overhead.

python 
class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        # Determine bits that differ
        different_bits = start ^ goal
        flips = 0
        # Efficient count of bits set to 1
        while different_bits:
            different_bits &= different_bits - 1  # Remove the least significant bit one by one
            flips += 1
        return flips

The provided Python solution aims to find the minimum number of bit flips needed to convert a binary representation of one number (start) to another (goal). The solution leverages bitwise XOR to identify which bits differ between the two numbers. The operation start ^ goal results in a binary number where every bit that is set to 1 represents a differing bit that needs to be flipped.

To count the number of 1s (which correspond to the flips needed), the solution then utilizes a loop to iteratively remove the least significant bit set to 1 using the operation different_bits &= different_bits - 1. Each iteration of this loop corresponds to a single flip, and hence increments a flips counter.

  • The binary XOR operation identifies differing bits.
  • A while-loop with the bitwise operation efficiently counts the bits, giving the number of flips.

This approach ensures an optimal solution using bit manipulation, providing an efficient way to calculate the result with a minimized number of operations.

Comments

No comments yet.