二進(jìn)制中1的個(gè)數(shù)
更新時(shí)間：2013年09月27日 16:24:05 作者：
這篇文章介紹了二進(jìn)制中1的個(gè)數(shù)，有需要的朋友可以參考一下
前言
最近會(huì)手寫一些?？嫉拿嬖囶}目，測(cè)試通過后會(huì)跟大家分享一下
移位法
僅適應(yīng)于正數(shù)的做法：
移位法就是每次判斷n的二進(jìn)制的最低位是否為1,時(shí)間復(fù)雜度為O(logn)
int nativeOnenum(int n)
{
int count = 0;
while (n) {
if (n & 1) count ++;
n >>= 1;
}
return count;
}
對(duì)于正數(shù)沒問題，但是如果n為負(fù)數(shù)，這里就出現(xià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ù)量
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
int quickOne(int n)
{
int count = 0;
while (n) {
count ++;
n = n & (n - 1);
}
return count;
}
最近會(huì)手寫一些?？嫉拿嬖囶}目，測(cè)試通過后會(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ù)沒問題，但是如果n為負(fù)數(shù)，這里就出現(xià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)文章
Java中java.lang.ClassCastException異常原因以及解決方法詳解
這篇文章主要給大家介紹了關(guān)于Java中java.lang.ClassCastException異常原因以及解決方法的相關(guān)資料,ClassCastException從字面上看是類型轉(zhuǎn)換錯(cuò)誤,通常是進(jìn)行強(qiáng)制類型轉(zhuǎn)換時(shí)候出的錯(cuò)誤,需要的朋友可以參考下2024-02-02
iReport是一個(gè)能夠創(chuàng)建復(fù)雜報(bào)表的開源項(xiàng)目，它100%使用Java語(yǔ)言編寫，是目前全球最為流行的開源報(bào)表設(shè)計(jì)器，由于它豐富的圖形界面，你能夠很快的創(chuàng)建出任何一種你想要的報(bào)表2021-10-10
這篇文章主要介紹了java中的插入排序，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-08-08
IDEA?2020.3最新永久激活碼(免費(fèi)激活到?2099?年,親測(cè)有效)
分享一下?IntelliJ?IDEA?2020.3.1?最新激活注冊(cè)碼，破解教程如下，可免費(fèi)激活至?2099?年，親測(cè)有效，本文給大家分享兩種方法，感興趣的朋友參考下吧2021-01-01
這篇文章主要介紹了SpringBoot使用JSP作為視圖模板的方法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧2018-08-08
這篇文章主要介紹了使用JPA自定義SQL查詢結(jié)果，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-11-11
本篇文章主要介紹了SpringCloud之Feign示例詳解，詳細(xì)的介紹了Feign簡(jiǎn)介和使用，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧2018-01-01
小編最近的工作中遇到了一些知識(shí)圖譜的工作，自然就用到了圖數(shù)據(jù)庫(kù)，這一NoSQL?數(shù)據(jù)庫(kù)可以很好的展示節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系，對(duì)于一些圖譜的關(guān)系操作是很好的選擇，下面來(lái)介紹下?Springboot?配置Neo4J的問題2021-12-12
Spring依賴注入Dependency Injection的三種方式
依賴注入(Dependency Injection)和控制反轉(zhuǎn)(Inversion of Control)是同一個(gè)概念。具體含義是:當(dāng)某個(gè)角色(可能是一個(gè)Java實(shí)例，調(diào)用者)需要另一個(gè)角色(另一個(gè)Java實(shí)例，被調(diào)用者)的協(xié)助時(shí)，在傳統(tǒng)的程序設(shè)計(jì)過程中，通常由調(diào)用者來(lái)創(chuàng)建被調(diào)用者的實(shí)例2023-02-02
Java實(shí)現(xiàn)Redis分布式鎖的三種方案匯總
setnx、Redisson、RedLock?都可以實(shí)現(xiàn)分布式鎖,從易到難得排序?yàn)椋簊etnx?<?Redisson?<?RedLock,本文為大家整理了三種方法的實(shí)現(xiàn),希望對(duì)大家有所幫助2023-11-11