关于算法:编程之美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;
}