476. Number Complement（求补数）

Dear 丶 2022-09-28 14:25 97阅读 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 条评论，97人围观）

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

相关阅读

相关 476. Number Complement（求补数）

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

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

相关 [leetcode]: 476. Number Complement

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

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

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

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

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

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

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

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

相关 476_Number_Complement

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

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

相关 leetcode 476. Number Complement 计算补数

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

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

相关【LeetCode】476.Number Complement 补数

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

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

相关 LeetCode476. 数字的补数

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。注意: 1. 给定的整数保证在32位带符号整数的范围内。 2. 你可以假定二进制数不包含前导零位。示例

àì夳堔傛蜴生んèń/ 2022年05月23日 03:10/ 0 赞/ 144 阅读

相关 476. Number Complement

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

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

相关二补数 (2's complement)

二补数 (2's complement) :是一种用二进位表示有号数的方法，也是一种将数字的正负号变号的方式，常在计算机科学中使用。一个数字的二补数就是将该数字作位元反向运

野性酷女/ 2021年12月17日 02:47/ 0 赞/ 208 阅读