快捷導(dǎo)航

二進(jìn)制中1的個(gè)數(shù)

更新時(shí)間：2013年09月27日 16:24:05 作者：

這篇文章介紹了二進(jìn)制中1的個(gè)數(shù)，有需要的朋友可以參考一下

前言
最近會(huì)手寫一些常考的面試題目，測(cè)試通過(guò)后會(huì)跟大家分享一下

移位法
僅適應(yīng)于正數(shù)的做法：

移位法就是每次判斷n的二進(jìn)制的最低位是否為1,時(shí)間復(fù)雜度為O(logn)

復(fù)制代碼代碼如下:

int nativeOnenum(int n)   
{   
    int count = 0;   

    while (n) {   
        if (n & 1)  count ++;   
        n >>= 1;   
    }   

    return count;   
}

對(duì)于正數(shù)沒(méi)問(wèn)題，但是如果n為負(fù)數(shù)，這里就出現(xiàn)問(wèn)題了，以負(fù)數(shù)-8為例，二進(jìn)制補(bǔ)碼形式為11111111|11111111|11111111|11111000|,右移一位之后，變成了11111111|11111111|11111111|11111100|,因?yàn)槭秦?fù)數(shù)，所以符號(hào)位會(huì)一直補(bǔ)1,導(dǎo)致最后全1,出現(xiàn)死循環(huán)

針對(duì)這種情況，我們可以用變量flag =1,從右向左去和n比較，32位int最多比較32次即可知道n中1的數(shù)量

復(fù)制代碼代碼如下:

int oneNum(int n)   
{   
    int count, flag;   

    for (count = 0, flag = 1; flag; flag <<= 1) {   
        if (flag & n)   count ++;   
    }   

    return count;   
}

快速法
這種解法的思路是，二進(jìn)制中1的個(gè)數(shù)只與1的位數(shù)有關(guān)，n & (n - 1)快速的去掉最左邊的1，例如7（0111） & 6（0110）= 6（0110）,快速的去掉了最左邊的1

復(fù)制代碼代碼如下:

int quickOne(int n)   
{   
    int count = 0;   

    while (n) {   
        count ++;   
        n = n & (n - 1);   
    }   

    return count;   
}

相關(guān)文章

解決Maven項(xiàng)目中 Invalid bound statement 無(wú)效的綁定問(wèn)題
這篇文章主要介紹了解決Maven項(xiàng)目中 Invalid bound statement 無(wú)效的綁定問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2021-06-06
Java操作pdf文件的方法大全
這篇文章主要為大家詳細(xì)介紹了Java操作pdf文件的相關(guān)知識(shí)，例如合并pdf文件，手繪pdf文件以及導(dǎo)出PDF文件等，有需要的小伙伴可以參考一下
2024-04-04
如何發(fā)布jar包到maven中央倉(cāng)庫(kù)
這篇文章主要介紹了發(fā)布jar包到maven中央倉(cāng)庫(kù)的相關(guān)知識(shí),本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友參考下吧
2023-12-12
SpringBoot集成tika實(shí)現(xiàn)word轉(zhuǎn)html的操作代碼
Tika是一個(gè)內(nèi)容分析工具,自帶全面的parser工具類,能解析基本所有常見(jiàn)格式的文件,得到文件的metadata,content等內(nèi)容,返回格式化信息,本文給大家介紹了SpringBoot集成tika實(shí)現(xiàn)word轉(zhuǎn)html的操作,需要的朋友可以參考下
2024-06-06
Trace?在多線程異步體系下傳遞流程解析
這篇文章主要為大家介紹了Trace?在多線程異步體系下傳遞流程解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
2023-12-12
mybatis配置mapper-locations位置的三種方式小結(jié)
這篇文章主要給大家介紹了關(guān)于mybatis配置mapper-locations位置的三種方式,Mybatis-Plus的初衷是為了簡(jiǎn)化開(kāi)發(fā),而不建議開(kāi)發(fā)者自己寫SQL語(yǔ)句的,但是有時(shí)客戶需求比較復(fù)雜,需要的朋友可以參考下
2023-08-08
Java?web訪問(wèn)http://localhost:8080/xx/xx.jsp報(bào)404錯(cuò)誤問(wèn)題的解決方法
這篇文章主要給大家介紹了關(guān)于Java?web訪問(wèn)http://localhost:8080/xx/xx.jsp報(bào)404錯(cuò)誤問(wèn)題的解決方法,很多小伙伴在剛開(kāi)始用Springboot整合jsp開(kāi)發(fā)時(shí)都會(huì)遇到這個(gè)問(wèn)題, 按照別人的教程一步一步搭建,但就是會(huì)報(bào)404,文中介紹的非常詳細(xì),需要的朋友可以參考下
2023-04-04
Java程序?qū)崿F(xiàn)導(dǎo)出Excel的方法(支持IE低版本)
下面小編就為大家?guī)?lái)一篇Java程序?qū)崿F(xiàn)導(dǎo)出Excel的方法(支持IE低版本)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2016-07-07
java報(bào)錯(cuò):找不到或無(wú)法加載主類的解決方法簡(jiǎn)單粗暴
本文主要介紹了java報(bào)錯(cuò):找不到或無(wú)法加載主類的解決方法簡(jiǎn)單粗暴，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2023-01-01
Java中引用類型之強(qiáng)引用、軟引用、弱引用和虛引用詳解
這篇文章主要介紹了Java中引用類型之強(qiáng)引用、軟引用、弱引用和虛引用的相關(guān)資料,通過(guò)實(shí)際代碼示例,展示了如何利用引用隊(duì)列來(lái)跟蹤對(duì)象的回收狀態(tài),并實(shí)現(xiàn)資源的自動(dòng)清理,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下
2025-03-03