• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            

            
	
	


            
	
            
		春暖花開
            
		雪化了，花開了，春天來了
	
            

            
            		
	

            

            


            
	
		
            
			


            
posts - 149,comments - 125,trackbacks - 0


            
	

            


            
	
					


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

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

            代碼寫出來是這樣的：
            

            int numOnesInBinary(int num)
            {
                            int count = 0;
                            while (num != 0)
                            {
                                if (num % 2 == 1)
                        count            ++;
                    num             = num>>1;
                }

                            return count;
            }
            

            看了一下書中的答案，的確比我簡(jiǎn)練很多。對(duì)于求余這個(gè)方法還是比較笨的。書中采用了邏輯與。

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

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

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

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

            

            int numOnesInBinary2(int num)
            {
                            int count = 0;
                            while(num != 0)
                            {
                    num             = num & (num-1);
                    count            ++;
                }
                            return count;
            }
            


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

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

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

            







            
	    
    


            
FeedBack:

            
	

		
            
			
            # re: “1”的個(gè)數(shù)
            
			
            
				2009-08-02 08:21 | codespy
            
				
            無分支版的你這個(gè)快，原理是遞歸求二進(jìn)位相鄰兩位的和。  回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: “1”的個(gè)數(shù)
            
			
            
				2009-08-02 08:23 | codespy
            
				
            @codespy

            無分支版的 比 你這個(gè)快，原理是遞歸求二進(jìn)位相鄰兩位的和。  回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: “1”的個(gè)數(shù)
            
			
            
				2009-08-04 11:42 | Sandy
            
				
            @codespy

            

            這個(gè)我還真的沒有想到.

            你說的是這種么?

            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中看到的,原理是利用二分法，兩兩一組相加，之后四個(gè)四個(gè)一組相加，接著八個(gè)八個(gè)，最后就得到各位之和了。

            

            他還提供了一種是

            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;

            }

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

            

              回復(fù)  更多評(píng)論
              
            
			
            
			
			
		
            
	








            






            

				

            


    
    







            
	   
	



99999久久久久久亚洲|
狠狠久久综合伊人不卡|
久久久久久久波多野结衣高潮
|
久久AⅤ人妻少妇嫩草影院|
亚洲国产精品嫩草影院久久
|
日韩精品久久久久久久电影蜜臀|
久久99精品久久久久久齐齐|
色婷婷久久综合中文久久一本|
久久免费的精品国产V∧|
久久精品视频一|
亚洲精品蜜桃久久久久久|
久久久久亚洲精品无码网址|
国产精品免费看久久久香蕉|
久久精品成人免费国产片小草|
99热成人精品免费久久|
午夜人妻久久久久久久久|
久久中文字幕视频、最近更新|
久久精品一区二区国产|
噜噜噜色噜噜噜久久|
久久亚洲欧洲国产综合|
久久久国产亚洲精品|
久久人人爽人人爽人人片AV不|
亚洲国产精品嫩草影院久久|
亚洲精品99久久久久中文字幕
|
国产精自产拍久久久久久蜜|
久久激情亚洲精品无码?V|
国产成人精品久久一区二区三区av|
久久九九青青国产精品|
久久精品女人天堂AV麻|
久久国产劲爆AV内射—百度|
久久亚洲私人国产精品|
青草影院天堂男人久久|
亚洲国产高清精品线久久
|
国内精品伊人久久久久|
91久久香蕉国产熟女线看|
亚洲va久久久噜噜噜久久|
国产午夜电影久久|
精品国产日韩久久亚洲|
久久人人爽人人爽人人av东京热|
久久99精品久久久久子伦|
久久国产亚洲高清观看|