题解 | #二进制中1的个数#

题目

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

思路

注释部分为我自己的思考。
①正数
当n为正数，如何得到它的二进制数呢？通过求模。将n除以2得到的余数保存下来，这里用到了栈的结构（其实后来思考过用不用都行，用了反而复杂点，可以直接用数组的），将每次运算得到的余数入栈，最后对这个栈做出栈处理，判断如果栈顶元素==1，则总数num+1。
②负数
当n为负数，如何得到它的二进制数呢？要知道负数的补码等于该数的绝对值的原码取反+1，有一种更快的方法，比如得到绝对值的原码为1010100，取反加1后为0101100，规律：在原码从右往左找到第一个1，这个1左边的所有数字取反，这个1右边的所有数字保持不变，得到的数就是反码。所以我的代码为将这个负数绝对值除以2的余数存进一个arrayList集合中，从左至右其实是原码的从右至左，找到数组的第一个为1的元素的下标，然后遍历这个下标以后的数组元素，如果为0则num++，最后返回num的数还要加1，因为还有找到的第一个1没有被加进去。

可惜我的思路实践出来是错误的，还未找到原因，并且发现他人的代码更加简洁精炼。

代码

import java.util.Stack;
import java.util.ArrayList;

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >>> i) & 1) == 1) {
                count++;
            }
        }
        return count;

        /*Stack<Integer> stack1 = new Stack<Integer>();
        int num = 0;
        if(n == 0){
            return num;
        }else if(n > 0){
            while(n != 0){
                stack1.push(n%2);
                n=n/2;
            }

            while(stack1.isEmpty() == false){
                int top = stack1.pop();
                if(top == 1){
                    num++;
                }
            }

            return num;
        }else{
            int m = n*(-1);
            int index = 0;
            ArrayList list = new ArrayList();
            while(m != 0){
                list.add(m%2);
                m=m/2;
            }

            int[] arr = new int[32];

            for(int i=0;i<32;i++){
                if(i<list.size()){
                    arr[i] = (Integer)list.get(i);
                }else{
                    arr[i] = 0; 
                }

            }

            for(int j=0;j<32;j++){
                if(arr[j] == 1){
                    index = j;
                    break;
                }
            }

            for(int j=index+1;j<arr.length;j++){
                if(arr[j] == 0){
                    num++;
                }
            }
            num = num +1;
            return num;
        }*/

    }
}