《剑指offer第二版》面试题12：矩阵中的路径（java）

题目描述

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

解题思路一:

1. 定义标志位flag，初始值为1.
2. 每次将flag 左移一位，然后和输入的整数做与操作，如果结果大于0，说明这一位为1。如此反复即可求得1的总数。
3. 循环的次数为32次。

解题思路二：

1. m & (m - 1)，相当于将m的二进制的最后一个1变成了0。比如m=1100, m-1=1001, m&(m-1)=1000。
2. 一个整数的二进制中有多少个1，则可以进行多少次这样的操作。

代码

// 解法一
int numberOfn(int n){
    int count = 0;
    int flag = 1;
    while (flag > 0){
        if ((flag & n) >= 1 ) {
            count++;
        }
        flag = flag << 1;
    }
    return count;
}

// 解法二
int numberOfnV2(int n){
    // 1100
    // 1011
    int count = 0;
    while (n > 0) {
      count ++;
      n = n & (n - 1);
    }
    return count;
}