行文脈絡(luò)

1. 解法一——除法
2. 解法二——移位
3. 解法三——高效移位
4. 解法四——查表
5. 擴(kuò)展問題——異或后轉(zhuǎn)化為該問題

?

對于一個(gè)字節(jié)（8bit）的變量，求其二進(jìn)制“1”的個(gè)數(shù)。例如6（二進(jìn)制0000 0110）“1”的個(gè)數(shù)為2，要求算法效率盡量高。

解法一

對于二進(jìn)制數(shù)來說，除一個(gè)2，就少一位，可以判斷這個(gè)少的位來確定“1”的個(gè)數(shù)。

例如：6（0000 0110）

0000 0110 / 2 = 0000 0011 ? ? ----少的一位為0

0000 0011 / 2 = 0000 0001 ? ? ----少的一位為1

0000 0001 / 2 = 0000 0000 ? ? ----少的一位為1

操作數(shù)數(shù)已經(jīng)為0，到此結(jié)束

參考代碼

int Count_1(int val)
{int num = 0;while(val){if(val % 2 != 0)   //用取模獲得去除的一位++num;val /= 2;}return num;
}

性能：時(shí)間復(fù)雜度O(log₂v)，即二進(jìn)制數(shù)的位數(shù)；空間復(fù)雜度O(1)

?

解法二

對于二進(jìn)制數(shù)來說，除法是用移位完成。

例如：6（0000 0110）

0000 0110 >> 1 = 0000 0011 ? ? ----少的一位為0

0000 0011 >> 1 = 0000 0001 ? ? ----少的一位為1

0000 0001 >> 1 = 0000 0000 ? ? ----少的一位為1

操作數(shù)數(shù)已經(jīng)為0，到此結(jié)束

參考代碼

int Count_2(int val)
{int num = 0;while(val){if(val & 1 != 0)   //用與1與獲得移除的一位++num;val >>= 1;}return num;
}

性能：時(shí)間復(fù)雜度O(log₂v)，即二進(jìn)制數(shù)的位數(shù)；空間復(fù)雜度O(1)

?

解法三

對于上述算法，有個(gè)問題，比如1000 0000，大把的時(shí)間用在沒用的0上，最好尋求一種直接判斷“1的個(gè)數(shù)。

通過觀察可以找到規(guī)律：對于數(shù)a, a = a & (a-1)就可以去除a的最后一個(gè)1

例如：6（0000 0110）

0000 0110 & 0000 0101 = 0000 0100 ? ??

0000 0100 & 0000 0011?= 0000 0000

操作數(shù)數(shù)已經(jīng)為0，到此結(jié)束

參考代碼

int Count_3(int val)
{int num = 0;while(val){val &= (val -1);++num;}return num;
}

性能：時(shí)間復(fù)雜度O(M)，即二進(jìn)制中“1”的個(gè)數(shù)，空間復(fù)雜度O(1)

?

解法四

查表法，把0~255這256個(gè)數(shù)的結(jié)果全部存儲在數(shù)組中，val直接作為下標(biāo)，countTable[val]即為結(jié)果。典型的用空間換時(shí)間。

參考代碼

int Count_5(int val)
{int countTable[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};return countTable[val];
}

性能：時(shí)間復(fù)雜度：O(1), 空間復(fù)雜度O(N)

?

整個(gè)程序執(zhí)行參考

#include<iostream>
using namespace std;int Count_1(int val)
{int num = 0;while(val){if(val % 2 != 0)++num;val /= 2;}return num;
}int Count_2(int val)
{int num = 0;while(val){if(val & 1 != 0)++num;val >>= 1;}return num;
}int Count_3(int val)
{int num = 0;while(val){val &= (val -1);++num;}return num;
}
int Count_5(int val)
{int countTable[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};return countTable[val];
}int main()
{int a = 6, b = 255;cout << "Num of 1:" << Count_1(a) << endl; cout << "Num of 1:" << Count_2(a) << endl; cout << "Num of 1:" << Count_3(a) << endl; cout << "Num of 1:" << Count_5(b) << endl; cout << "Num of 1:" << Count_1(b) << endl; cout << "Num of 1:" << Count_2(b) << endl; cout << "Num of 1:" << Count_3(b) << endl; cout << "Num of 1:" << Count_5(b) << endl; 
}

View Code

結(jié)果

?

擴(kuò)展問題

1. 給定兩個(gè)正整數(shù)（二進(jìn)制表示）A、B，如何快速找出A和B二進(jìn)制表示中不同位數(shù)的個(gè)數(shù)。

　　思路

　　首先A和B進(jìn)行異或操作，然后求得到的結(jié)果中1的個(gè)數(shù)（此問題）。

2. 判斷一個(gè)數(shù)是否是2的冪

bool powerof2(int n)
{return ((n & (n-1)) == 0);
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/kaituorensheng/p/3562076.html

總結(jié)

以上是生活随笔為你收集整理的求二进制中1的个数（编程之美2.1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。