面试题15. 二进制中1的个数

怼烎@ 2023-02-11 03:18 33阅读 0赞

# 题目来源 #

[面试题15. 二进制中1的个数][15. _1]

[191. 位1的个数][191. _1]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 调用库函数 ##

public class Solution {
        
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
        
            return Integer.bitCount(n);
        }
    }

![在这里插入图片描述][2020052114445441.png]

## 转为二进制字符串 ##

先转为二进制字符串，然后在统计字符串中1出现的个数

public class Solution {
        
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
        
            char[]  carr = Integer.toBinaryString(n).toCharArray();
            int i = 0;
            for (char c: carr) {
        
                if (c == '1'){
        
                    i++;
                }
            }
            return i;
        }
    }

## 位运算 ##

[理论][Link 1]

每次判断数字的二进制表达的最后一位是否为1，如果是1就计数器加一，然后将数字右移一位

public class Solution {
        
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
        
            int cnt = 0;
            while(n != 0) {
        
                cnt = cnt + (n & 1); // 注意+的优先级比&大, 所以一定要(). t &1 表示取出最后一位
                n = n >>> 1;  // 左移
            }
            return cnt;
        }
    }

![在这里插入图片描述][20200521155007519.png]

## n与n-1 ##

上一种方法会有很多无效操作，比如100个0连在一起，需要右移100次才能遇到下一个1。这里可以用到上面提到的x & (x - 1)，每次去掉最右边的一个1，x中有多少个1，就只要循环这么多次。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

public class Solution {
        
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
        
            int cnt = 0;
            while(n != 0) {
        
                n = n&(n-1);  //消除最右边的1
                cnt++; 
            }
            return cnt;
        }
    }

![在这里插入图片描述][20200521160553882.png]

## 平行算法 ##

[CCCC][]

[15. _1]: https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
[191. _1]: https://leetcode-cn.com/problems/number-of-1-bits/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521144503932.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[2020052114445441.png]: https://img-blog.csdnimg.cn/2020052114445441.png
[Link 1]: https://blog.csdn.net/zhizhengguan/article/details/106258502
[20200521155007519.png]: https://img-blog.csdnimg.cn/20200521155007519.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521160450502.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200521160553882.png]: https://img-blog.csdnimg.cn/20200521160553882.png
[CCCC]: https://www.cnblogs.com/selwynHome/articles/2565010.html