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








            






            

				

            


    
    







            
	   
	



无码人妻久久一区二区三区蜜桃|
精品久久久久久国产潘金莲|
亚洲国产综合久久天堂
|
久久精品成人影院|
狠狠久久综合伊人不卡|
日本国产精品久久|
久久www免费人成看片|
国产精品天天影视久久综合网|
免费观看成人久久网免费观看|
国产高潮国产高潮久久久91
|
久久久久亚洲av毛片大|
伊人久久久AV老熟妇色|
久久国产欧美日韩精品|
观看 国产综合久久久久鬼色 欧美 亚洲 一区二区
|
久久人人爽人爽人人爽av|
伊人色综合九久久天天蜜桃|
久久精品人人槡人妻人人玩AV|
久久99国产精品久久|
久久婷婷五月综合成人D啪|
亚洲AV无码1区2区久久|
99久久精品九九亚洲精品|
精品国产日韩久久亚洲|
久久精品国内一区二区三区|
欧美伊人久久大香线蕉综合69|
久久久精品2019免费观看|
久久综合视频网站|
嫩草影院久久国产精品|
久久WWW免费人成一看片|
久久国产午夜精品一区二区三区|
人妻无码中文久久久久专区|
久久久久黑人强伦姧人妻|
久久99国产综合精品|
思思久久99热只有频精品66|
国产成人久久精品区一区二区|
久久亚洲天堂|
亚洲国产成人久久精品影视|
久久WWW免费人成一看片|
久久伊人影视|
久久国产精品二国产精品|
AAA级久久久精品无码片|
久久久国产打桩机|