题目描述
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示
示例:
输入：10
返回：2
我们发现将10 转成二进制为1010，按照题目的描述，表示1的个数有2个，所以返回2
这时我们自定义输入个数：15，看看二进制结果是多少？
返回1的个数的结果应该是4，为什么输入10 的二进制是1010，输入15是1111?
二进制转换
我们使用Byte字符的二进制做演示，首先我们直观一点举例正数说明
以此类推....那么十进制转二进制该怎么做呢？来看看规律？
有没有发现？从右开始往左是2^0(二的零次方)、2^1（二的一次方）、2^2（二的平方）、2^3（二的三次方）
根据前面知识点，你知道：01101110的十进制是多少么？
那么我们说Byte表示 -128 ~127 ，那么0和1 是怎么表示正数和负数的呢？
我们现在知道二进制的最高位：0 正数 1 负数
那么对于整数还要提三个码：原码、反码、补码
那么我们思考一下：在计算机中： -14 是什么样的呢？
接下来看看负数的解析图:十进制：14、二进制：00001110
接下来我相信大家都了解了什么是原码、反码、补码了，而题目中刚提到负数用补码来展示
在Java中整数常量默认为int类型，而用二进制定义整数的时候默认为32位
解法一：
我们先从32位的思路开始一个一个开始比较，需要比较32次
public class Solution {
public int NumberOf1(int n) {
int result =0;
//我们可以直接利用移位操作对一个十进制数进行移位操作，
// 即：将最高位的数移至最低位（移31位），除过最低位其余位置清零，使用& 操作，可以使用和1相与（&），
// 由于1在内存中除过最低位是1，其余31位都是零，然后把这个数按十进制输出,如果为1，则记为1，从0累加
// 再移次高位，做相同的操作，直到最后一位
for(int i = 31;i >= 0; i--) {
if((n >>> i & 1)==1){
result++;
}
}
return result;
}
}时间复杂度：O(32)
空间复杂度：O(1)
会不会有小伙伴遇到& 什么意思？其实是将两边的数转换为二进制位，然后运算最终值
简单来说就是
1&1=1 1&0=0
0&0=0 0&1=0
那么n >>>1 是什么意思呢？ >>>其实是右移运算符
当我们遇到没有符号的右移运算符时，比如说15的二进制位是0000 1111 ， 右移1位就是0000 0111
若我们把0000 0111 转为十进制就是7
若我们按照思路一个一个比较，那么输入10，他的十进制就是0000 1010
我们移动i个就可以丢弃，所以 n>>> i 即丢弃，高位补位的意思
题目的要求是表示1的个数，此时我们只需要res == 1 即满足要求
解法二：
上一种解法中，我们发现无用操作是若当前位是0， 还是会做判断，然后一位一位的移动
那么能不能让遇到0直接略过？什么意思呢？
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，如果最右边的1后面还有0的话，那么在1后面的所有的0都会变成1，其余所有位将不会受到影响
我们举个示例看看，比如说10 和9
我们输入十进制：10 ，转换的二进制是1010，当我们将10减1时，就会变成9
我们输入十进制：9 ，转换的二进制是1001，这时(1010)从右往左数最右边1就会变为0
原最右边的1后面还有个0，所以0变成1，那么就是1010 -> 1001
这个时候如果我们再把原来的整数和减去1之后的结果做位运算
从原来整数最右边一个1那一位开始所有位都会变成0
如1100 & 1011 = 1000 也就是说，把一个整数减去1，再和原整数做运算，会把该整数最右边一个1变成0 那么一个整数的二进制有多少个1，就可以进行多少次这样的操作
public int NumberOf1(int n) {
//解法 把一个整数n减去1，再和原来的整数与运算，会把该整数的最右边的1变成0，
//那么，一个整数的二进制中有多少个1，就可以进行多少次这样的操作。循环结束的条件是n为0
int result=0;
while(n!=0){
n = (n-1) & n;
result++;
}
return result;
}时间复杂度：O(n) n为输入参数n中1的个数
空间复杂度：O(1)
京公网安备 11010502036488号