关于算法:编程之美21-求无符号整数N的二进制表示中1的个数

题目：求无符号整数N的二进制示意中1的个数

#include <iostream>

// way1办法相似将10进制数转换为二进制数的过程，
// 如果一个整数对2取模，如果后果为1，代表其最低位为1；
// 而后咱们将该整数向右挪动一位（即除2）
// 反复此过程，就能够拿到所有1的个数
int way1( unsigned int num )
{
    int count = 0;
    while ( num ) {
        if ( num % 2 == 1 ) {
            count++;
        }
        num = num / 2;
    }
    return count;
}

// way2办法：相当于把取模运算变为了按位与，将除2变为了右移操作，从而晋升了效率
int way2( unsigned int num )
{
    int count = 0;
    while ( num ) {
        count += num & 0x01;
        num = num >> 1;
    }
    return count;
}

// way3办法原理如下利用N和（N-1)的二进制表达式的关系，即N&(N-1)就会打消N的二进制中最左边的1。
// 具体阐明如下：
// 已知N，求N-1，咱们回顾一下，求N-1的二进制的减法过程
// 在N的二进制示意中，从最左边向左找第一个1，而后借位，被借的那个数位1变为0，而后往右返回一个2（二进制，借1当2），左边数位留下一个1，再借给右边的数位一个1，
// 反复此过程，直至最左边的数位。
// 举个例子，比方N=1100（十进制的12），N-1 = 1100 - 1 = 1011 ( 十进制的11）
// 请留神这个过程会产生一个景象，即N-1的二进制表达式和N的二进制表达式，从N的最右边的一个1（ 即1[1]00, 被[]括起来的那个1 ）开始，数位是齐全相同的，
// 而这个被括起来的1的右边，N和N-1是统一的。
// 因而，咱们能够利用这个法则，用N&(N-1)（&为按位与）来打消N的最低的一位1，（ 1100 & 1011 = 1000 ), 而后将后果赋值给N，
// 如此重复，能够做几次N&(N-1)，其二进制中就有几个1
int way3( unsigned int num )
{
    int count = 0;
    while ( num ) {
        num = num & (num - 1);
        count++;
    }
    return count;
}

int main( int argc, char** argv )
{
    // 求无符号整数num的二进制示意中1的个数
    // 为了不便验证后果，咱们间接将整数以二进制模式定义
    unsigned int num = 0b101110001;
    std::cout << "num is " << num << std::endl;
    std::cout << "way1 result : " << way1(num) << std::endl;
    std::cout << "way2 result : " << way2(num) << std::endl;
    std::cout << "way3 result : " << way3(num) << std::endl;

    return 0;
}