05.06. Convert Integer

Description

Write a function to determine the number of bits you would need to flip to convert integer A to integer B.

Example1:

 Input: A = 29 (0b11101), B = 15 (0b01111)



 Output: 2

Example2:

 Input: A = 1，B = 2



 Output: 2

Note:

1. -2147483648 <= A, B <= 2147483647

Solutions

Solution 1: Bit Manipulation

We perform a bitwise XOR operation on A and B. The number of $1$s in the result is the number of bits that need to be changed.

The time complexity is $O(\log n)$, where $n$ is the maximum value of A and B. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptRustSwift

class Solution:
    def convertInteger(self, A: int, B: int) -> int:
        A &= 0xFFFFFFFF
        B &= 0xFFFFFFFF
        return (A ^ B).bit_count()

class Solution {
    public int convertInteger(int A, int B) {
        return Integer.bitCount(A ^ B);
    }
}

class Solution {
public:
    int convertInteger(int A, int B) {
        unsigned int c = A ^ B;
        return __builtin_popcount(c);
    }
};

func convertInteger(A int, B int) int {
    return bits.OnesCount32(uint32(A ^ B))
}

function convertInteger(A: number, B: number): number {
    let res = 0;
    while (A !== 0 || B !== 0) {
        if ((A & 1) !== (B & 1)) {
            res++;
        }
        A >>>= 1;
        B >>>= 1;
    }
    return res;
}

impl Solution {
    pub fn convert_integer(a: i32, b: i32) -> i32 {
        (a ^ b).count_ones() as i32
    }
}

class Solution {
    func convertInteger(_ A: Int, _ B: Int) -> Int {
        return (Int32(A) ^ Int32(B)).nonzeroBitCount
    }
}

Comments