Question

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

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
  }
}