MinimumBitFlipsToConvertNumber2220.kt

package 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 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
 */
fun minBitFlips(start: Int, goal: Int): Int {
    var xor = start.xor(goal)
    var count = 0
    while (xor != 0) {
        xor = xor.and(xor - 1)
        count++
    }
    return count
}

/**
 * Brute force solution
 *
 * Algorithm
 * Initialize a counter count to keep track of the number of bit flips needed.
 *
 * Loop while either start or goal has bits left to check:
 *
 * Compare the least significant bits (rightmost bits) of start and goal:
 * Use the bitwise AND operation (& 1) to isolate the least significant bit of each number.
 * If the bits differ ((start & 1) != (goal & 1)), increment the count by 1.
 * Right shift both start and goal by one position (>>= 1) to move to the next bit.
 * Return the total count after all bits have been checked.
 */
fun minBitFlipsSol2(start: Int, goal: Int): Int {
// Initialize a counter count to kee[ track of the number of bit flips needed
    var counter = 0
    var s =start
    var g= goal

    // Loop while either start or goal has bits left to check
    while (s > 0 || g > 0) {
        // Increment count if the current bits differ
        if ((s.and(1)) != (g.and(1))) {
            counter++
        }

        // Shift both numbers to the right to check the next bits
        s = s.shr(1)
        g = g.shr(1)
    }
    return counter
}