資訊專欄INFORMATION COLUMN
摘要：題目輸入一個(gè)數(shù)不管是幾進(jìn)制，輸出這個(gè)數(shù)二進(jìn)制表示中的個(gè)數(shù)。代碼如下相當(dāng)于這個(gè)解法中循環(huán)次數(shù)等于目標(biāo)整數(shù)二進(jìn)制的位數(shù)，位整數(shù)就需要循環(huán)次，方案三給出目標(biāo)整數(shù)中有幾個(gè)就只循環(huán)幾次的方案。舉個(gè)例子一個(gè)二進(jìn)制數(shù)，從右邊數(shù)起第三位是處于最右邊的一個(gè)。
題目：輸入一個(gè)數(shù)（不管是幾進(jìn)制），輸出這個(gè)數(shù)二進(jìn)制表示中1的個(gè)數(shù)。比如輸入 9 應(yīng)該輸出 2 ；輸入0x1F（31） 應(yīng)該輸出 5 。（16進(jìn)制表示是在前面加 0x ）
方案一：
我最開始的想法是把這個(gè)數(shù)轉(zhuǎn)化成二進(jìn)制，因?yàn)橹白鲞^十進(jìn)制轉(zhuǎn)二進(jìn)制所以理所應(yīng)當(dāng)?shù)倪@么想了，最后感覺不太對，要這么寫那的寫幾個(gè)進(jìn)制轉(zhuǎn)換類啊，而且效率不高。
方案二：
然后看了一下書，書上的做法很巧妙：先查看目標(biāo)數(shù)字末尾位是0還是1，這可以通過與一個(gè)1做與運(yùn)算得到結(jié)果，然后把目標(biāo)數(shù)字右移一位，繼續(xù)與1做與，聲明一個(gè)計(jì)數(shù)器count，持續(xù)加就好。
不過也給出了缺陷，缺陷在于如果目標(biāo)數(shù)字是負(fù)數(shù)（負(fù)數(shù)的符號位也要算進(jìn)總的1的個(gè)數(shù)里）不光沒法的到正確結(jié)果，還會讓陷入死循環(huán)：把負(fù)數(shù)0x8000右移一位，其實(shí)是變成了0xc000，多移幾次就變成0xffff然后
死循環(huán)了，因?yàn)樽笠坪陀乙剖腔谶@樣的原則：
左移時(shí)最左邊的n位被丟棄，同時(shí)在最右邊補(bǔ)上n個(gè)0。
右移時(shí)如果是正數(shù)補(bǔ)0，負(fù)數(shù)在最左邊補(bǔ)1.
所以更新方案：把1左移，循環(huán)一次就左移一次，這樣目標(biāo)數(shù)每一位的1就都不會放過，與運(yùn)算每得到一個(gè)1就count++。反正最后1移到最后就溢出了變成0000000000，這就是循環(huán)中止條件。
代碼如下：
public class Jianzhi{
public static void main(String[] args){
int num = 0xFF ; //相當(dāng)于int num = 31 ;
int flag = 1 ;
int count = 0 ;
while( flag != 0 ){
if( (num&flag) != 0 ){
count++ ;
}
flag = flag << 1 ;
}
System.out.print(count);
}
}
這個(gè)解法中循環(huán)次數(shù)等于目標(biāo)整數(shù)二進(jìn)制的位數(shù)，32位整數(shù)就需要循環(huán)32次，方案三給出目標(biāo)整數(shù)中有幾個(gè)1就只循環(huán)幾次的方案。
方案三：
如果一個(gè)整數(shù)不為0，那么這個(gè)整數(shù)至少有一位是1。如果我們把這個(gè)整數(shù)減1，那么原來處在整數(shù)最右邊的1就會變?yōu)?，原來在1后面的所有的0都會變成1(如果最右邊的1后面還有0的話)。其余所有位將不會受到影響。
舉個(gè)例子：一個(gè)二進(jìn)制數(shù)1100，從右邊數(shù)起第三位是處于最右邊的一個(gè)1。減去1后，第三位變成0，它后面的兩位0變成了1，而前面的1保持不變，因此得到的結(jié)果是1011.我們發(fā)現(xiàn)減1的結(jié)果是把最右邊的一個(gè)1開始的所有位都取反了。這個(gè)時(shí)候如果我們再把原來的整數(shù)和減去1之后的結(jié)果做與運(yùn)算，從原來整數(shù)最右邊一個(gè)1那一位開始所有位都會變成0。如1100&1011=1000.也就是說，把一個(gè)整數(shù)減去1，再和原整數(shù)做與運(yùn)算，會把該整數(shù)最右邊一個(gè)1變成0.那么一個(gè)整數(shù)的二進(jìn)制有多少個(gè)1，就可以進(jìn)行多少次這樣的操作。
基于這種思想有如下代碼：
public class Jianzhi{
public static void main(String[] args){
int num = 0xFF ; //相當(dāng)于int num = 31 ;
int flag = num-1 ;
int count = 0 ;
while(num != 0 ){
num = num & flag ;
flag = num - 1 ;
count ++ ;
}
System.out.print(count);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71395.html
摘要：圖解第二種算法圖解代碼示例算法如果為真，說明拿到的是二進(jìn)制序列的個(gè)數(shù)為算法為的時(shí)候說明已經(jīng)拿完了，循環(huán)終止二進(jìn)制序列中的個(gè)數(shù)以上代碼，還可做優(yōu)化在此僅作參考，若有更好的算法，還望能夠私信告知，多謝各位。 ?前言?： 算法是一個(gè)程序員的內(nèi)功，能很好的體現(xiàn)程序員的編程思維，通過學(xué)習(xí)和掌握常見的算...
摘要：問題描述輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。思路方法將二進(jìn)制變成字符數(shù)組，遍歷數(shù)組統(tǒng)計(jì)的個(gè)數(shù)，這種辦法不需要考慮正負(fù)數(shù)。遍歷字符數(shù)組，統(tǒng)計(jì)的個(gè)數(shù)判斷該位是否是，如果是就，否則執(zhí)行下一次循環(huán)。的二進(jìn)制表示想右移一位。 1.問題描述 輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。 2.思路 方法1：將二進(jìn)制變成字符數(shù)組，遍歷數(shù)組統(tǒng)計(jì)1的個(gè)數(shù)，這...
摘要：長話短說，讓我們來看一道題統(tǒng)計(jì)的個(gè)數(shù)給定一個(gè)非負(fù)整數(shù)，對于任意，，計(jì)算的值對應(yīng)的二進(jìn)制數(shù)中的個(gè)數(shù)，將這些結(jié)果返回為一個(gè)數(shù)組。第二版本的時(shí)間復(fù)雜度是最后版本的時(shí)間復(fù)雜度是，是的二進(jìn)制數(shù)中的的個(gè)數(shù)，介于之間。 小胡子哥@Barret李靖給我推薦了一個(gè)寫算法刷題的地方leetcode.com，沒有ACM那么難，但題目很有趣。而且據(jù)說這些題目都來源于一些公司的面試題。好吧，解解別人公司的面試題...
閱讀 3843·2021-11-25 09:43
閱讀 2184·2021-11-23 10:11
閱讀 1413·2021-09-29 09:35
閱讀 1359·2021-09-24 10:31
閱讀 2048·2019-08-30 15:48
閱讀 2366·2019-08-29 15:28
閱讀 439·2019-08-29 12:36
閱讀 3499·2019-08-28 18:12
