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