面试题10：二进制中1的个数

题目描述

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

代码实现

public class Solution {
public int  NumberOf1(int n) {
/*
    //”逻辑右移“n然后与1相与的方法
    int count = 0;
    while (n != 0) {
        if ((n & 1) == 1) {
            count++;
        }
        n = n >>> 1;
    }
    return count;
*/ 
/*
    //左移1然后与n相与的方法
    int count = 0,flag = 1;
    while (flag != 0) {
        if ((n & flag) != 0) {
            count++;
        }
        flag = flag << 1;
    }
    return count;
*/
    //把一个整数减去1之后再和原来的整数做位与运算的方法
    int count = 0;
    while (n != 0) {
        n = (n-1) & n;
        count++;
    }
    return count;
}
}

主要思路

1、首先因为位运算只有与,或,异或,左移,右移这五种运算，很自然地想到用右移n然后与1相与的方法（必须是逻辑右移>>>,否则会出现死循环）,或者用左移1然后与n相与的方法
2、把一个整数减去1之后再和原来的整数做位与运算,得到的结果相当于是把整数的二进制表示中的最右边一个1变成0,因此一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作