leetcode476. 数字的补数

leetcode 476. 数字的补数

题目描述

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。 给你一个整数 num ，输出它的补数。

示例 1：

输入：num = 5 输出：2 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。 示例 2：

输入：num = 1 输出：0 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

提示：

1 <= num < 231

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/number-complement 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

异或
我们知道,取反最快的方法是异或,直接对-1(11...11全是1)就可以得到取反数,所以我们可以使用用户的 方法来解决这个题
但是需要注意的是,我们需要忽略前置0,就是说前面的所有0都要忽略,从首位为1开始异或,所以我们不能直接异或-1,
所以我们需要:

1. 找到为1的数据的位置
2. 对后面的数据进行异或

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func findComplement(num int) int {
 i := 32
 for ; i >= 0; i-- { //找到为1的数据的位置
  if 1<<i&num > 0 {
   break
  }
 }
 for i >= 0 { //对后面的数据进行异或
  num ^= 1 << i
  i--
 }
 return num
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 90.54% 的用户 通过测试用例： 149 / 149 炫耀一下:

算法优化

func findComplement(num int) int {
 i := 32
 for ; i >= 0; i-- { //找到为1的数据的位置
  if 1<<i&num > 0 {
   i++
   break
  }
 }
 return num ^ (1<<i - 1)//异或去前置0后的数
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 90.54% 的用户 通过测试用例： 149 / 149