476. Number Complement（求补数）

Dear 丶 2022-09-28 14:25 155阅读 0赞

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

1.  The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2.  You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Input: 5
    Output: 2
    Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: 1
    Output: 0
    Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

题目大意：给定一个正整数，求其补数。补数的定义是：翻转原数的二进制表示之后得到的数，不考虑原数前面的0。

解题思路：

解法一：不停地对原数进行%2和/2的操作，如果取余结果为0，则加上对应位置的2的整数次方，直到原数变为0。

代码如下：（13ms，beats 29.50%）

public int findComplement(int num) {
    		int res = 0;
    		int i = 0;
    		while (num != 0) {
    			if ((num & 0x1) == 0) {
    				res += Math.pow(2, i);
    			}
    			i++;
    			num >>= 1;
    		}
    		return res;
    	}

解法二：一行代码搞定，大意是先将原数取翻，但此时原数左边的若干个0变成了1，我们只取需要的右半部分。其中java.lang.Integer.highestOneBit(int i)返回的是将i的二进制表示中最高非0位右边的所有位都置0所得到的数，例如对5（101）执行该方法返回的就是4（100）。

代码如下：（11ms，beats 64.10%）

public int findComplement(int num) {
    		return (~num) & ((Integer.highestOneBit(num) << 1) - 1);
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关 476. 数字的补数

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。示例 1: 输入: 5 输出: 2 解释: 5 的二进制表示为 101（没有前导零位）

梦里梦外;/ 2023年10月05日 19:52/ 0 赞/ 40 阅读

相关 476. 数字的补数

题目来源 [leetcode][] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_

喜欢ヅ旅行/ 2023年02月11日 07:22/ 0 赞/ 28 阅读

相关 476. Number Complement（求补数）

Given a positive integer, output its complement number. The complement strategy is to fl

Dear 丶/ 2022年09月28日 14:25/ 0 赞/ 156 阅读

相关 [leetcode]: 476. Number Complement

1.题目描述 Given a positive integer, output its complement number. The complement strategy

淩亂°似流年/ 2022年06月16日 00:39/ 0 赞/ 159 阅读

相关 leetcode--476--Number Complement（我的解法）

原题目为： ![Image 1][] 我的源代码如下: class Solution { public: int findCom

偏执的太偏执、/ 2022年06月14日 11:11/ 0 赞/ 156 阅读

相关【leetcode】【套路题】476. Number Complement

一、题目描述 Given a positive integer, output its complement number. The complement strategy

短命女/ 2022年06月10日 08:59/ 0 赞/ 155 阅读

相关 476_Number_Complement

/ Given a positive integer, output its complement number. The complement strateg

小咪咪/ 2022年06月08日 00:52/ 0 赞/ 371 阅读

相关 leetcode 476. Number Complement 计算补数

Given a positive integer, output its complement number. The complement strategy is to fl

约定不等于承诺〃/ 2022年06月04日 10:28/ 0 赞/ 174 阅读

相关【LeetCode】476.Number Complement 补数

题目题目地址 [https://leetcode.com/problems/number-complement/description/][https_leetcode

﹏ヽ暗。殇╰゛Y/ 2022年06月01日 02:08/ 0 赞/ 192 阅读

相关 476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to fl

迈不过友情╰/ 2022年03月25日 00:41/ 0 赞/ 167 阅读