青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

OnTheWay2012
埋葬昨天的我,迎來重生的我!
posts - 15,  comments - 89,  trackbacks - 0

求一個unsigned int 數(shù)的二進制表示中有多少個1?
這是一道面試題可以用以下的一些方案。
第一種是很容易想到的采用循環(huán)的方式并且與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進行右移。
當(dāng)然了以上的兩個方法存在一個問題:不管如何這個函數(shù)肯定要循環(huán)32次(對于32平臺來說)。
那又沒有更好的方法?當(dāng)然有,請看下面:
 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}

假如使用參數(shù)12345(二進制是11000000111001)調(diào)用該函數(shù),該函數(shù)的執(zhí)行情況如下:
第一次進入循環(huán)
0 < 11000000111001
11000000111001 &= (11000000111001 - 1) 之后 nValue 的值 是 11000000111000
nBitNum 的值是1
經(jīng)過本次循環(huán)之后11000000111001 變成了 11000000111000 比之前少了一個1
第二次進入循環(huán)
0 < 11000000111000
11000000111000 &= (11000000111000 - 1) 之后 nValue 的值 是 11000000110000
nBitNum 的值是2
經(jīng)過本次循環(huán)之后11000000111000 變成了 11000000110000 比之前少了一個1
第三次進入循環(huán)
0 < 11000000110000
11000000110000 &= (11000000110000 - 1) 之后 nValue 的值 是 11000000100000
nBitNum 的值是3
經(jīng)過本次循環(huán)之后11000000110000 變成了 11000000100000 比之前少了一個1
經(jīng)過以上3次循環(huán)情況的說明,我相信你一定看出了些什么吧。nValue &=(nValue - 1),這句
代碼實際上就是把nValue 的某位及其以后的所有位都變成0,當(dāng)nValue最后變成0的時候循環(huán)結(jié)束,
且nBitNum 記錄的就是1的個數(shù)。
上面的做法已經(jīng)很不錯了,但是作為程序員的你是否會有疑問,“還有其他的方法嗎?”。
有,當(dāng)然有!請看下面的代碼:
 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}


假如你是第一次看到這些代碼,你是否能看明白?呵呵,本人第一次看到這些代碼的時候看了好久才感覺
好像有點明白。下面我就以一個例子來說明上面的代碼是如何做到的。
假如參數(shù)是0xffffffff。
第一行代碼:
nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
a的二進制表示是:1010
5的二進制表示是:0101
0xffffffff 與 0xaaaaaaaa 進行與運算之后是0x10101010101010101010101010101010
然后再進行左移操作后是0x01010101010101010101010101010101
0x55555555 & nValue 進行與運算之后是0x01010101010101010101010101010101
然后0x01010101010101010101010101010101 & 0x01010101010101010101010101010101
得到0x10101010101010101010101010101010
我們把得到的結(jié)果分成16組0x10  10  10  10  10  10  10  10  10  10  10  10  10  10  10  10
每組的10單獨來看是不是十進制的2
我們0x01010101010101010101010101010101和0x01010101010101010101010101010101這兩個數(shù)也按照上面的方法分成
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
那么這兩個數(shù)的每一個組都是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
我們把得到的結(jié)果分成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);
請自己按照上面的方法做一遍,就會發(fā)現(xiàn)規(guī)律:第一次32位數(shù)分成32組,第二次分成16組,第三次分成8,第四次分成4,第五次分成2組。
如果還是不明白請多看看,然后多選擇幾個參數(shù)進行試驗,多試幾次肯定會明白的。


看了這么多解法是不是有中很過癮的感覺,當(dāng)我知道有這么多解法是也很過癮,也很遺憾。遺憾什么呢?遺憾當(dāng)時我碰到這道面試題的時候
只想到了采用循環(huán)的方法,可是那個面試題上明確說明不準(zhǔn)使用循環(huán)!!當(dāng)時很郁悶!!
鄭重聲明:上面最后兩個解法非本人原創(chuàng),本人只是總結(jié)歸納,向想出這么好方法的前輩高人致敬!

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

FeedBack:
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-03-25 17:00 | 樂蜂專賣店
案件的驕傲是巨大  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-03-25 17:01 | hoodlum1980
一個UINT32,寫成16進制字符串,是“00000000”,“FFFFFFFF”。
“0”到“F”,可以做一個16個元素的數(shù)組,該數(shù)組提供每個字母中 1 的個數(shù)。

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

例如:“0”: 0000; 1的個數(shù) = 0, “F”:1111; 1的個數(shù)=4;

