二进制数中1的个数

红太狼 2022-03-25 15:26 202阅读 0赞

# [二进制数中1的个数][1] #

## 题目描述 ##

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

思路：在平时的学习中感受不到位运算的精妙，但是在一些算法处理和效率问题上位运算却提供了很好的解决方法，毕竟它是立足于二进制来处理数据的，最底层的也是效率最高的。  本题的考察重点也是位运算。

通过运算 & 与运算，每次循环 ——n=n & (n-1) 会使得每次都会排除一个1（在草稿纸上多举几个例子更加明白，因为二进制只能取到0  1.这对于负数也是一样的，但如果只对于正数而言，我们还可以通过 位运算——右移>> 1计算1的个数）,当通过与运算一定次数之后，n就会全变为0退出循环。

public class Solution {
        public int NumberOf1(int n) {
            int count = 0;
            while(n!= 0){
                count++;
                n = n & (n - 1);
             }
            return count;
        }
    }

关于位运算详解可以在本博客相关随笔找到

小插曲：

在看jdk文档时发现，Integer有一个bitCount方法可以直接计算二进制1的位数，而且还特定标明了有时用于人口普查。

![1456741-20180817101224727-1169755728.png][]

System.out.println(Integer.bitCount(-100));   // 28

1 //这里给出该方法的内部实现
     2  
     3 @HotSpotIntrinsicCandidate
     4     public static int bitCount(int i) {
     5         // HD, Figure 5-2
     6         i = i - ((i >>> 1) & 0x55555555);
     7         i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
     8         i = (i + (i >>> 4)) & 0x0f0f0f0f;
     9         i = i + (i >>> 8);
    10         i = i + (i >>> 16);
    11         return i & 0x3f;
    12     }

posted @ 2018-08-06 08:11 [Octopus22][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

[1]: https://www.cnblogs.com/Octopus-22/p/9428229.html
[1456741-20180817101224727-1169755728.png]: /images/20220325/18734cba01ed47a6bfd4b9291f4a1455.png
[Octopus22]: https://www.cnblogs.com/Octopus-22/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=9428229