首页 > 代码库 > 剑指Offer之二进制中1的个数

剑指Offer之二进制中1的个数

 思路分析:

  首先分析把一个数减去1的情况,如果一个整数不等于0,那么改整数的二进制表示其中至少有一位是1.先假设这个数的最右边是1,那么减去1时,最后一位变成0而其他所有位都保持不变。也就是最后一位相当于做了取反操作,由1变成了0。

  接下来假设最后一位不是1而是0的情况。如果该整数的二进制表示中最右边1位位于第m位,那么减去1时,第m位由1变成0,而第m位之后的所有0都变成1,整数中第m位之前的所有位都保持不变。举个例子:一个二进制数1100,它的第二位是从最右边数起的一个1.减去1之后,第二位变成0,它的后两位0变成1,而前面的1保持不变,因此得到的结果是1011。

  在前面两种情况中,我们发现把一个整数减去1,都是把最右边的1变成0.如果它的右边还有0的话,所有的0都变成1,而它左边所有位都保持不变。接下来我们把一个整数和它减去1的结果做与运算,相当于把它最右边的1变成0.还是以前面的1100为例,它减去1的结果是1011.我们再把1100和1011做位于运算,得到的结果是1000.我们把1100最右边的1变成了0,结果刚好是1000。

  我们把上面的分析总结起来就是:把一个整数减去1,在和原整数做与运算,会把该整数的最右边一个1变成0.那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。基于这种思路,代码如下:

import java.util.Scanner;

/**
 * Created by Feng on 2017/5/6.
 * 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
 */
public class NumberOf1InBinary {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int result = numberOf1(n);
            System.out.println(result);
        }
    }

    private static int numberOf1(int n) {
        int count = 0;
        while (n != 0) {
            ++count;
            n = (n - 1) & n;
        }

        return count;
    }
}

 

剑指Offer之二进制中1的个数