不知可行否?  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-03-25 18:10 | OnTheWay
不可行。
你的方法的思想是有點類似于桶排序的思想,但是是不可行的。
首先從時間效率和空間效率上看與上述的任何一個方案相比都沒有優(yōu)勢。
另外在計算機里數(shù)據(jù)是按照二進制的方式進行存儲的,按照你的方案還需要把二進制再轉(zhuǎn)換成16進制的,如果你能進行轉(zhuǎn)換的話,很可能說明此時你已經(jīng)知道了這些二進制位中有多少個1了。  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-03-25 18:11 | OnTheWay
@樂蜂專賣店
別在這里做廣告了。  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個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的個數(shù)
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;
}  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-03-25 18:32 | OnTheWay
@hoodlum1980
呵呵,我的理解有誤,按照你的方案確實可以實現(xiàn)。
不過時間效率和空間效率確實不是太高。
另外如果可以使用這么多系統(tǒng)函數(shù)的話,那還是使用標(biāo)準(zhǔn)庫的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()
{
//測試數(shù)據(jù)
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;
}  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)[未登錄]
2010-03-26 09:52 | hh
先計算出結(jié)果, 找規(guī)律

之后重寫程序, 兩字: 查表  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-03-29 12:53 | 小時候可靚了
查表吧,反正是有限位,建一個表
比如 0 0 ,1 1, 2 1 , 3 2...  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)[未登錄]
2010-03-31 14:54 | tom
試過std::bitset沒?可以用int直接構(gòu)造,再循環(huán)調(diào)用std::bitset::test()測試每一位就齊活。  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-04-04 22:29 | ARush
#include "stdafx.h"
#include <stdio.h>
//得到一個unsigned int整數(shù)的二進制表示中1的數(shù)目
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;
}  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-04-08 11:53 | jmchxy
調(diào)用任何系統(tǒng)函數(shù)都會增加時間空間效率, 循環(huán)調(diào)用 bitset::test 不會比第一種方法更好。 sprintf 轉(zhuǎn)換到16進制本身就需要進行一次循環(huán)除法取余, std::count 同樣是循環(huán)算法. 第三種方法是常數(shù)復(fù)雜度,最快的。  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-04-29 17:05 | D
int countbit(int n)
{
int c;
for(c=0;n;n>>=1) c+=n&1;
return c;
}
  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)[未登錄]
2010-05-29 11:26 | hdqqq
unsigned long val ;
int count = 0;
while(val) {
count += (val & 1) ;
val >>= 1;
}  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)[未登錄]
2010-05-29 11:30 | hdqqq
@hdqqq
上面已經(jīng)貼了類似的,我的作廢。  回復(fù)  更多評論
  
