We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Bit Flips to Convert Number

Number: 2323

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Microsoft, persistent systems

Problem Description

Given two integers start and goal, determine the minimum number of bit flips required to convert start into goal. A bit flip involves changing a single bit from 0 to 1 or from 1 to 0. This problem is equivalent to computing the Hamming distance between the binary representations of start and goal.

Key Insights

  • Use the XOR operation on start and goal to get a number whose set bits (1's) represent the positions where start and goal differ.
  • Count the number of set bits in the result which directly gives the minimum number of bit flips needed.
  • This technique efficiently computes the answer in O(n) time where n is the number of bits, given that start and goal are bounded by 10^9, n is at most 32.

Space and Time Complexity

Time Complexity: O(1) - constant time with respect to the size of integers since the number of bits is fixed (e.g., 32 bits). Space Complexity: O(1) - uses a constant amount of additional space.

Solution

The solution leverages bit manipulation:

  1. Compute the XOR of start and goal. This operation highlights all the bits that differ between the two numbers.
  2. Iterate through the bits of the XOR result and count the number of set bits.
  3. The count obtained is equal to the minimum number of bit flips required.

Data Structures and Algorithms:

  • Bitwise XOR: To detect differing bits.
  • Bit counting: Can be performed using a loop and bit shifting, or utilizing built-in functions if available.

Key Trick:

  • Using XOR directly transforms the problem into counting the number of ones (the Hamming distance), which is much simpler and more efficient than comparing bit by bit manually.

Code Solutions

# Function to count the number of bit flips between start and goal
def min_bit_flips(start, goal):
    # Calculate XOR of start and goal to highlight differing bits
    xor_result = start ^ goal
    bit_flip_count = 0
    
    # Count the number of 1 bits in xor_result
    while xor_result:
        # Check if the lowest bit is 1; if so, increment the count
        bit_flip_count += xor_result & 1
        # Shift right by 1 to process the next bit
        xor_result >>= 1
    return bit_flip_count

# Example usage:
print(min_bit_flips(10, 7))  # Expected output: 3
print(min_bit_flips(3, 4))   # Expected output: 3
← Back to All Questions