首页 > 代码库 > LeetCode 476. Number Complement(easy难度c++)

LeetCode 476. Number Complement(easy难度c++)

题目: 

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.

思路: 
题目其实不难,但是找到高效的解法其实并不容易,从我测试的结果来看,题目中的测试用例使用的应该都是正数。具体来说可以这样做:1、先确定转化为二进制之后的数字位数,比如5对应101,就是三位数;2.再取对应的数量的1,此时取111,二者异或运算,得到010,也就是2,就是所求的数字。

代码如下:

 1 class Solution {
 2 public:
 3     int findComplement(int num) {
 4         
 5          int mask = 1, temp = num;
 6         while(temp > 0) {
 7               mask = mask << 1;
 8              temp = temp >> 1;
 9          }
10          return num^(mask-1);
11     }
12 };

 

首先来补充一点背景知识。
 
1、在计算机系统中,数值一律使用补码来表示和存储。主要原因是使用补码可以将符号位和其它位统一处理;同时,减法也可按照加法来处理。另 外,   两个用补码表示的数相加时,如果最高位(符号位)有进位,则进位被舍弃。
- 补码与原码的转换过程几乎相同。
    - 数值的补码表示(分两种)
        - 正数的补码:与原码相同
        - 负数的补码:符号位位1,其余位位该数绝对值的原码按位取反;然后整个数加1
    - 已知一个数的补码,求原码的操作分为两种情况
        - 如果补码的符号位“0”,表示是一个正数,所以补码就是该数的原码
        - 如果补码的符号位为“1”,表示是一个负数,求原码的操作可以是:符号位位1,其余各位取反,然后整个数加1。
2、移位运算符就是在二进制的基础上对数字进行平移。Java按照平移的方向和填充数字的规则分为三种:<<左移,>>带符号右移 和>>>无符号右移。
3、 在Java的移位运算中,byte、short和char类型移位后的结果会变成int类型,对于byte、short、char和int进行移位时,对于char、short、char和int进行移位操作时,规定实际移动的次数是移动次数和32的余数,也就是移位33次和移位1次得到的结果相同。移动long型的数值时,规定实际移动的次数是移动次数和64的余数,也就是移动65次移位1次得到相同的结果。
    (1) <<  运算规则:按二进制形式吧所有的数字向左移动对应的位数,高位移出(舍弃),低位的空位补零。
    语法格式:
         需要移位的数字<<移位的次数
         例如:4<<2 ,则是将数字4左移2位
     计算过程
         4<<2
        Java中一个int数占四个字节,那么4的二进制数字为00000000 00000000 00000000 00000100,然后把该数字左移两位。其它的数字都朝右平移两位,最后在低位(右侧)的两个空位补零。则得到的最终结果是00000000 00000000 00000000 00010000,即转换为十进制数16。
         在数字没有溢出的前提下,对于正数和负数,左移一位都相当于乘以2的1次方,左移n位就相当于乘以2的n次方。
         在溢出的前提前,则不符合这个规律。读者可以尝试输出(long)1610612736*4和1610612736<<2这两个结果进行比对。
    (2)>>运算规则:按二进制形式吧所有的数字都向右移动对应的位置,低位移出(舍弃),高位的空位补符号位,即正数补零,负数补1。
     语法格式:
         需要移位的数字>>移位的次数
         例如:-4>>2和4>>2,则是将数字 -4和4右移2位
     计算过程
         4>>2
         Java中一个int数占四个字节,同样4的二进制为00000000 00000000 00000000 00000100,然后把该数字右移两位。其它的数字都朝左平移两位,最后在高位补符号位(该数是正数,全补零),得到的结果是00000000 00000000 00000000 00000001,即使十进制的1。数学意义就是右移移位相当于除2,右移n位相当于除以2的n次方。
        4>>2
         由于负数在计算机中是以补码的形式存储的,那么-4的二进制为11111111 11111111 11111111 11111100,然后把该数字右移两位,其它数字都朝左平移两位,最后在高位补符号位(该数是负数,全补一),得到的结果是11111111 11111111 11111111 11111111(补码格式),即是十进制的-1。
    (3)>>>运算规则:按二进制形式吧所有的数字向右移动对应的位数,低位移出(舍弃),高位的空位补零。正数运算结果与带符号右移相同,对于负数来说则不同。
         对于4>>>2和-4>>>2运算,可以通过上述例子进行类推。

LeetCode 476. Number Complement(easy难度c++)