# re: 一道面試題(求一個unsigned int 數(shù)的二進制表示中有多少個1?)
2010-11-24 23:22 | triangle
@OnTheWay
第一行代碼:nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
將32位數(shù)分為16組,判斷出每兩位中有多少個1,并用兩位來表示結(jié)果。
(0xaaaaaaaa & nValue)>>1) 計算偶數(shù)位是否為1; 如10&10>>1 = 01
(0x55555555 & nValue) 計算基數(shù)為是否為1; 如10&01= 00
兩數(shù)相加得出10中包含的1的個數(shù)為0x01;
后面的代碼則是如何將16組2位數(shù)相加得出最后的結(jié)果。
第二行代碼:((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
將nValue的分成8組,每組中的兩兩相加;
如(0110 & 1100)>>2 + (0110 & 0011) = 0011; 即 01 + 10 = 0011;
同理:
第三行代碼: 將nValue分成4組,每組中的兩兩相加,也就是每4位相加,結(jié)果保存在8位數(shù)中。
第四行代碼: 將nValue分成2組,每組中的兩兩相加,也就是每8位相加,結(jié)果保存在16位數(shù)中。
第五行代碼: 將nValue分成1組,每組中的兩兩相加,也就是每16位相加,結(jié)果保存在32位數(shù)中。






  回復(fù)  更多評論
  

<2010年3月>
28123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

友情連接

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲国内自拍| 欧美mv日韩mv亚洲| 国产精品卡一卡二| 午夜视频一区| 亚洲欧美日韩精品| 精品二区视频| 亚洲第一毛片| 蜜臀av在线播放一区二区三区| 1024亚洲| 亚洲精品免费看| 欧美四级电影网站| 久久久久久久一区二区三区| 久久精品国产精品亚洲精品| 亚洲国产日韩综合一区| 亚洲精品一区二区在线| 国产精品影院在线观看| 蜜桃av噜噜一区二区三区| 欧美成人精品一区二区三区| 亚洲午夜视频在线| 欧美一区1区三区3区公司| 亚洲精美视频| 亚洲一区在线观看视频| 亚洲国产精品女人久久久| 亚洲美女少妇无套啪啪呻吟| 国产精品一区二区欧美| 亚洲成色777777女色窝| 欧美三级视频在线播放| 久久久久久久高潮| 欧美日韩一区二区欧美激情| 久久精品久久综合| 欧美日韩国产成人在线免费| 久久精品视频在线| 欧美精品一区二区三| 久久精品最新地址| 欧美色视频在线| 免费观看成人| 国产精品区一区二区三区| 蜜臀久久久99精品久久久久久 | 亚洲国产精品一区二区久| 欧美三级乱人伦电影| 欧美成人免费在线视频| 国产精品视频免费在线观看| 亚洲国产成人精品久久| 黑人巨大精品欧美一区二区| 国产精品99久久久久久白浆小说| 亚洲激情一区二区三区| 久久精品国产综合| 性久久久久久久| 欧美日韩国产一区二区三区| 免费成人网www| 国产午夜精品理论片a级探花 | 欧美国产日韩a欧美在线观看| 国产精品一区二区你懂得| 99re视频这里只有精品| 亚洲日本va在线观看| 久久久人成影片一区二区三区观看| 亚洲免费在线电影| 欧美日韩一区自拍| 亚洲精品国久久99热| 亚洲人成网站777色婷婷| 欧美一区成人| 久久亚洲色图| 久久综合九色99| 国产日韩专区| 亚洲欧美日韩在线综合| 欧美一区二区国产| 国产精品久久久久久久久免费| 日韩一级二级三级| 亚洲午夜精品视频| 国产精品wwwwww| 亚洲天堂成人在线视频| 香蕉成人啪国产精品视频综合网| 国产精品vip| 午夜亚洲精品| 久久一二三国产| 一区二区视频在线观看| 免费欧美日韩| 亚洲区欧美区| 亚洲婷婷国产精品电影人久久| 欧美日韩大陆在线| 亚洲视频一二区| 久久精品日产第一区二区三区| 国内精品美女av在线播放| 久久亚洲精品伦理| 亚洲激情第一区| 亚洲欧美国产另类| 国内精品久久久久伊人av| 久久尤物视频| a4yy欧美一区二区三区| 欧美伊人久久大香线蕉综合69| 国产亚洲欧美日韩美女| 蜜臀a∨国产成人精品| 日韩一二在线观看| 久久精品中文字幕免费mv| 亚洲二区在线| 欧美三区不卡| 久久久久久久久伊人| 亚洲欧洲精品天堂一级 | 国产精品欧美日韩| 久久日韩精品| 亚洲视频免费看| 老司机午夜免费精品视频| 亚洲美女一区| 国产精品羞羞答答xxdd| 久久亚洲国产成人| 亚洲尤物在线视频观看| 欧美v国产在线一区二区三区| 99精品视频免费全部在线| 国产亚洲欧美日韩日本| 欧美日韩精品一区二区在线播放| 欧美一区激情视频在线观看| 亚洲国产日本| 久久夜色撩人精品| 午夜精品福利一区二区蜜股av| 亚洲欧洲视频在线| 激情欧美亚洲| 国产精品久久久久久五月尺| 久久只精品国产| 校园激情久久| 一本色道88久久加勒比精品 | 欧美成人午夜免费视在线看片 | 亚洲视频每日更新| 精品av久久707| 国产欧美婷婷中文| 欧美午夜免费电影| 免费人成精品欧美精品| 久久精品国产99| 免费成人高清视频| 欧美日韩国产精品自在自线| 久久婷婷国产综合国色天香| 国产一区二三区| 欧美午夜国产| 欧美久久电影| 久久久久久久久久久久久女国产乱 | 欧美日韩中文字幕在线视频| 欧美在线视频一区二区| 亚洲男人的天堂在线观看| 日韩视频免费| 亚洲日本理论电影| 久久国产精品高清| 亚洲女人天堂av| 国产精品99久久久久久人| 亚洲精品久久久久久久久久久久 | 一区二区亚洲| 好吊一区二区三区| 伊人婷婷欧美激情| 在线日韩欧美视频| 亚洲国产成人久久综合一区| 在线免费观看日本一区| 在线精品视频免费观看| 在线欧美影院| 亚洲经典三级| 一区二区av在线| 亚洲专区欧美专区| 欧美亚洲网站| 久久久99国产精品免费| 免费欧美高清视频| 亚洲国产精品va在线看黑人动漫| 欧美承认网站| 亚洲精品乱码久久久久久久久| 亚洲精品影视| 亚洲欧美国产高清| 久久久国产一区二区三区| 毛片基地黄久久久久久天堂| 欧美黄色片免费观看| 国产精品成人aaaaa网站| 国产精品国色综合久久| 国产一区二区精品久久| 亚洲国产欧美日韩精品| 在线综合视频| 久久久久五月天| 亚洲国产精品999| 亚洲视频 欧洲视频| 久久精品夜夜夜夜久久| 欧美人与禽性xxxxx杂性| 国产拍揄自揄精品视频麻豆| 亚洲国产成人精品女人久久久| 一区二区三区精密机械公司| 久久岛国电影| 亚洲国产影院| 欧美一级成年大片在线观看| 欧美18av| 国产一区二区三区的电影| 亚洲精品永久免费精品| 欧美在线精品一区| 亚洲国产精品成人一区二区| 亚洲香蕉在线观看| 欧美国产高清| 国内久久精品视频| 亚洲一区二区免费在线| 欧美成人a视频| 亚洲精品一区二| 一区二区三区波多野结衣在线观看| 韩日成人在线| 亚洲网站在线播放| 欧美激情亚洲综合一区| 亚洲欧美日韩精品久久亚洲区 | 午夜一区在线| 国产精品久久久久国产a级| 91久久精品一区二区别|