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

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 閱讀(6192) 評論(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ù)  更多評論
  

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用鏈接

留言簿(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>
            久久久久久伊人| 一本色道88久久加勒比精品| 午夜一级久久| 亚洲欧美日韩综合一区| 国产伦精品一区| 久热爱精品视频线路一| 蜜桃av噜噜一区二区三区| 亚洲国产精品免费| 亚洲精品久久嫩草网站秘色 | 亚洲日韩欧美一区二区在线| 欧美精品在线观看| 亚洲一区欧美一区| 欧美影院成人| 亚洲国产综合91精品麻豆| 日韩一区二区精品在线观看| 国产精品三区www17con| 久久亚洲精品一区二区| 欧美日本在线看| 欧美专区在线观看| 欧美成人精品激情在线观看| 亚洲一区二区视频在线观看| 欧美一级一区| 日韩视频精品在线| 性欧美暴力猛交另类hd| 亚洲精品一品区二品区三品区| 99在线|亚洲一区二区| 国产一级一区二区| 最新高清无码专区| 国产深夜精品福利| 久久夜色精品国产噜噜av| 亚洲黄页一区| 99精品久久久| 亚洲激情亚洲| 性做久久久久久久久| 99香蕉国产精品偷在线观看| 久久精品视频99| 亚洲一区国产视频| 欧美成人综合网站| 久久五月激情| 国产欧美日韩三级| 这里只有精品在线播放| 91久久久久久| 久久久欧美精品sm网站| 久久大综合网| 国产精品a久久久久久| 亚洲国产精品久久久| 精品成人乱色一区二区| 亚洲免费一区二区| 亚洲中字在线| 欧美私人网站| 亚洲毛片播放| 日韩亚洲欧美成人一区| 蜜臀av性久久久久蜜臀aⅴ| 久久久久久香蕉网| 国产一区二区看久久| 亚洲欧美日本国产专区一区| 亚洲一区视频在线| 欧美性猛交xxxx免费看久久久| 亚洲国产经典视频| 亚洲欧洲一区二区三区在线观看| 久久色在线播放| 蜜臀va亚洲va欧美va天堂| 国内精品久久久久久| 久久成人久久爱| 久久网站免费| 亚洲国产国产亚洲一二三| 久久中文精品| 亚洲大片av| 一区二区三欧美| 欧美日韩一区二区在线观看视频| 99国产精品99久久久久久粉嫩| 中文国产一区| 国产伦精品一区二区三区高清版| 亚洲欧美一级二级三级| 久久精品青青大伊人av| 伊人狠狠色j香婷婷综合| 免费不卡在线观看| 亚洲精品久久久久久久久久久久久| 亚洲精品在线一区二区| 欧美日韩综合不卡| 欧美亚洲一区在线| 欧美va天堂va视频va在线| 亚洲精品一二区| 欧美日韩在线一区| 欧美一区二区免费| 亚洲高清视频一区二区| 亚洲五月六月| 国产一区二区三区四区三区四| 久久一二三四| 99精品国产在热久久下载| 久久av一区二区三区漫画| 亚洲电影免费| 国产精品久久久久一区二区三区共 | 国产精品日韩欧美一区二区| 欧美一区二区三区免费大片| 欧美二区在线播放| 亚洲一二三四久久| 经典三级久久| 欧美极品在线播放| 亚洲精品日产精品乱码不卡| 欧美视频一区二区三区…| 性欧美激情精品| 亚洲精品1234| 久久麻豆一区二区| 亚洲午夜精品久久久久久app| 国产亚洲二区| 欧美日本高清一区| 久久成人免费电影| 亚洲少妇中出一区| 亚洲国产精品一区在线观看不卡| 欧美一区二区三区视频免费| 日韩亚洲欧美高清| 亚洲电影免费观看高清完整版在线| 国产精品va在线| 欧美国产综合| 久久久久久久999| 亚洲一区在线观看免费观看电影高清| 欧美高清日韩| 久久夜色撩人精品| 久久丁香综合五月国产三级网站| 日韩午夜在线观看视频| 在线观看亚洲精品视频| 国产一区美女| 国产精品视频在线观看| 欧美日韩一区二区三区在线| 欧美国产三区| 美女主播视频一区| 久久久久久久999| 久久国产精品免费一区| 亚洲欧美视频一区| 亚洲免费小视频| 亚洲综合精品| 亚洲一区二区精品| 一区二区三区高清在线| 亚洲人成人一区二区在线观看| 牛牛国产精品| 欧美刺激午夜性久久久久久久| 久久亚洲欧美国产精品乐播| 久久久久国产一区二区| 久久久久网站| 久久永久免费| 免费不卡在线观看| 免费在线观看精品| 欧美国产三区| 亚洲福利国产精品| 亚洲精品五月天| 一本久久a久久免费精品不卡| 亚洲美女啪啪| 中文成人激情娱乐网| 亚洲性夜色噜噜噜7777| 午夜宅男久久久| 久久久久国色av免费观看性色| 久久国产精品久久久久久电车| 久久久久久久久蜜桃| 蜜臀91精品一区二区三区| 欧美久久久久| 国产精品久久一卡二卡| 国产一区二区精品久久| 亚洲电影自拍| 一区二区高清视频在线观看| 亚洲欧美综合一区| 久久在线精品| 亚洲精品色婷婷福利天堂| 亚洲校园激情| 久久久www成人免费毛片麻豆| 免费成人毛片| 欧美午夜免费影院| 极品少妇一区二区三区精品视频 | 欧美日韩在线视频一区| 国产乱码精品一区二区三| 精品av久久久久电影| 99精品免费网| 久久九九全国免费精品观看| 欧美激情视频网站| 亚洲专区一区| 牛牛国产精品| 国产精品亚洲片夜色在线| 久久精品国产一区二区电影| 欧美一区二区三区四区视频| 免费成人高清视频| 国产美女一区二区| 亚洲欧洲精品一区二区| 午夜亚洲福利| 亚洲欧洲偷拍精品| 欧美一级大片在线观看| 欧美日韩成人免费| 国语精品一区| 亚洲一区欧美激情| 亚洲国产精品免费| 欧美在线播放| 国产精品国产福利国产秒拍| 亚洲国产精品www| 久久久91精品国产一区二区三区 | 亚洲综合精品四区| 欧美黄色大片网站| 久久国产一区| 国产精品一区二区久久国产| 一区二区av在线| 欧美国产高潮xxxx1819| 久久国产精品久久国产精品|