请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如,把9表示成二进制是1001,有两位是1.因此,如果输入9,则该函数输出2。
- 正数(包括边界值1、0x7FFFFFFF)
- 负数(包括边界值0x80000000、0xFFFFFFFF)
- 0
- 考察应聘者对二进制及位运算的理解。
首先把n和1做与运算,判断n的最低位是不是为1,接着把1左移一位得到2,再和n做运算,就能判断n的次低位是不是1...这样反复左移,每次都能判断n的其中一位是不是1。
我们基于这样一个事实:把一个整数减去1之后再后原来的整数做位与运算,得到的结果相当于把整数的二进制表示中最右边的1变成0。例子如下:
n : 10110100
n-1 : 10110011
n&(n-1) : 10110000
那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。
Integer.bitCount(n);
对二进制操作不了解。
Java中没有无符号整形,所以这里忽略。
/**
* 二进制中1的个数
* @Author rex
* 2018/7/20
*/
public class Solution {
/**
* 惊喜解法
*
* 利用了把一个整数减去1之后再后原来的整数做位与运算,得到的结果相当于把整数的二进制表示中最右边的1变成0
*
* @param n
* @return
*/
public int numberOf1(int n) {
int count = 0;
while (n != 0) {
++count;
n = (n-1) & n;
}
return count;
}
}
位运算只有5中运算:与、或、异或、左移和右移。
与、或、异或运算就是简单的真值表。
左移运算符 m<<n 表示把 m 左移 n 位。在左移 n 位的时候,最左边的 n 位将被丢弃,同时在最右边补上 n 个0.
右移运算符 m>>n 表示把 m 右移 n位。在右移 n 位的时候,最右边的 n 位将被丢弃,但右移时处理最左边位情形有两种情况,如果数字是无符号数字,则用0填补最左边的 n 位;如果数字是一个有符号数值,则用数字的符号位填补最左边的 n 位。也就是说,如果数字原先是一个正数,则右移之后再最左边填补 n 个0;如果数字原先是负数,则右移之后在最左边补 n 个1。
负数的二进制表示(计算机用补码表示负数)
- 变成原码:将绝对值转换成二进制数,然后在最高位补1
- 变成反码:对原码除符号位外各位取反
- 变成补码:在反码最后一位加1
问题: 把整数右移一位和把整数除以2在数学上是等价的吗?
不是,除法的效率比一位运算效率低得多,在实际编程中应尽可能得用一位运算符代替乘除法。
值得注意的地方:
把一个整数减去1之后再后原来的整数做位与运算,得到的结果相当于把整数的二进制表示中最右边的1变成0。 很多二进制问题都可以用这种思路解决。