Skip to content

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

Thinking

Turning \(A\) into \(B\) flips every bit where they differ. A \(32\)-step bit walk works.

Those bits are exactly the ones in \(A\oplus B\), so the answer is the Hamming weight of the XOR.

Mask both with \(0xFFFFFFFF\) so negative values share a \(32\)-bit unsigned view, then bit_count.

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)\).

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

1
2
3
4
5
class Solution {
    public int convertInteger(int A, int B) {
        return Integer.bitCount(A ^ B);
    }
}

1
2
3
4
5
6
7
class Solution {
public:
    int convertInteger(int A, int B) {
        unsigned int c = A ^ B;
        return __builtin_popcount(c);
    }
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

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

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

Comments