首頁新隨筆新文章聯(lián)系聚合

posts - 149,comments - 125,trackbacks - 0

2009年3月

>

日

一

二

三

四

五

六

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

13

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

常用鏈接

留言簿(9)

隨筆分類(144)

隨筆檔案(149)

文章分類(54)

文章檔案(54)

技術(shù)博客

搜索

積分與排名

積分 - 328712
排名 - 76

閱讀排行榜

評論排行榜

“1”的個數(shù)

這也是《程序員面試攻略》上的一道題，題目是這樣的：
請編寫一個函數(shù)，確定一個整數(shù)的計算機內(nèi)部表示中有幾個“1”。

思索了一下這個題目，我是這樣考慮的，也學(xué)書上給出偽代碼
count = 0;
while (這個整數(shù)不為0)
{
如果這個整數(shù)對2求余的結(jié)果是1，則count加1；
將這個整數(shù)向右移移位
}

代碼寫出來是這樣的：

int numOnesInBinary(int num)

{

int count = 0;

while (num != 0)

{

if (num % 2 == 1)

count++;

num = num>>1;

}

return count;

}

看了一下書中的答案，的確比我簡練很多。對于求余這個方法還是比較笨的。書中采用了邏輯與。

判斷條件從“num%2 == 1”變成 “num&1 == 1”，從程序中更傾向與后者。
所以在分析問題的時候，要學(xué)會用邏輯“與、或、異或”進行判斷。

到這一步，看似已經(jīng)很完美了。但是書中又出奇的給了另一種解法。這種想法我真的沒有想到。

想法的出發(fā)點是考慮一個數(shù)字減1時，它的二進制發(fā)生了什么變化。減1得到的結(jié)果是，從最低位的1到最低位都發(fā)生了翻轉(zhuǎn)，其他高位保持不變。如果您對這個整數(shù)和減一后的結(jié)果進行AND操作，得到的新的數(shù)字與原來的整數(shù)相比，只有最后一個1變成0.

如果進行多次這樣的操作，這個整數(shù)的值變?yōu)?。這樣我們也就獲得了這個數(shù)的計算機表示中“1”的個數(shù)。

int numOnesInBinary2(int num)

{

int count = 0;

while(num != 0)

{

num = num & (num-1);

count++;

}

return count;

}

第一方法的時間復(fù)雜度為o(n)，第二種的時間復(fù)雜度為o(m)，m為1的個數(shù)。

后記：
最近一周多，一直在做這本書上的編程題。一天3道，自己先嘗試編寫，運行成功后再與書上的解答進行對比。稍有幾次略感比書上稍好些。但大多數(shù)情況還是效率差一些。想想原因，還是練得比較少。所以繼續(xù)努力。多多積累，養(yǎng)成良好的思維習(xí)慣。

posted on 2009-07-28 15:56 Sandy 閱讀(726) 評論(3) 編輯收藏引用所屬分類: 面試總結(jié)

FeedBack:

# re: “1”的個數(shù)

2009-08-02 08:21 | codespy

無分支版的你這個快，原理是遞歸求二進位相鄰兩位的和。回復(fù) 更多評論

# re: “1”的個數(shù)

2009-08-02 08:23 | codespy

@codespy
無分支版的比你這個快，原理是遞歸求二進位相鄰兩位的和。回復(fù) 更多評論

# re: “1”的個數(shù)

2009-08-04 11:42 | Sandy

@codespy

這個我還真的沒有想到.
你說的是這種么?
int numOnesInBinary3(int num)
{
num = num - ((num >> 1) & 0x55555555);
num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
num = (num+ (num >> 4)) & 0x0F0F0F0F;
num = num + (num >> 8);
num = num + (num >> 16);
return num & 0x0000003F;
}

我是在http://bvcat007.javaeye.com/blog/203577中看到的,原理是利用二分法，兩兩一組相加，之后四個四個一組相加，接著八個八個，最后就得到各位之和了。

他還提供了一種是
int numOnesInBinary4(int num)
{
unsigned n;
n = (num >> 1) & 033333333333;
num = num - n;
n = (n >> 1) & 033333333333;
num = num - n;
num = (num + (num >> 3)) & 030707070707;
num = num% 63;

return num;
}
首先是將二進制各位三個一組，求出每組中1的個數(shù)，然后相鄰兩組歸并，得到六個一組的1的個數(shù)，最后很巧妙的用除63取余得到了結(jié)果。因為2^6 = 64，也就是說 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，這里的等號表示同余。

回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: 感謝所有幫助我的人轉(zhuǎn)：函數(shù)的線程安全和可重入 “1”的個數(shù) 二面總結(jié) struct 與class的區(qū)別記實習(xí)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(9)

隨筆分類(144)

隨筆檔案(149)

文章分類(54)

文章檔案(54)

技術(shù)博客

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