首页 > 代码库 > 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:
- The given integer is guaranteed to fit within the range of a 32-bit signed integer.
- 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++）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。