問題：計(jì)算某個(gè)數(shù)的二進(jìn)制中1的個(gè)數(shù)

站在用戶的角度思考問題，與客戶深入溝通，找到龍江網(wǎng)站設(shè)計(jì)與龍江網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站建設(shè)、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名與空間、虛擬空間、企業(yè)郵箱。業(yè)務(wù)覆蓋龍江地區(qū)。

思路：x = x & (x-1) 將 x 的二進(jìn)制最右面的一個(gè) 1 變?yōu)?0，其余保持不變。反復(fù)操作，直到變?yōu)?0 為止，計(jì)算操作次數(shù)，即為 x 的二進(jìn)制中 1 的個(gè)數(shù)。

證明：假設(shè) x 的二進(jìn)制末尾為 10...0 [末尾有 k 個(gè) 0，k = 0,1,2,...]。

則 x - 1 的二進(jìn)制末尾 k+1 位為 01...1 [末尾有 k 個(gè) 1，k = 0,1,2,...]，其他與 x 相同。

從而 x & (x-1) 的末尾 k+1 位為 00...0 [末尾有 k+1 個(gè) 0，k = 0,1,2,...]，其他與 x 相同。

即 x = x & (x-1) 將 x 的最右邊的一個(gè) 1 變?yōu)?0，其余位數(shù)無變化。

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 的二進(jìn)制最右面的一個(gè) 0 變?yōu)?1，其余保持不變。
證明：假設(shè) x 的二進(jìn)制末尾為 01...1 [末尾有 k 個(gè) 1，k = 0,1,2,...]。
則 x + 1 的二進(jìn)制末尾 k+1 位為 10...0 [末尾有 k 個(gè) 0，k = 0,1,2,...]，其他與 x 相同。
從而 x | (x+1) 的末尾 k+1 位為 11...1 [末尾有 k+1 個(gè) 1，k = 0,1,2,...]，其他與 x 相同。
即 x = x | (x+1) 將 x 的最右邊的一個(gè) 0 變?yōu)?1，其余位數(shù)無變化。
應(yīng)用：判斷一個(gè)整數(shù) x 是否為 2 的冪。
思路：假如 x 為 2 的冪，則 x 只有最高位為 1，其余均為 0，因此按照上面的做法 x = x & (x-1) 將會(huì)為 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<            
            
                        

            本文名稱：計(jì)算二進(jìn)制中1的個(gè)數(shù)            

            分享URL：http://weahome.cn/article/jgpjsi.html