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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 */
function NumberOf1( n ) {
    // js中所有数值都是使用64位存储的
    // 但在进行位运算时，JavaScript 引擎会将操作数转换为 32 位有符号整数，然后执行位运算，最后再将结果转换回为 64 位浮点数。
    // 故本题可以直接将整数n当做32位的二进制数
    // 此外，js中整数类型存储形式默认就是补码，因此也不需要进行特殊处理。
    // 原始思路：1的32位进制表示为0000...0001，最后一位为1，将n与1进行按位与操作，如果结果不为0，则表示最后一位为1，之后对n右移一位，继续比较下一位，以此类推进行计数。（运行超时）
    // let count = 0;
    // while(n){
    //     if(n & 1) count++;
    //     n = n >> 1;
    // }
    // return count;
    // 改进思路：布莱恩·科林汉算法 n & (n-1) 用于清除最右边的1，将其变为0
    // n-1是指将n最右边的1变为0，1右边的所有位变为1，如n为1101,则n-1为1100,n&(n-1)为1100，若n为1100,则n-1为1011，n&(n-1)为1100
    // n & (n-1)：结果是将n最右边的1变为0，即清除最右边的1。
    let count = 0;
    // 每清除一次，计数一次
    while(n){
        count++;
        n = n & (n - 1);
    }
    return count;

}
module.exports = {
    NumberOf1 : NumberOf1
};