剑指offer-11、⼆进制中1的个数

题⽬描述

输⼊⼀个整数，输出该数 32 位⼆进制表示中 1 的个数。其中负数⽤补码表示。
示例1
输⼊：10
返回值：2
说明：⼗进制中10的32位⼆进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。
示例2
输⼊：-1
返回值：32
说明：负数使⽤补码表示 ，-1的32位⼆进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1
思路及解答

错误解答（不考虑负数）

⾸先说⼀个错误的解法，很多⼈可能会想到，那就是不断对 2 取余数。但是这种做法有个致命的缺陷，那就是忽略了负数，负数使⽤补码表示的时候，是取反之后加⼀

1. public class Solution {
2.         public int NumberOf1(int n) {
3.                 int num = 0;
4.                 while (n != 0) {
5.                         int tmp = n % 2;
6.                         if (tmp == 1||tmp==-1) ++num;
7.                         n /= 2;
8.                 }
9.                 return num;
10.         }
11. }

复制代码

字符串遍历

将整数转换为二进制字符串，然后遍历字符串统计'1'的个数。

1. public int NumberOf1(int n) {
2.     String binaryStr = Integer.toBinaryString(n);
3.     int count = 0;
4.     for (int i = 0; i < binaryStr.length(); i++) {
5.         if (binaryStr.charAt(i) == '1') {
6.             count++;
7.         }
8.     }
9.     return count;
10. }

复制代码

• 时间复杂度：O(n)，n为二进制位数（固定32位）
  
• 空间复杂度：O(n)，需要存储二进制字符串
  

API调⽤(不推荐)

Java标准库提供了统计二进制1个数的方法。

1. public int hammingWeight(int n) {
2.     return Integer.bitCount(n);
3. }

复制代码

位掩码与移位（逐位检查）

使用位掩码和移位操作逐位检查是否为1。
移位算法，把整数当成⼆进制，不断向右移位和1 进⾏与计算。利⽤了所有数和1 进⾏与计算，结果为1则证明最后⼀位是1 。

1. public int NumberOf1(int n) {
2.     int count = 0;
3.     int mask = 1;
4.     for (int i = 0; i < 32; i++) {
5.         if ((n & mask) != 0) {
6.             count++;
7.         }
8.         mask <<= 1;
9.     }
10.     return count;
11. }

复制代码

位运算

利用n & (n - 1)可以消除最右边的1的特性，直到n变为0
⽐如7的⼆进制是111 ，那么7&6=111&110=110=6 ，就完美把最后⼀位1 变成0 了， 6 的⼆进制是110 , 6&5=110&101=100=4 ，也把最后⼀位1 变成了0 。
负数呢？⽐如：
32位-7 = 11111111111111111111111111111001 ，
32位-8 = 11111111111111111111111111111000，
-7&-8 = 11111111111111111111111111111000

1. public int NumberOf1(int n) {
2.     int count = 0;
3.     while (n != 0) {
4.         count += (n & 1);
5.         n >>>= 1; // 无符号右移
6.     }
7.     return count;
8. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！