计算二进制中1的个数-创新互联

问题：计算某个数的二进制中1的个数

思路：x = x & (x-1) 将 x 的二进制最右面的一个 1 变为 0，其余保持不变。反复操作，直到变为 0 为止，计算操作次数，即为 x 的二进制中 1 的个数。

证明：假设 x 的二进制末尾为 10...0 [末尾有 k 个 0，k = 0,1,2,...]。

则 x - 1 的二进制末尾 k+1 位为 01...1 [末尾有 k 个 1，k = 0,1,2,...]，其他与 x 相同。

从而 x & (x-1) 的末尾 k+1 位为 00...0 [末尾有 k+1 个 0，k = 0,1,2,...]，其他与 x 相同。

即 x = x & (x-1) 将 x 的最右边的一个 1 变为 0，其余位数无变化。

C++程序：

#include 
using namespace std;

int manyOne(int x){
    int countx = 0;
    while(x){
        ++countx;
        x = x&(x-1);
    }
    return countx;
}

int main(){
    cout<
类似问题：x = x | (x+1) 将 x 的二进制最右面的一个 0 变为 1，其余保持不变。
证明：假设 x 的二进制末尾为 01...1 [末尾有 k 个 1，k = 0,1,2,...]。
则 x + 1 的二进制末尾 k+1 位为 10...0 [末尾有 k 个 0，k = 0,1,2,...]，其他与 x 相同。
从而 x | (x+1) 的末尾 k+1 位为 11...1 [末尾有 k+1 个 1，k = 0,1,2,...]，其他与 x 相同。
即 x = x | (x+1) 将 x 的最右边的一个 0 变为 1，其余位数无变化。
应用：判断一个整数 x 是否为 2 的幂。
思路：假如 x 为 2 的幂，则 x 只有最高位为 1，其余均为 0，因此按照上面的做法 x = x & (x-1) 将会为 0；反之，假如 x = x & (x-1) 为 0，则 x 只有一位为 1，其余均为 0，显然 x 为 2 的幂。
C++程序：
#include 
using namespace std;
int isTwoPow(int x){
    if( (x&(x-1)) == 0) return 1;
    else return 0;
} 
int main(){
    cout<
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            当前名称：计算二进制中1的个数-创新互联            

            文章地址：http://cxhlcq.com/article/cdhijh.html