剑指Offer LeetCode 面试题15. 二进制中1的个数

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

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：00000000000000000000000000001011

输出：3

解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

示例 2：

输入：00000000000000000000000010000000

输出：1

解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。

示例 3：

输入：11111111111111111111111111111101

输出：31

解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

解题1

因为JDK中的Integer包装类中自带了toBinaryString方法，可以实现十进制转2进制。

可以先调用这个String s = Integer.toBinaryString(n);进行十进制转换成二进制

然后遍历一遍，匹配1。计数。就ok了。

但是效率有点低

import java.util.Arrays;
class Solution {
    static public int hammingWeight(int n) {
        int num = 0;
        String s = Integer.toBinaryString(n);
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i)=='1'){
                num++;
            }
        }
        return num;
    }
    public static void main(String[] args) {
        System.out.println(hammingWeight(11));
    }
}

解题思路2 利用“移位”操作实现

果然是十进制转换二进制的时候出了问题。

利用“移位”操作实现

import java.util.Arrays;
class Solution {
    static public int hammingWeight(int n) {
        int num = 0;
        for(int i = 31;i >= 0; i--) {
            if((n >>> i & 1)==1){
                num++;
            }
        }
        return num;
    }
    public static void main(String[] args) {
        System.out.println(hammingWeight(11));
//        System.out.println();
    }
}

利用“移位”操作实现

我们可以直接利用移位操作对一个十进制数进行移位操作，即：将最高位的数移至最低位（移31位），除过最低位其余位置清零，使用& 操作，可以使用和1相与（&），由于1在内存中除过最低位是1，其余31位都是零，然后把这个数按十进制输出；再移次高位，做相同的操作，直到最后一位 ，代码如下。可以说，这是我到目前为止见到的最简单的实现方式了。

public void binaryToDecimal(int n){
     for(int i = 31;i >= 0; i--)
         System.out.print(n >>> i & 1);
 }

说明：由于计算机中存储的都是数的补码，正数的原码、反码、补码都是相同的；而负数的原码、反码、补码是不一样的，补码=原码取反+1（符号位不变）。所以，负数是按照它的补码输出的。

>>>为逻辑移位符，向右移n位，高位补0

>>算数移位符，也是向右移n位，不同的是：正数高位补0，负数高位补1

<< 移位符，向左移n位，低位补0