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