• <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


            
	

            


            
	
					


            
	
	這也是《程序員面試攻略》上的一道題，題目是這樣的：
            請編寫一個函數(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 閱讀(698) 評論(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ù)  更多評論
              
            
			
            
			
			
		
            
	








            






            

				

            


    
    







            
	   
	



久久精品99无色码中文字幕|
2020久久精品亚洲热综合一本|
国产A三级久久精品|
蜜臀av性久久久久蜜臀aⅴ麻豆|
久久综合精品国产二区无码|
国产成人精品白浆久久69|
国产综合成人久久大片91|
久久人人爽人人爽人人片av麻烦|
伊人久久大香线蕉亚洲五月天|
国产V综合V亚洲欧美久久|
91精品国产91久久|
精品国产青草久久久久福利|
777米奇久久最新地址|
色偷偷91久久综合噜噜噜噜|
精品久久久无码人妻中文字幕豆芽
|
国产精久久一区二区三区|
久久九九久精品国产|
久久香综合精品久久伊人|
欧美成人免费观看久久|
亚洲精品高清久久|
久久久久久久亚洲Av无码|
久久久久久伊人高潮影院|
精品欧美一区二区三区久久久
|
韩国无遮挡三级久久|
香港aa三级久久三级老师2021国产三级精品三级在
|
欧美噜噜久久久XXX|
日韩中文久久|
久久成人精品|
a级毛片无码兔费真人久久|
久久久婷婷五月亚洲97号色|
久久伊人五月丁香狠狠色|
久久精品这里只有精99品|
国产精品99久久精品爆乳|
久久青草国产手机看片福利盒子|
蜜臀久久99精品久久久久久小说|
国产69精品久久久久观看软件|
久久精品国产精品亚洲艾草网美妙
|
蜜臀av性久久久久蜜臀aⅴ|
伊人久久大香线蕉av不卡|
久久久无码精品亚洲日韩蜜臀浪潮|
久久国产精品二国产精品|