仓库源文，站点原文

title: '算法:二进制中1的个数' cover: https://img.paulzzh.com/touhou/random?13 categories: 算法题目 date: 1996-07-27 08:00:00 tags: [算法题目, 位运算]

toc: true

<br/>

二进制中1的个数

二进制中1的个数

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

分析

这个问题我能想到的有三种解法：

• 数字转为字符串计算'1'出现次数;
• 通过位运算进行计算;
• 使用Java底层API: Integer.bitCount(x)

代码

数字转为字符串计算'1'出现次数;

public class Solution {
    public int NumberOf1(int n) {
        int t=0;
            char[]ch=Integer.toBinaryString(n).toCharArray();
            for(int i=0;i<ch.length;i++){
                if(ch[i]=='1'){
                    t++;
                }
            }
            return t;
    }
}

位运算

Java提供了>>>位移运算符：忽略符号位，而仅将整个数右移；

对于>>唯一运算符：右移一位，高位补上符号位，将会造成死循环

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

另一种解法：

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

Java底层API

public class Solution {
public int  NumberOf1(int n) {
         return Integer.bitCount(n);
     }
}

底层实现：

public class Solution {
    public int NumberOf1(int i) {
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }
}