討論區快速選單
知識庫快速選單
網路投保旅行平安險 傑米的攝影旅遊筆記 政府補助!學嵌入式+物聯網
[ 回上頁 ] [ 討論區發言規則 ]
1的個數
更改我的閱讀文章字型大小
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/8 上午 07:14:34
assume there is an alternative number in word ( 32 bits ) , such as 101010111111110101011111000011011. how to write a little routine that can count it's 1's number ? (In this case , the number is 22)
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/8 上午 08:47:53
http://en.wikipedia.org/wiki/Hamming_weight
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/8 下午 08:00:09
the method that needs many shift operations and extra patterns. it owns highly computing times.
作者 : doraemon(人稱阿牛)
[ 貼文 74 | 人氣 5056 | 評價 220 | 評價/貼文 2.97 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/8 下午 08:51:28
做個256項目的表, 以BYTE為索引事先計算好這值有幾個1存入表中
4bytes的整數只要查4次表,結束
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/8 下午 09:37:43
it still needs extra patterns.
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/8 下午 11:26:57
>the method that needs many shift operations and extra patterns. it owns highly computing times.

First of all, please specify your constrains and/or conditions, how much is "many"?

Anyway, the article gives several ideas of what can be done, however, you are not and should not be confine by those methods only, one can always use a combination of the methods shown in the article, e.g., using lookup table for 4 bit value, there are only 16 entries.

Using the table, you only need one shift, bitwise & and addition to compute population count for an unsigned 8-bit value:
    return table[x & 0x0f] + table[x >> 4]; // x is unsigned char

To compute population count for 32-bit unsigned value, you can cast the address of the 32-bit value to unsigned char*, and then use the casted pointer as a unsigned char array and call the previous function 4 times (3 addition operation).
  int popcount(unsigned __int32 x)
  {
    unsigned char *p = (unsigned char*)&x;
    return popcount(p[0]) + popcount(p[1]) + popcount(p[2]) + popcount(p[3]);
  }

As regarding computing time, I have not done any profiling and therefore unable to compare the differences and effects of each operations. Even if I do, they are usually platform and compiler dependent and might not hold true in general.

Population Count or Hamming Weight algorithm has been studied quite extensively for several decades, are you actively looking into this for your project or simply testing us like a quiz ? I suspect the later based on several questions you posted in this forum; if so, you must have some ideal solutions in your mind and we all be delighted if you can share your findings with us.

作者 : 100111(music8844)
[ 貼文 3 | 人氣 0 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/9 下午 03:44:16
你的數字有 33 bit

int i, result;

DWORD k = 0xABFD5F0D; // 10101011111111010101111100001101

for (i=0, result=0; i < 32; i++)
{
if ((k >> i) & 0x1)
{
result++;
}
}

作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/9 下午 04:50:16
It seems that your method is good. can you enhance its speed ? its time complexity is O(n) and we will not know by advance its value.
作者 : 100111(music8844)
[ 貼文 3 | 人氣 0 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/9 下午 05:10:00
int i, result;

DWORD k = 0xABFD5F0D; // 10101011111111010101111100001101

for (i=0, result=0; i < 32; i++)
{
result = ((k & 0x1)) & 0x01 ? result + 1 : result;

k = k >> 1;
}
作者 : 100111(music8844)
[ 貼文 3 | 人氣 0 | 評價 0 | 評價/貼文 0 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/9 下午 05:15:43

上一則有誤, 應改為[


int i, result;

DWORD k = 0xABFD5F0D; // 10101011111111010101111100001101

for (i=0, result=0; i < 32; i++)
{
     result = k & 0x1 ? result + 1 : result;

     k = k >> 1;
}
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/9 下午 05:23:20
it seems that the complexity of routine is same , O(n) . can it faster ?
作者 : turing(Alan)
[ 貼文 68 | 人氣 0 | 評價 300 | 評價/貼文 4.41 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/9 下午 09:31:18
隨意寫來一個。

#include <stdio.h>

#define DWORD unsigned int
#define UNKNOWN -1

int count(int l)
{
int c = 0;

do {
c += (l & 0x01) ? 1 : 0;
} while ((l >>= 1) > 0);

return c;
}

int main()
{
int table[16] = {
UNKNOWN, UNKNOWN, UNKNOWN, UNKNOWN,
UNKNOWN, UNKNOWN, UNKNOWN, UNKNOWN,
UNKNOWN, UNKNOWN, UNKNOWN, UNKNOWN,
UNKNOWN, UNKNOWN, UNKNOWN, UNKNOWN
};
int i, l, result;

DWORD k = 0xABFD5F0D; // 10101011111111010101111100001101

for (i = 0, result = 0; i < 8; i++)
{
l = k & 0x0F;

if (table[l] == UNKNOWN)
{
table[l] = count(l);
}

result += table[l];

k >>= 4;
}

printf("Number of 1 = %d\n", result);

return 0;
}


1. What is the Big-O of this?

2. Big-O跟table大小的關係又是甚麽?
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/10 下午 12:13:52
樓主的題目常常語焉不詳。
什麼是"a little routine"
程式小還是效率高?
要效率沒有比table方法更高的方法。
樓主說它需要額外的pattern。
使手shift又嫌它複雜度高(O(n))。
不能等人家交卷後才訂規則吧?
其實shift的方法稍加改善即可以使複雜度不是O(n):
它的複雜度最差情況是O(n)
要提高效率就得犧牲一點程式的簡潔度,再疊一層:
int Weight1s(unsigned long lData){return lData?(lData&1)+Weight1s(lData>>1) : 0;}
int Weight(unsigned long lData){ return lData?Weight1s(lData&0xFF)+Weight(lData>>8) : 0;}
呼叫Weight會比直接呼叫Weight1s降底平均複雜度。

作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/10 下午 12:17:39
抱歉,漏了一行:
其實shift的方法稍加改善即可以使複雜度不是O(n):
int Weight1s(unsigned long lData){return lData?(lData&1)+Weight1s(lData>>1) : 0;}
它的複雜度最差情況是O(n)


作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/10 下午 04:43:45
二分法:
int Weight1s(unsigned __int32 nD, unsigned __int32 nB=sizeof(unsigned __int32)*8)
{//呼叫時第一個參數使用預設
return nD?((nB/=2)? Weight1s(nD&((1<<nB)-1), nB)+Weight1s(nD>>nB, nB): 1) : 0;
}
作者 : turing(Alan)
[ 貼文 68 | 人氣 0 | 評價 300 | 評價/貼文 4.41 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/11 上午 06:49:24
>樓主的題目常常語焉不詳。
>什麼是"a little routine"
>程式小還是效率高?
>要效率沒有比table方法更高的方法。
>樓主說它需要額外的pattern。
>使手shift又嫌它複雜度高(O(n))。
>不能等人家交卷後才訂規則吧?
>其實shift的方法稍加改善即可以使複雜度不是O(n):
>它的複雜度最差情況是O(n)
>要提高效率就得犧牲一點程式的簡潔度,再疊一層:

要數1,事先不知有多少個,當然要數完。數完所有1便是O(n),似乎是不能再快。不數1而數patterns,是必然的出路。

Extra patterns放哪?要容易存取,當然是放在table/array內。
Shift就是指sub pattern matching,不match單個1而match pattern,一次match數個1,成為O(n/k)。

這其實是很基本的hashing方法,以空間換時間,沒大不了,hashing入門而已。對學生的水平是可以說得神神秘秘。

最高效是先建一個32bit patterns都有的表。效率是O(1)或O(constant)。

純從效率考慮,pattern表會先以人手先硬置。我花了數分鐘寫了一個自動建patterns的表,再玩玩caching,反問Big O及pattern size跟Big O的關係。想看看要當老師考人的水平如何。

懂不懂進行統計分析Big O?懂不懂分析時考慮algorithm中的變數?

似乎仍未能回答。
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/11 上午 10:20:02
>要數1,事先不知有多少個,當然要數完。數完所有1便是O(n),似乎是不能再快。
最差情況是O(n)沒錯,但資料若不一定要數完才能知道結果呢?
1.如果data是0,需要每一個bit都數過,才能能知道1的數量為0嗎?當然不是!
2.把資料分成兩半,分別計算1的數量加起來就是資料bit為1的總量。如果任一半資料為0,就不用計算了(見1)。
3.再把切分的資料再切成兩半分別計算再加總(如同2.),一直切到不能再切為止(切分資量為1個bit)。
這演算法就像是binary search,只是把search變成計數就行了。
程式實現,前面已貼,再貼一次:
int Weight1s(unsigned __int32 nD, unsigned __int32 nB=sizeof(unsigned __int32)*8)
{//呼叫時第一個參數使用預設
return nD?((nB/=2)? Weight1s(nD&((1<<nB)-1), nB)+Weight1s(nD>>nB, nB): 1) : 0;
}

要計算 0x805A00FF bit為1數量:
Weight1s(0x805A00FFui32);
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/11 上午 10:56:01
>要數1,事先不知有多少個,當然要數完。數完所有1便是O(n),似乎是不能再快。

除了 lookup 外, 有比一個一個位元來檢查更有效率的演算法: x & x-1 直接把 least-significant 的 1 轉成 0:
  int population_count(unsigned int x)
  {
    int count = 0;
    for (; x; ++count)
    {
      x &= x-1;
    }
    return count;
  }

當所有的 1 都變成 0, 就跳出迴圈了. 也就是說, loop 的次數等於 x 數值裡 1 的個數, 最好的情況是 x = 0, 最差的情況是 x = UINT_MAX.

作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/11 下午 12:47:07
>除了 lookup 外, 有比一個一個位元來檢查更有效率的演算法: x & x-1 直接把 least-significant 的 1 轉成 0
不用查表的話,這個應該最猛了。
作者 : doraemon(人稱阿牛)
[ 貼文 74 | 人氣 5056 | 評價 220 | 評價/貼文 2.97 | 送出評價 3 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/11 下午 10:26:18
>當所有的 1 都變成 0, 就跳出迴圈了. 也就是說, loop 的次數等於 x 數值裡 1 的個數, 最好的情況是 x = 0, 最差的情況是 x = UINT_MAX.
>
>
必須推這個, 算法簡單重要的是不帶任何條件判斷
在管線化的cpu架構下能飛快執行

提外話,終於沒用英文發文啦 lol
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2019 程式設計俱樂部 http://www.programmer-club.com.tw/
0.21875