如何判斷一個整數(shù)的二進制中有多少個1
更新時間：2013年05月28日 15:45:53 作者：
本篇文章是對如何判斷一個整數(shù)的二進制中有多少個1的方法進行了詳細的分析介紹，需要的朋友參考下
復制代碼 代碼如下:
// 判斷一個整數(shù)的二進制位中有多少個1
void totalOne(int x)
{
int count = 0;
while(x)
{
x = x & ( x - 1 );
count++;
}
printf("count = %d/n", count);
}
循環(huán)： x = x & ( x - 1 ); count++; 直到x為0為止。該方法的時間復雜度是O(m)
在此，不妨把x的二進制位表示為
x=an-1an-2...a0。
按從低位到高位的順序，不失一般性，假設x的第i位為第一個為1的二進制位，即：ai=1。此時有：
x =an-1an-2...ai+1100...0 <1>
(x-1) =an-1an-2...ai+1011...1 <2>
很明顯，從式1和式2可以得出，在第一次 x & (x-1) 后：
x=an-1an-2...ai+1000...0
之后重復同樣操作，直到x的二進制位中沒有1為止
從上面可以看出，每執(zhí)行過一次 x & (x-1) 后，都會將x的二進制位中為1的最低位的值變?yōu)?，并記數(shù)加1。
目前而言，一個整數(shù)最大64bit，所有三種方法執(zhí)行起來都可以認為是0(1)。
相關文章
靜態(tài)鏈接庫.lib和動態(tài)鏈接庫.dll。其中動態(tài)鏈接庫在被使用的時候，通常還提供一個.lib，稱為引入庫，它主要提供被Dll導出的函數(shù)和符號名稱，使得鏈接的時候能夠找到dll中對應的函數(shù)映射2012-11-11
本文將詳細介紹NSString與C字符串之間的相互轉換，需要的朋友可以參考下2012-11-11
這篇文章主要介紹了C++如何調(diào)用簡單的python程序問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要介紹了C++&&Opencv實現(xiàn)控制臺字符動畫的方法，本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-07-07
在C#中要說類默認給我們定義的特殊成員函數(shù)，莫過于構造函數(shù)，但在?C++?中這樣的特殊函數(shù)高達6種，本文就整合一下和大家一起聊一聊2022-07-07
這篇文章主要介紹了C++編譯/編輯器對OIer的必要功能，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04
Cmake主要用于開發(fā)跨平臺的C++項目，本文主要介紹了CMake語法及CMakeList.txt簡單使用小結，具有一定的參考價值，感興趣的可以了解一下2022-05-05
本文將詳細介紹c++容器簡介,c++容器的比較 與操作實例，需要了解更多的朋友可以參考下2012-11-11
這篇文章主要為大家詳細介紹了C語言中const和指針的秘密，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
今天小編就為大家分享一篇關于C++中new和delete的介紹，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12