Question

1611. 使整数变为 0 的最少操作次数

English Version

题目描述

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。
• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

 

示例 1：

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

示例 2：

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

 

提示：

• 0 <= n <= 109

解法

方法一：格雷码逆变换（格雷码转二进制码）

本题实际上求的是格雷码为 $n$ 的逆变换，即通过格雷码构造原数。

我们先来回顾一下二进制码转换成二进制格雷码，其法则是保留二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或，而格雷码其余各位与次高位的求法相类似。

假设某个二进制数表示为 $B_{n-1}B_{n-2}…B_2B_1B_0$，其格雷码表示为 $G_{n-1}G_{n-2}…G_2G_1G_0$。最高位保留，所以 $G_{n-1} = B_{n-1}$；而其它各位 $G_i = B_{i+1} \oplus B_{i}$，其中 $i=0,1,2..,n-2$。

那么，格雷码转换成二进制码的逆变换是什么呢？

我们可以发现，格雷码的最高位保留，所以 $B_{n-1} = G_{n-1}$；而 $B_{n-2} = G_{n-2} \oplus B_{n-1} = G_{n-2} \oplus G_{n-1}$；而其它各位 $B_i = G_{i} \oplus G_{i+1} \cdots \oplus G_{n-1}$，其中 $i=0,1,2..,n-2$。因此，我们可以用下面的函数 $rev(x)$ 得到其二进制码：

int rev(int x) {
  int n = 0;
  for (; x != 0; x >>= 1) {
    n ^= x;
  }
  return n;
}

时间复杂度 $O(\log n)$，其中 $n$ 为题目给定的整数。空间复杂度 $O(1)$。

class Solution:
  def minimumOneBitOperations(self, n: int) -> int:
    ans = 0
    while n:
      ans ^= n
      n >>= 1
    return ans

class Solution {
  public int minimumOneBitOperations(int n) {
    int ans = 0;
    for (; n > 0; n >>= 1) {
      ans ^= n;
    }
    return ans;
  }
}

class Solution {
public:
  int minimumOneBitOperations(int n) {
    int ans = 0;
    for (; n > 0; n >>= 1) {
      ans ^= n;
    }
    return ans;
  }
};

func minimumOneBitOperations(n int) (ans int) {
  for ; n > 0; n >>= 1 {
    ans ^= n
  }
  return
}

function minimumOneBitOperations(n: number): number {
  let ans = 0;
  for (; n > 0; n >>= 1) {
    ans ^= n;
  }
  return ans;
}

方法二

class Solution:
  def minimumOneBitOperations(self, n: int) -> int:
    if n == 0:
      return 0
    return n ^ self.minimumOneBitOperations(n >> 1)

class Solution {
  public int minimumOneBitOperations(int n) {
    if (n == 0) {
      return 0;
    }
    return n ^ minimumOneBitOperations(n >> 1);
  }
}

class Solution {
public:
  int minimumOneBitOperations(int n) {
    if (n == 0) {
      return 0;
    }
    return n ^ minimumOneBitOperations(n >> 1);
  }
};

func minimumOneBitOperations(n int) int {
  if n == 0 {
    return 0
  }
  return n ^ minimumOneBitOperations(n>>1)
}

function minimumOneBitOperations(n: number): number {
  if (n === 0) {
    return 0;
  }
  return n ^ minimumOneBitOperations(n >> 1);
}