首页 > 代码库 > LeetCode 476. Number Complement (数的补数)

LeetCode 476. Number Complement (数的补数)

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.

 

 


 题目标签:Bit Manipulation
  这道题目给了我们一个int数,让我们找到它的补数。而且这个数字是正数,那么我们只要把除了leading zeros的数字都反转一下就可以了。设一个32次的for loop, 利用 & 1 来判断最后边的bit 是不是0, 如果是0,那么我们需要反转它,设一个x,规律是1,2,4,8。。。2进制, 如果是0,那么就加x,如果是1,那么不需要加。然后利用 >> 1来移动num 向右一位。 当num == 1的时候,意味着所有1左边的数字都是0了,这个时候已经不需要在继续反转下去了。
这道题目看上去挺简单的,但是一下子还没做出来。。。看来今天状态不佳,适合出去玩。
 

Java Solution:

Runtime beats 61.45% 

完成日期:06/29/2017

关键词:Bit Manipulation

关键点:利用 & 1 判断最右边的bit; 利用 >> 来移动bits;判断num == 1 来终止反转

 

 1 public class Solution 
 2 {
 3     public int findComplement(int num) 
 4     {
 5         int res = 0;
 6         int x = 1;
 7         
 8         for(int i=0; i<32; i++)
 9         {
10             if((num & 1) == 0) // meaning num‘s bit is 0, need to flip this bit.
11                 res += x;
12             
13             x = x * 2; // increase the x 
14             
15             if(num == 1) // if current num is == 1, meaning all the leading numbers are zeros; stop
16                 break;
17                 
18             num = num >> 1; // shift num to right by 1 bit.
19             
20         }
21         
22         return res;
23     }
24 }

参考资料:

http://www.cnblogs.com/grandyang/p/6275742.html

LeetCode 476. Number Complement (数的补数)