剑指offer-二进制中1的个数

时间：2021-12-31 00:07:42

题目：二进制中1的个数

题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：这个题比较有意思，平时碰到二进制的题还是蛮少的

法1：直接将数n进行移位，从n 的二进制右面进行比较，先将n与1与一下，如果结果为1，则说明n的当前这一位为1，则计数器counts++，然后n右移一位，继续进行上述操作，直到n为0。上述做法对于正数是没问题的，但对于负数，其在右移时左边的符号位总是总动补1，导致程序会陷入死循环

所以要用>>>是无视符号位的右移，而不是>>带符号位右移

代码：

 1 public class Solution {
 2     public int NumberOf1(int n) {
 3         int counts=0;
 4        
 5             while(n!=0){
 6                 if((n&1)==1){counts++;}
 7                 n=n>>>1;         
 8         }
 9         return counts;
10     }
11 }

法2：也可以不移整数n，反而去移1，每次让1左移一位去逐次的与n的各个位置进行比较

 1 public class Solution {
 2     public int NumberOf1(int n) {
 3         int counts=0;
 4         int flag=1;    
 5           while(flag!=0){
 6                 if((n&flag)!=0){counts++;}
 7                 flag=flag<<1;         
 8         }
 9         return counts;
10     }
11 }

不过，这里注意这里的flag只有在刚开始等于1，左移一位后，flag=2（10）,再左移就变成了4（100），当1进行了32次左移后，flag=0跳出while循环，因为int型最大是32位，另外在这只能是(n&flag)!=0，而不是(n&flag)==1，因为n&flag可能等于任何数，实质上就是两个数相与

法3，学习一下与运算的最优解

 1 public class Solution {
 2     public int NumberOf1(int n) {
 3         int counts=0;     
 4           while(n!=0){
 5                counts++;
 6                n=n&(n-1);     
 7         }
 8         return counts;
 9     }
10 }

这个n=n&(n-1)其实也很好理解，相当于把二进制右端的位置，如果是1，则计数并将该位1清0，如果是0，则跳过该位了

以n=1111为例，循环一次后，n=1110;循环2次后，n=1100;循环3次后，n=1000;循环4次后，n=0000,跳出循环了

以n=1101为例，循环一次后，n=1100;循环2次后，n=1000;循环3次后，n=0000，跳出循环了

 

标签：

相关文章