首页 > 代码库 > 476. Number Complement【位运算】
476. Number Complement【位运算】
2017/3/14 15:36:44
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.
解法1
思路:5的二进制 00000101 , 取反后 11111010 , 应该返回 00000010,从左至右遇到第一个0截止,切前面的1替换为0即为答案。
publicclassSolution{
publicint findComplement(int num){
num =~num;
int flag =31;
while((1<<flag & num)!=0){
--flag;
}
int comparer =1<<flag;
comparer |= comparer>>1;
comparer |= comparer>>2;
comparer |= comparer>>4;
comparer |= comparer>>8;
comparer |= comparer>>16;
return comparer & num ;
}
}
鉴于jdk中Integer类中有一个highestOneBit函数如下 ,作用 00010011---> 00010000 ,可以简化解法1的while循环
publicstaticint highestOneBit(int i){
// HD, Figure 3-1
i |=(i >>1);
i |=(i >>2);
i |=(i >>4);
i |=(i >>8);
i |=(i >>16);
return i -(i >>>1);
}
顺便,了解了源码中如何得到最后一个1,作用 00001100 --> 00000100 函数如下
publicstaticint lowestOneBit(int i){
// HD, Section 2-1
return i &-i;
}
另 00001000 --> 00001111 , 在只有一个1的情况下填充1 有个更简单的方法,num<<1 - 1 。因此可以简化解法1的5个或位运算,得到解法2。
解法2:(借鉴discuss)
publicclassSolution{
publicint findComplement(int num){
return~num &((Integer.highestOneBit(num)<<1)-1);
}
}
又 因为 num取反后 11111010, 所以不需要 00000111,只需要00000011即可,因此不用左移1位,这是比较多余的一步。
publicclassSolution{
publicint findComplement(int num){
return~num &(Integer.highestOneBit(num)-1);
}
}
476. Number Complement【位运算】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。