• <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ù)  更多評論
              
            
			
            
			
			
		
            
	








            






            

				

            


    
    







            
	   
	



欧美精品一本久久男人的天堂|
久久久久久久人妻无码中文字幕爆|
MM131亚洲国产美女久久|
亚洲AV无码久久精品色欲|
久久久久久伊人高潮影院|
思思久久99热只有频精品66|
人妻无码αv中文字幕久久|
国产国产成人久久精品|
精品久久久久久亚洲|
伊人久久大香线蕉av不卡|
99久久国产亚洲高清观看2024
|
欧美日韩久久中文字幕|
99久久精品这里只有精品|
99久久精品九九亚洲精品|
国产午夜电影久久|
精品熟女少妇aⅴ免费久久|
久久国产热精品波多野结衣AV|
亚洲国产小视频精品久久久三级
|
精品久久久久久国产牛牛app|
久久国产精品成人片免费|
嫩草伊人久久精品少妇AV|
国产成人精品久久二区二区|
日本久久久精品中文字幕|
久久毛片免费看一区二区三区|
色狠狠久久综合网|
精品久久久久久成人AV|
人人狠狠综合久久亚洲|
99久久精品国产麻豆|
99久久做夜夜爱天天做精品|
国产精品一区二区久久|
亚洲中文字幕久久精品无码APP|
久久狠狠高潮亚洲精品|
亚洲色欲久久久综合网|
国产女人aaa级久久久级|
久久久久久久女国产乱让韩|
青青草原综合久久大伊人精品|
久久国产影院|
日本人妻丰满熟妇久久久久久|
蜜臀av性久久久久蜜臀aⅴ|
99精品国产99久久久久久97|
成人综合久久精品色婷婷|