Question

面试题 05.06. 整数转换

English Version

题目描述

整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。

示例1:

 输入：A = 29 （或者0b11101）, B = 15（或者0b01111）
 输出：2

示例2:

 输入：A = 1，B = 2
 输出：2

提示:

1. A，B范围在[-2147483648, 2147483647]之间

解法

方法一：位运算

我们将 A 和 B 进行异或运算，得到的结果中 $1$ 的个数即为需要改变的位数。

时间复杂度 $O(\log n)$，其中 $n$ 为 A 和 B 的最大值。空间复杂度 $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
  }
}