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

37次阅读

共计 1176 个字符,预计需要花费 3 分钟才能阅读完成。

题目:求无符号整数 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;
}

正文完
 0