[LeetCode刷题] 476. 数字的补数–Java实现

题目链接

https://leetcode-cn.com/problems/number-complement/

题目描述

对整数的二进制表示取反（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

解题思路

1.位运算

通过位运算实现题解，主要分为四步：

1. 将输入数字取反并暂存；
2. 将输入数字的二进制，从左至右，从第一个1开始，将所有0变为1；
3. 将第二步得到的数字取反；
4. 将第三步与第一步得到的两个数字求异或，即为题目要求的“补数”。

时间复杂度O(1);

[note]: 位运算笔记

Java代码实现：

class Solution {
       public int findComplement(int num) {
            //以5为例：00000101
            //取反 11111010
            int tem = ~num;
            //经过下面四行：00000101变为00000111
            num |= num >> 1;
            num |= num >> 2;
            num |= num >> 4;
            num |= num >> 8;//整型一般是 32 位，上面假设 8 位。
            //取反：变为11111000
            num = ~num;
            //异或 11111010和11111000变为00000010
            tem = tem ^num;

            return tem;
      }
}