http://bookshadow.com/weblog/2017/01/08/leetcode-number-complement/
public int findComplement(int num) {
int valid = 0; // 最高位为1的位数
int tmp = num;
while(tmp > 0) {
tmp /= 2;
valid++;
}
return ~num & ((1 << valid) - 1);
}
其中，(1 << valid) - 1是二进制操作中一种常用的求掩码的方式，如valid为3，那么1<
https://www.cnblogs.com/liujinhong/p/6279855.html
X. http://www.cnblogs.com/grandyang/p/6275742.html
我们知道需要做的就是每个位翻转一下就行了，但是翻转的起始位置上从最高位的1开始的，前面的0是不能被翻转的，所以我们从高往低遍历，如果遇到第一个1了后，我们的flag就赋值为true，然后就可以进行翻转了，翻转的方法就是对应位异或一个1即可
解法I 位运算（异或）
def findComplement(self, num): """ :type num: int :rtype: int """ mask = (1 << 1 + int(math.log(num, 2))) - 1 return mask ^ num
解法II 按位取反并累加
def findComplement(self, num): """ :type num: int :rtype: int """ return int(''.join(str(1 - int(x)) for x in bin(num)[2:]), 2)
https://discuss.leetcode.com/topic/75605/java-very-simple-code-and-self-evident-explanation
https://discuss.leetcode.com/topic/74897/maybe-fewest-operations
impressive, but failed when num=0
X. https://leetcode.com/problems/number-complement/discuss/96018/Java-very-simple-code-and-self-evident-explanation
https://zxi.mytechroad.com/blog/bit/476-number-complement/
https://www.cnblogs.com/liujinhong/p/6279855.html
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:
Example 2:
https://discuss.leetcode.com/topic/74642/java-1-line-bit-manipulation-solution public int findComplement(int num) {
return ~num & ((Integer.highestOneBit(num) << 1) - 1);
}- The
flippedversion of the originalinputbut - Only flip
Nbits within the range fromLEFTMOSTbit of1toRIGHTMOST.
For example input =5(the binary representation is101), theLEFTMOSTbit of1is the third one fromRIGHTMOST(100,N= 3). Then we need to flip 3 bits fromRIGHTMOSTand the answer is010
To achieve above algorithm, we need to do 3 steps:
- Create a bit mask which has
Nbits of1fromRIGHTMOST. In above example, the mask is111. And we can use the decent Java built-in functionInteger.highestOneBitto get theLEFTMOSTbit of1, left shift one, and then minus one. Please remember this wonderful trick to create bit masks withNones atRIGHTMOST, you will be able to use it later. - Negate the whole input number.
Bit ANDnumbers in step1and2.
As several people pointed out, we don't need to left shift 1. That's true because the highest
1 bit will always become 0 in the Complement result. So we don't need to take care of that bit. public int findComplement(int num) {
return ~num & (Integer.highestOneBit(num) - 1);
}public int findComplement(int num) {
return num ^ ((Integer.highestOneBit(num) << 1) - 1);
}public int findComplement(int num) {
int valid = 0; // 最高位为1的位数
int tmp = num;
while(tmp > 0) {
tmp /= 2;
valid++;
}
return ~num & ((1 << valid) - 1);
}
其中，(1 << valid) - 1是二进制操作中一种常用的求掩码的方式，如valid为3，那么1<
https://www.cnblogs.com/liujinhong/p/6279855.html
2 public int findComplement(int num) { 3 int mask = 1, temp = num; 4 while(temp > 0) { 5 mask = mask << 1; 6 temp = temp >> 1; 7 } 8 return num^(mask-1); 9 }
我们知道需要做的就是每个位翻转一下就行了，但是翻转的起始位置上从最高位的1开始的，前面的0是不能被翻转的，所以我们从高往低遍历，如果遇到第一个1了后，我们的flag就赋值为true，然后就可以进行翻转了，翻转的方法就是对应位异或一个1即可
int findComplement(int num) { bool start = false; for (int i = 31; i >= 0; --i) { if (num & (1 << i)) start = true; if (start) num ^= (1 << i); } return num; }
解法I 位运算（异或）
def findComplement(self, num): """ :type num: int :rtype: int """ mask = (1 << 1 + int(math.log(num, 2))) - 1 return mask ^ num
解法II 按位取反并累加
def findComplement(self, num): """ :type num: int :rtype: int """ return int(''.join(str(1 - int(x)) for x in bin(num)[2:]), 2)
https://discuss.leetcode.com/topic/75605/java-very-simple-code-and-self-evident-explanation
for example:
100110, its complement is 011001, the sum is 111111. So we only need get the min number large or equal to num, then do substraction
100110, its complement is 011001, the sum is 111111. So we only need get the min number large or equal to num, then do substraction
public int findComplement(int num)
{
int i = 0;
int j = 0;
while (i < num)
{
i += Math.pow(2, j);
j++;
}
return i - num;
} public int findComplement(int num) {
int n = 0;
while (n < num) {
n = (n << 1) | 1;
}
return n - num;
}https://discuss.leetcode.com/topic/74897/maybe-fewest-operations
impressive, but failed when num=0
int findComplement(int num) {
int mask = num;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
return num ^ mask;
}2 public int findComplement(int num) { 3 int res = 0; 4 int i = 31; 5 while (i >= 0) { 6 if (((num >>> i) & 1) == 1) break; 7 i--; 8 } 9 while (i >= 0) { 10 if (((num >>> i) & 1) == 0) { 11 res |= 1<<i; 12 } 13 i--; 14 } 15 return res; 16 }
X. https://leetcode.com/problems/number-complement/discuss/96018/Java-very-simple-code-and-self-evident-explanation
100110, its complement is 011001, the sum is 111111. So we only need get the min number large or equal to num, then do substraction
public int findComplement(int num)
{
int i = 0;
int j = 0;
while (i < num)
{
i += Math.pow(2, j);
j++;
}
return i - num;
} public int findComplement(int num) {
int res = 1;
while (res <= num) {
res = res<<1;
}
return res - 1 - num;
}
int findComplement(int num) {
int mask = ~0;
while (num & mask) mask <<= 1;
return ~num ^ mask;
}
Integer.highestOneBit(i)是一个什么样的函数呢？
首先来补充一点背景知识。
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运算，可以通过上述例子进行类推。
了解了Java的位运算之后，来看下 Integer.highestOneBit (i) 这个函数的实现代码：
1 publicstaticinthighestOneBit(int i) { 2 // HD, Figure 3-1 3 i |= (i >> 1); 4 i |= (i >> 2); 5 i |= (i >> 4); 6 i |= (i >> 8); 7 i |= (i >> 16); 8 return i - (i >>> 1); 9 }
1、第一步的作用是把最高位1右移移位，并与原数据按位取或。那么这就使得最高位和它的下一位是连续两个1。
2、第二步的作用是把刚刚移位得到连续两个1继续右移两位并与原数据按位取或。那么这就使得最高两位和它的下两个连续位组成四个连续的1。
3、 以此类推，最终得到的i是从开始的最高位到结束全是1。并减去i不带符号的右移一位，即可得到一个int数据的最高位的值。
4、上述情况是针对于i不为零和负数的情况，如果i为零，那么得到的结果始终为零。如果i位负数，那么得到的结果始终是-2147483648。即等于Integer.MIN_VALUE。（原因在于负数的最高位始终为1，即是负数的符号位）
此函数的最重要理解点在与要始终把握二进制的最高位进行运算处理，那么对于函数中的右移一位、两位、四位、八和十六位就好理解了。同理，对于long类型的取最高位运算应该需要加一条语句 i|=(i>>32); 原因在于long类型在Java中是64位的。
Long类型的hightestOneBit(i)代码如下：
Long类型的hightestOneBit(i)代码如下：
1 public static long highestOneBit(long i) { 2 // HD, Figure 3-1 3 i |= (i >> 1); 4 i |= (i >> 2); 5 i |= (i >> 4); 6 i |= (i >> 8); 7 i |= (i >> 16); 8 i |= (i >> 32); 9 return i - (i >>> 1); 10 }
