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

    
            

            




            







												


        


            

            
	
	


            
	
            
		OnTheWay2012
            
		埋葬昨天的我，迎來重生的我！
	
            

            
            		
	

            

            


            
	
		
            
			


            
posts - 15, 
comments - 89, 
trackbacks - 0


            
	

            

            
	
					


            
	
	
            求一個unsigned int 數的二進制表示中有多少個1？
            這是一道面試題可以用以下的一些方案。
            第一種是很容易想到的采用循環的方式并且與1進行位與運算，具體代碼如下。
            

             1unsigned int GetBitNumOfOne_ByLoop1(unsigned int nValue)
             2{
             3 const unsigned int nNumOfBitInByte = 8;
             4 unsigned int nBitMask = 1;
             5 unsigned int nBitNum = 0;
             6 for(unsigned int i = 0 ; i < sizeof(nValue) * nNumOfBitInByte ; i++)
             7 {
             8  (0 < (nValue & nBitMask)) ? nBitNum++ : 0;
             9  nBitMask<<=1;
            10 }
            11 return nBitNum;
            12}
            13unsigned int GetBitNumOfOne_ByLoop2(unsigned int nValue)
            14{
            15 const unsigned int nNumOfBitInByte = 8;
            16 unsigned int nBitMask = 1;
            17 unsigned int nBitNum = 0;
            18 for(unsigned int i = 0 ; i < sizeof(nValue) * nNumOfBitInByte ; i++)
            19 {
            20  (0 < (nValue & nBitMask)) ? nBitNum++ : 0;
            21  nValue>>=1;
            22 }
            23 return nBitNum;
            24}
            

            這兩種做法很相像，卻別就是在是對nBitMask進行左移還是對nValue進行右移。
            當然了以上的兩個方法存在一個問題：不管如何這個函數肯定要循環32次（對于32平臺來說）。
            那又沒有更好的方法？當然有，請看下面：
            

             1unsigned int GetBitNumOfOne_ByLoop3(unsigned int nValue)
             2{
             3 unsigned int nBitNum = 0;
             4 while(0 < nValue)
             5 {
             6  nValue &=(nValue - 1);
             7  nBitNum++;
             8 }
             9 return nBitNum;
            10}
            

            假如使用參數12345（二進制是11000000111001）調用該函數，該函數的執行情況如下：
            第一次進入循環
            0 < 11000000111001
            11000000111001 &= (11000000111001 - 1) 之后 nValue 的值 是 11000000111000
            nBitNum 的值是1
            經過本次循環之后11000000111001 變成了 11000000111000 比之前少了一個1
            第二次進入循環
            0 < 11000000111000
            11000000111000 &= (11000000111000 - 1) 之后 nValue 的值 是 11000000110000
            nBitNum 的值是2
            經過本次循環之后11000000111000 變成了 11000000110000 比之前少了一個1
            第三次進入循環
            0 < 11000000110000
            11000000110000 &= (11000000110000 - 1) 之后 nValue 的值 是 11000000100000
            nBitNum 的值是3
            經過本次循環之后11000000110000 變成了 11000000100000 比之前少了一個1
            經過以上3次循環情況的說明，我相信你一定看出了些什么吧。nValue &=(nValue - 1)，這句
            代碼實際上就是把nValue 的某位及其以后的所有位都變成0，當nValue最后變成0的時候循環結束，
            且nBitNum 記錄的就是1的個數。
            上面的做法已經很不錯了，但是作為程序員的你是否會有疑問，“還有其他的方法嗎？”。
            有，當然有！請看下面的代碼：
            

             1unsigned int GetBitNumOfOne(unsigned int nValue)
             2{
             3 nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
             4 nValue = ((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
             5 nValue = ((0xf0f0f0f0 & nValue)>>4) + (0x0f0f0f0f & nValue);
             6 nValue = ((0xff00ff00 & nValue)>>8) + (0x00ff00ff & nValue);
             7 nValue = ((0xffff0000 & nValue)>>16) + (0x0000ffff & nValue);
             8 
             9 return nValue;
            10}
            


            假如你是第一次看到這些代碼，你是否能看明白？呵呵，本人第一次看到這些代碼的時候看了好久才感覺
            好像有點明白。下面我就以一個例子來說明上面的代碼是如何做到的。
            假如參數是0xffffffff。
            第一行代碼：
            nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
            a的二進制表示是：1010
            5的二進制表示是：0101
            0xffffffff 與 0xaaaaaaaa 進行與運算之后是0x10101010101010101010101010101010
            然后再進行左移操作后是0x01010101010101010101010101010101
            0x55555555 & nValue 進行與運算之后是0x01010101010101010101010101010101
            然后0x01010101010101010101010101010101 & 0x01010101010101010101010101010101
            得到0x10101010101010101010101010101010
            我們把得到的結果分成16組0x10  10  10  10  10  10  10  10  10  10  10  10  10  10  10  10
            每組的10單獨來看是不是十進制的2
            我們0x01010101010101010101010101010101和0x01010101010101010101010101010101這兩個數也按照上面的方法分成
            16個組0x01  01  01  01  01  01  01  01  01  01  01  01  01  01  01  01
                  0x01  01  01  01  01  01  01  01  01  01  01  01  01  01  01  01
            那么這兩個數的每一個組都是01 那么兩個01 里面有幾個1，是不是2個。這是2是不是二進制的10，然后16個10組合起來是不是
            0x10101010101010101010101010101010
            

            第二行代碼：
            nValue = ((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
            此時nValue是0x10101010101010101010101010101010
            c的二進制表示是：1100
            3的二進制表示是：0011
            0xcccccccc 與 nValue) 進行與運算之后是0x10001000100010001000100010001000
            然后再進行左移操作后是0x00100010001000100010001000100010
            0x33333333 & nValue 進行與運算之后是0x00100010001000100010001000100010
            

            然后0x00100010001000100010001000100010 & 0x00100010001000100010001000100010
            得到0x01000100010001000100010001000100
            我們把得到的結果分成8組0x0100 0100 0100 0100 0100 0100 0100 0100
            每組的0100單獨來看是不是十進制的4 總共有多少個4？是不是8個，8×4=32。
            

            以下的代碼：
             nValue = ((0xf0f0f0f0 & nValue)>>4) + (0x0f0f0f0f & nValue);
             nValue = ((0xff00ff00 & nValue)>>8) + (0x00ff00ff & nValue);
             nValue = ((0xffff0000 & nValue)>>16) + (0x0000ffff & nValue);
            請自己按照上面的方法做一遍，就會發現規律：第一次32位數分成32組，第二次分成16組，第三次分成8，第四次分成4，第五次分成2組。
            如果還是不明白請多看看，然后多選擇幾個參數進行試驗，多試幾次肯定會明白的。
            


            看了這么多解法是不是有中很過癮的感覺，當我知道有這么多解法是也很過癮，也很遺憾。遺憾什么呢？遺憾當時我碰到這道面試題的時候
            只想到了采用循環的方法，可是那個面試題上明確說明不準使用循環！！當時很郁悶！！
            鄭重聲明：上面最后兩個解法非本人原創，本人只是總結歸納，向想出這么好方法的前輩高人致敬！
            

	
            posted on 2010-03-24 18:02 OnTheWay 閱讀(6159) 評論(15)  編輯 收藏 引用  所屬分類: 面經  
            

            







            
	    
    


            
FeedBack:

            
	

		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-03-25 17:00 | 樂蜂專賣店
            
				
            案件的驕傲是巨大  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-03-25 17:01 | hoodlum1980
            
				
            一個UINT32，寫成16進制字符串，是“00000000”，“FFFFFFFF”。

            “0”到“F”，可以做一個16個元素的數組，該數組提供每個字母中 1 的個數。

            

            這樣我們把這個數字格式化成16進制的字符串，然后用查表法，累加每個字母位于數組中的1的個數即可。

            

            例如：“0”： 0000; 1的個數 = 0, “F”：1111; 1的個數=4；

            

            不知可行否？  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-03-25 18:10 | OnTheWay
            
				
            不可行。
            你的方法的思想是有點類似于桶排序的思想，但是是不可行的。
            首先從時間效率和空間效率上看與上述的任何一個方案相比都沒有優勢。
            另外在計算機里數據是按照二進制的方式進行存儲的，按照你的方案還需要把二進制再轉換成16進制的，如果你能進行轉換的話，很可能說明此時你已經知道了這些二進制位中有多少個1了。  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-03-25 18:11 | OnTheWay
            
				
            @樂蜂專賣店
            別在這里做廣告了。  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-03-25 18:12 | hoodlum1980
            
				
            補全一下代碼：

            #include <stdio.h>

            #include <string.h>

            int GetBitNumOfOne_ByHoodlum(unsigned int nValue)

            {

            	size_t i;

            	int count = 0;

            	char *CharSet = "0123456789ABCDEF";

            

            	//每個字符中含有的1的個數

            	int table[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };

            	char str[12];

            	sprintf(str, "%X", nValue);

            	size_t length = strlen(str);

            	for(i=0; i < length; i++)

            	{

            		count += table[ strchr(CharSet, str[i]) - CharSet ];

            	}

            	return count;

            }  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-03-25 18:32 | OnTheWay
            
				
            @hoodlum1980
            呵呵，我的理解有誤，按照你的方案確實可以實現。
            不過時間效率和空間效率確實不是太高。
            另外如果可以使用這么多系統函數的話，那還是使用標準庫的bitset方便些。
            代碼如下：
            #include <iostream>
            #include <bitset>
            #include <algorithm>

            using namespace std;

            size_t GetBitNumOfOne_ByBitSet(unsigned int nValue)
            {
            	const size_t sizeBitNum = 8;
            	bitset<sizeof(unsigned int) * sizeBitNum> TestBitSet(nValue);
            	string strContent = TestBitSet.to_string();
            	return std::count(strContent.begin(), strContent.end(), '1');
            }

            void main()
            {
            	//測試數據
            	cout<<GetBitNumOfOne_ByBitSet(0)<<endl;
            	cout<<GetBitNumOfOne_ByBitSet(1)<<endl;
            	cout<<GetBitNumOfOne_ByBitSet(2)<<endl;
            	cout<<GetBitNumOfOne_ByBitSet(123)<<endl;
            	cout<<GetBitNumOfOne_ByBitSet(0xff)<<endl;
            }  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）[未登錄]
            
			
            
				2010-03-26 09:52 | hh
            
				
            先計算出結果, 找規律

            

            之后重寫程序, 兩字: 查表  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-03-29 12:53 | 小時候可靚了
            
				
            查表吧，反正是有限位，建一個表

            比如  0   0   ,1   1,   2  1 ,  3   2...  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）[未登錄]
            
			
            
				2010-03-31 14:54 | tom
            
				
            試過std::bitset沒？可以用int直接構造，再循環調用std::bitset::test()測試每一位就齊活。  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-04-04 22:29 | ARush
            
				
            #include "stdafx.h"

            #include <stdio.h>

            //得到一個unsigned int整數的二進制表示中1的數目

            int GetNO(unsigned int number);

            int _tmain(int argc, _TCHAR* argv[])

            {

             int number;

             puts("input a int number");

             while(scanf("%d",&number)==1)

             {

              int result=0;

              result=GetNO(number);

              printf("\nthe length of %d is %d\n",number,result);

                    puts("input a int number");

             }

             return 0;

            }

            int GetNO(unsigned int number)

            {

             int size=sizeof(unsigned int)*8;

             int result=0;

             for(int i=0;i<size;i++,number>>=1)

             {

              if(number==0)

               break;

               if((01&number)==01)

                result++;

             }

             return result;

            }  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-04-08 11:53 | jmchxy
            
				
            調用任何系統函數都會增加時間空間效率， 循環調用 bitset::test 不會比第一種方法更好。 sprintf 轉換到16進制本身就需要進行一次循環除法取余， std::count 同樣是循環算法. 第三種方法是常數復雜度，最快的。  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-04-29 17:05 | D
            
				
            int countbit(int n)

            {

            	int c;

            	for(c=0;n;n>>=1)	c+=n&1;

            	return c;

            }

              回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）[未登錄]
            
			
            
				2010-05-29 11:26 | hdqqq
            
				
            unsigned long val ;
            int count = 0;
            while(val) {
                count += (val & 1) ;
                val >>= 1;
            }  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）[未登錄]
            
			
            
				2010-05-29 11:30 | hdqqq
            
				
            @hdqqq
            上面已經貼了類似的，我的作廢。  回復  更多評論
              
            
			
            
			
			
		
            
	
		
            
			
            # re: 一道面試題（求一個unsigned int 數的二進制表示中有多少個1？）
            
			
            
				2010-11-24 23:22 | triangle
            
				
            @OnTheWay
             第一行代碼：nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
            將32位數分為16組，判斷出每兩位中有多少個1,并用兩位來表示結果。
            (0xaaaaaaaa & nValue)>>1) 計算偶數位是否為1; 如10&10>>1 = 01
            (0x55555555 & nValue) 計算基數為是否為1; 如10&01= 00
            兩數相加得出10中包含的1的個數為0x01;
            后面的代碼則是如何將16組2位數相加得出最后的結果。
            第二行代碼：((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
            將nValue的分成8組，每組中的兩兩相加;
            如(0110 & 1100)>>2 + (0110 & 0011) = 0011; 即 01 + 10 = 0011;
            同理：
             第三行代碼： 將nValue分成4組，每組中的兩兩相加，也就是每4位相加，結果保存在8位數中。
            第四行代碼：  將nValue分成2組，每組中的兩兩相加，也就是每8位相加，結果保存在16位數中。
            第五行代碼：  將nValue分成1組，每組中的兩兩相加，也就是每16位相加，結果保存在32位數中。






              回復  更多評論
              
            
			
            
			
			
		
            
	








            






            

				

            

            
	
		
            
			
            			
			
            
	
            
		
            <2010年5月>
            
	
            日一二三四五六
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

			

            常用鏈接
            


            留言簿(4)
            




		
            隨筆分類
            
		
				
			
	
		
            隨筆檔案
            
		
				
			
	
		
            友情連接
            
		
				
              
			
				
            
			
	




            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


            
	

            



    
    







            
	   
	



久久久久久曰本AV免费免费|
好属妞这里只有精品久久|
久久av高潮av无码av喷吹|
久久精品国产一区二区三区|
国产精品狼人久久久久影院|
国产精自产拍久久久久久蜜|
中文字幕无码av激情不卡久久|
久久精品国产亚洲αv忘忧草|
AV狠狠色丁香婷婷综合久久
|
99久久国产综合精品麻豆|
国产69精品久久久久99|
久久久久亚洲av综合波多野结衣
|
国产成人久久精品麻豆一区|
亚洲伊人久久成综合人影院|
国产产无码乱码精品久久鸭|
最新久久免费视频|
国产高清美女一级a毛片久久w|
久久99精品久久久大学生|
久久人人爽人人澡人人高潮AV|
99国产欧美久久久精品蜜芽|
久久人妻少妇嫩草AV蜜桃|
91精品日韩人妻无码久久不卡|
日韩精品久久久久久免费|
国产99久久久国产精品小说|
久久99精品久久久久久水蜜桃|
国产精品欧美久久久天天影视|
人妻丰满AV无码久久不卡
|
久久久无码精品亚洲日韩蜜臀浪潮|
国产成人久久久精品二区三区|
久久99国产精品久久|
久久精品中文騷妇女内射|
无码人妻精品一区二区三区久久久
|
久久―日本道色综合久久|
久久国产亚洲高清观看|
亚洲精品乱码久久久久久蜜桃不卡|
亚洲精品国产综合久久一线|
久久se精品一区二区影院|
久久久久亚洲精品无码网址|
久久综合五月丁香久久激情|
久久无码精品一区二区三区|
美女久久久久久|