標(biāo)題: 想判斷一個數(shù)中"1"的個數(shù)的多少,有沒有什么高效的算法 [打印本頁]
作者: Y_G_G    時間: 2022-9-22 22:08
標(biāo)題: 想判斷一個數(shù)中"1"的個數(shù)的多少,有沒有什么高效的算法
最近在搞一個擇多算法,用于無刷電機(jī)的過零檢測,參考了PIC的代碼,原理大概是這樣的
每10uS讀取一次過零端口的狀態(tài),然后把端口的電平保存,并左移一位,然后再進(jìn)行比較,檢測這個數(shù)里面1的位是多少,用來檢測當(dāng)前端口的電平,實(shí)際上就是一個濾波
if(IO) a |=0x01;
a <= 1;
a是個8位數(shù),這樣一來,在讀取8次之后, a 就是一個完整的8次的IO狀態(tài)了
我就想知道,有沒有什么高效的算法,能快速的檢測 a 里面"1"有多少個,或者是說,快速判斷 a 里面"1"的個數(shù)超過6個
這個又不能用比大小,因?yàn)榭赡軙霈F(xiàn)這種情況: 0111 1111 或者是 1111 1110,或者其它的組合
這兩種情況都是超過了6個"1"的
PIC的方法是只比較3個位,用的是數(shù)組的方式,但這種方法在低轉(zhuǎn)速的時候,有時候會檢測到假的過零事件
先謝謝了
有什么其它關(guān)于無刷電機(jī)知識的,也可以相互探討一下
作者: cnos    時間: 2022-9-22 23:50
這個不就是查表的事情嗎，常規(guī)256字節(jié)的表，半字節(jié)4位查就是16字節(jié)的表
作者: Hephaestus    時間: 2022-9-23 00:33
計算一個32位數(shù)字x含有1的個數(shù)：
  1. x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  2. x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  3. x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  4. x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  5. x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
復(fù)制代碼


在 Hacker's Delight 2nd Edition一書的§5.1，你自己看去吧。
作者: 188610329    時間: 2022-9-23 01:40
if(IO)
{
a |=0x01;
b++；
}
a <= 1;

直接判斷 if(b>=6)  不行么？
作者: glinfei    時間: 2022-9-23 08:46
還真沒想出太好的辦法，對于數(shù)位數(shù)，我是這么弄的：Count=(a&0x80)+(a&0x40)+...+(a&0x01)  然后看看Count是幾了。還有人直接位運(yùn)算但我老是編譯不過。
作者: lkc8210    時間: 2022-9-23 09:49
  1. // **********************************************
  2. u8 bdata CompDat = 0;
  3. sbit Data0 = CompDat^0;
  4. sbit Data1 = CompDat^1;
  5. sbit Data2 = CompDat^2;
  6. sbit Data3 = CompDat^3;
  7. sbit Data4 = CompDat^4;
  8. sbit Data5 = CompDat^5;
  9. sbit Data6 = CompDat^6;
  10. sbit Data7 = CompDat^7;
  11. u8 CountBit1(u8 Dat)
  12. {
  13.         u8 Result = 0;
  14.         CompDat = Dat;
  15.         if(Data0)Result++;
  16.         if(Data1)Result++;
  17.         if(Data2)Result++;
  18.         if(Data3)Result++;
  19.         if(Data4)Result++;
  20.         if(Data5)Result++;
  21.         if(Data6)Result++;
  22.         if(Data7)Result++;
  23.         
  24.         return Result;
  25. }
  26. // **********************************************
  27. u8 CountBit2(u8 Dat)
  28. {
  29.         u8 Result = 0, Mask;
  30.         for(Mask = 0x01;Mask!=0;Mask<<=1)
  31.         {
  32.                 if(Dat&Mask)Result++;
  33.         }
  34.         return Result;
  35. }
復(fù)制代碼
STC89C仿真結(jié)果








STC15W仿真結(jié)果









作者: paladina    時間: 2022-9-23 09:53
在 if(IO)  后加一個語句，新增一個統(tǒng)計變量 然后自增， count++； ，滿8次后等你賦值a=0時同時把count=0；不就解決了，沒必要在后面再去計算吧
作者: hhdsdy    時間: 2022-9-23 10:01
188610329 發(fā)表于 2022-9-23 01:40
if(IO)
{
a |=0x01;

這個簡單的方法我昨晚看帖就冒出來了，樓主不可能想不出來，我估計樓主是要判斷已經(jīng)生成后的a，也就是判斷任意一個數(shù)（一個字節(jié)）里1的個數(shù)，要極簡的方法我沒想到。
作者: lkc8210    時間: 2022-9-23 10:17
cnos 發(fā)表于 2022-9-22 23:50
這個不就是查表的事情嗎，常規(guī)256字節(jié)的表，半字節(jié)4位查就是16字節(jié)的表

查表真的快












全字節(jié)592-586=6步
半字節(jié)607-592=15步
作者: rctty    時間: 2022-9-23 10:56
肯定是要一個中間變量來計算的，一個是和樓上一樣，每次進(jìn)行a判斷時b自增，要么就最后用循環(huán)判斷a
for(i;i<8;i++)
{
    if(((a >> i) & 0x01) != 0)
    {
        b++;
    }
}
作者: coody_sz    時間: 2022-9-23 11:27
查表最快，我常用到這個判斷，類似權(quán)重濾波。256個字節(jié)的表而已。
作者: 我會想你的    時間: 2022-9-23 11:58
int bitcount (unsigned int n)
{
    int count=0 ;
    while (n) {
        count++ ;
        n &= (n - 1) ;
    }
    return count ;
}
這是我前段時間在另外一個論壇上看到的 作者是 cnxh  
作者: 188610329    時間: 2022-9-23 12:00
hhdsdy 發(fā)表于 2022-9-23 10:01
這個簡單的方法我昨晚看帖就冒出來了，樓主不可能想不出來，我估計樓主是要判斷已經(jīng)生成后的a，也就是判 ...

因?yàn)?任何其他可能用的方法, 都不會比  if(IO)  的時候，順便 b++ 來的更 “簡” ， 所以，我才探討性的，問一下?lián)е鳎腔谑裁丛�，不能用這個方式。我從來沒有認(rèn)為摟主想不出這個方法。
作者: 一事無成    時間: 2022-9-23 13:57
  1. if(IO){
  2.         a|=0x01;
  3.         cnt++;
  4. }
  5. if(a&0x80) cnt--;
  6. a=a<<1;
復(fù)制代碼
作者: xstong    時間: 2022-9-23 14:00
統(tǒng)計數(shù)據(jù)data中1的個數(shù)：counter = 0;  while(data)  {  data &= data - 1; counter++;  }，循環(huán)次數(shù)等于置1位的個數(shù)，代碼實(shí)現(xiàn)，除了查表想不出比這個效率高的方法了。
作者: xianfajushi    時間: 2022-9-23 14:47
如果a不是數(shù)組的話可以判斷a是否=127即可就這么簡單，a可以這樣去算，a=0;if(a==0)++a;else a=a*2+1;
作者: ly1972001    時間: 2022-9-23 16:32
要高效嵌入?yún)R編，C的位操作不方便。
作者: 的花朵    時間: 2022-9-23 17:39
Hephaestus 發(fā)表于 2022-9-23 00:33
計算一個32位數(shù)字x含有1的個數(shù)：

相見恨晚的神書啊，好兄弟好兄弟好兄弟
作者: 的花朵    時間: 2022-9-23 17:49
Hephaestus 發(fā)表于 2022-9-23 00:33
計算一個32位數(shù)字x含有1的個數(shù)：

此書中文譯本
hacker's delight(中文版)
自行網(wǎng)上搜索獲取

作者: Y_G_G    時間: 2022-9-23 22:28
188610329 發(fā)表于 2022-9-23 01:40
if(IO)
{
a |=0x01;

是我沒有把問題說清楚,不好意思了
這是一個過零檢測的濾波算法,因?yàn)樵谶^零的時候,會有波動,比較器會一下子輸出1,一下輸出0
那么我現(xiàn)在要做的就是檢測出實(shí)際的過零的時間,就是說檢測比較器什么時候是"真實(shí)的從0變成了1"
這中間的過程大概是這樣子的吧:000000000   10101010110110  111111111
中間那一段就是波動的時候
你不能簡單的累計有多少個1,比如我定時器定時是10uS,如果都累加的話,當(dāng)條件符合的時候,距離的真實(shí)過零點(diǎn)已經(jīng)過去了60uS這在無刷電機(jī)中時間太長了
擇多算法真實(shí)的過程是這樣的:每次都比較一下這個數(shù)中和0和1
當(dāng)出現(xiàn)這種情況時,就判定為過零:前面的數(shù)有超過一半是0的,后面的數(shù)超過一半是1的,就認(rèn)為是有效的一次從0變成1的過程
有時間你可以看一下這里面的算法,后面部分有代碼,我只是想升級一下而已
01175a_cn.pdf (512.2 KB, 下載次數(shù): 24)



作者: ly1972001    時間: 2022-9-24 08:37
如果有現(xiàn)成算法，那意味著大部分人都已經(jīng)無法升級這個算法，除非是數(shù)學(xué)天才。
作者: hhh402    時間: 2022-9-24 09:51
對于過零檢測我用外部中斷IO口檢測，IO口有跳變馬上進(jìn)入中斷，反應(yīng)最快，比定時檢測快。
作者: yzwzfyz    時間: 2022-9-24 10:08
1、一個方案是有0：則作過0處理。響應(yīng)快，易受干擾。
2、另個方案是，出0后，再有連續(xù)N個1：則作過0處理。響應(yīng)慢，不易受干擾。當(dāng)N=1時，就是方案一。
樓主可以根據(jù)設(shè)計的目的，選擇N。
另一個要間，是采樣的間隔時間。

作者: Y_G_G    時間: 2022-9-24 22:52
hhh402 發(fā)表于 2022-9-24 09:51
對于過零檢測我用外部中斷IO口檢測，IO口有跳變馬上進(jìn)入中斷，反應(yīng)最快，比定時檢測快。

那是有霍爾的
沒有霍爾的,哪能一有中斷就處理呀
換相一次之后馬上就有一次中斷了,如果是低轉(zhuǎn)速有電機(jī),電感量會大點(diǎn),能有三四的假過零
再到真實(shí)過零的時候,新西達(dá)電機(jī)好點(diǎn),一般只有一次或者兩次波動而已,其它的電機(jī),能有全十多次過零事件
不濾波哪里行呀,IO中斷我也用過,感覺好像不怎么好,1萬/分之后就開始一頓一頓的,電流也開始莫名的大了,估計就是換相上面的問題
我都燒了快10片IRS2101S了,之前沒管列死的問題,估計就是中斷頻繁錯誤換相搞壞有,現(xiàn)在,加入死區(qū)控制了就好點(diǎn)了
作者: hhh402    時間: 2022-9-25 18:37
過零檢測不準(zhǔn)確那時硬件的問題，加一組低通濾波就可以解決，過零檢測必須是過零才發(fā)出信號，如果發(fā)出錯誤信號是硬件問題，更改硬件而不是改程序。單片機(jī)編程必須要懂硬件的，單純懂軟件不行。
作者: Y_G_G    時間: 2022-9-26 00:44
hhh402 發(fā)表于 2022-9-25 18:37
過零檢測不準(zhǔn)確那時硬件的問題，加一組低通濾波就可以解決，過零檢測必須是過零才發(fā)出信號，如果發(fā)出錯誤信 ...

不知道你有沒有做過無感無刷電機(jī)?
無感無刷電機(jī)過零點(diǎn)波動很大的,就算是加了一個104電容也是會有波動的
電容不能加太大了,不然過零滯后時間就太長了
轉(zhuǎn)速1萬多的電機(jī),有的100uS就要換相了,人家商用電調(diào)連濾波電容都不加的
10萬轉(zhuǎn)速的話,過零濾波,PWM調(diào)整,換相,定時器計算都要在十幾u(yù)S之內(nèi)完成了
所以,要速度快呀,像那種幾十行代碼的,低轉(zhuǎn)速還行,高轉(zhuǎn)速就不行了
論壇上有的程序,我試了,1萬以下轉(zhuǎn)速還行,超過就不行了
作者: hhh402    時間: 2022-9-26 10:14
需要速度用STM32高主頻單片機(jī)。不過硬件不行靠軟件只能夠自己玩玩，電機(jī)能夠轉(zhuǎn)動而已，其他的就談不上了。
作者: 188610329    時間: 2022-9-26 12:00
Y_G_G 發(fā)表于 2022-9-23 22:28
是我沒有把問題說清楚,不好意思了
這是一個過零檢測的濾波算法,因?yàn)樵谶^零的時候,會有波動,比較器會一下 ...

大概的理解了你的目的. 你看對不對?
你定時器中斷, 每10us(假定時間) 讀一次 IO，存入變量 a, 變量 a 永遠(yuǎn)只保存 最后8次的 IO 狀態(tài)， 然后，你希望通過分析 變量 a 知道， 最后8次 是否 有6個以上的1。

如果我上述理解正確的話，個人覺得應(yīng)當(dāng)從源頭直接開始分析，而不是去分析變量a, (由于你只說是參考PIC，不知道你實(shí)際用的什么單片機(jī)，我就當(dāng)51吧，反正你能看明白)
a<<=1;
if(CY)   b--;
if(IO)
{
      a |= 0x01;
      b++;
}
// b的值永遠(yuǎn)和  變量a中 1 的個數(shù)保持一致。
作者: Y_G_G    時間: 2022-9-26 17:10
188610329 發(fā)表于 2022-9-26 12:00
大概的理解了你的目的. 你看對不對?
你定時器中斷, 每10us(假定時間) 讀一次 IO，存入變量 a, 變量 a 永 ...

不只是只要判斷有多少個1,還得判斷有多少個0,用來檢測IO從0變成1的一個點(diǎn)
或者是從1變成0
實(shí)際上就是上升沿和下降沿檢測
但因?yàn)樗俣纫筇?而且IO波動過大,又不能漏掉太多,不然會錯過"真實(shí)的"過零點(diǎn),處理時間并不多,就不能用什么復(fù)雜的算法
當(dāng)然,這個是現(xiàn)在暫時用的辦法,以后就用ADC了
作者: Y_G_G    時間: 2022-9-26 17:12
hhh402 發(fā)表于 2022-9-26 10:14
需要速度用STM32高主頻單片機(jī)。不過硬件不行靠軟件只能夠自己玩玩，電機(jī)能夠轉(zhuǎn)動而已，其他的就談不上了。
...

無刷電機(jī)不要什么高深的硬件呀,一般的就行,有入門的基礎(chǔ)就行
而且,TI早就有現(xiàn)成的硬件電路了,下載直接打開就行了
有AD格式的,打板就能用了
作者: 大漠落日    時間: 2022-9-28 13:07
查表最快了，計算慢一點(diǎn)
作者: 188610329    時間: 2022-9-28 20:36
Y_G_G 發(fā)表于 2022-9-26 17:10
不只是只要判斷有多少個1,還得判斷有多少個0,用來檢測IO從0變成1的一個點(diǎn)
或者是從1變成0
實(shí)際上就是上 ...

因?yàn)?nbsp; b 就是 變量a 中1 的 個數(shù)。
所以，8-b  就是變量 a 中  0的個數(shù)。

之所以  建議你 if(IO) 的時候 就記錄 1/0 的個數(shù)，主要是為了 把時間 分?jǐn)偟矫看?檢測 IO 電平的時候。既 每次定時器中斷的時候 只需要 ++ -- 一次， 也就是 花費(fèi)兩個 時鐘，當(dāng)真正滿足你設(shè)定的條件時 是 1個時鐘 就出結(jié)果了， 真正做到最快響應(yīng)。 反正，不管用什么方式去 判斷 a 里面有多少 1/0  就算用 查表，最少也要用 十幾個時鐘。當(dāng)然你如果用匯編查表能快點(diǎn)，不過，你不是拋棄匯編了么？所以，也就不考慮了。

橫看豎看要在 a 里面的 1 的個數(shù)達(dá)到標(biāo)準(zhǔn)時，你最快的速度能夠知道滿足這個條件的話， 也就 b++； b-- ； 最合適了。
作者: Y_G_G    時間: 2022-9-28 21:53
188610329 發(fā)表于 2022-9-28 20:36
因?yàn)?nbsp; b 就是 變量a 中1 的 個數(shù)。
所以，8-b  就是變量 a 中  0的個數(shù)。

不是要看個數(shù)達(dá)到標(biāo)準(zhǔn)的
是要看什么時候出現(xiàn)從0變成1的真實(shí)時間點(diǎn),這才是重點(diǎn),我之前沒有描述清楚
用b++或者b--都會出現(xiàn)0x00和0xff的,因?yàn)闊o刷電機(jī)只有過零點(diǎn)才出現(xiàn)變化,其它時間,它會一直是0或者1
if(IO)
{
      a |= 0x01;
      b++;
}
在沒有到過零點(diǎn)的時候,假設(shè)IO一直是高電平,b就會有一個從255變成0的過程,低轉(zhuǎn)速的時候,換相時間是比較長的應(yīng)該是會超過255*10uS=2,55mS
PIC那個方案,用新西達(dá)電機(jī)能跑1萬/分的轉(zhuǎn)速,因?yàn)殡娫礇]有大于5A的,改天換個大電流的試一下能到多少
這個問題只是討論一下,以后肯定是要用ADC來計算的
作者: 188610329    時間: 2022-9-29 00:36
Y_G_G 發(fā)表于 2022-9-28 21:53
不是要看個數(shù)達(dá)到標(biāo)準(zhǔn)的
是要看什么時候出現(xiàn)從0變成1的真實(shí)時間點(diǎn),這才是重點(diǎn),我之前沒有描述清楚
用b+ ...

我想，我在28樓的回復(fù)，你可能沒仔細(xì)看�；蛘�，瀏覽器緩沖的關(guān)系，你這里沒有刷出來。我再貼一遍吧，

代碼如下：
a<<=1;
if(CY)   b--;
if(IO)
{
      a |= 0x01;
      b++;
}

你說的 255變0的問題是不會出現(xiàn)的， b永遠(yuǎn)在 0~8 之間， 也永遠(yuǎn)等于 a 里面 1的個數(shù)。
如果你長時間的 高電平， a= 0xff    那么b 也是 = 8， 你長時間的 低電平， a=0x00, 那么 b 也是 = 0； 這是完全同步的。 和你 把 a 拿去做任何算法 計算有多少1 是完全吻合的。

當(dāng)然，我不是強(qiáng)迫你用這個方法， 只是我覺得可能 你沒完全理解  這個代碼的記錄原理，跟你再說明一下而已。
作者: jjwangxu2008    時間: 2022-10-22 17:02
用 匯編 寫  ，不是更快嗎？
作者: 188610329    時間: 2022-10-22 23:08
jjwangxu2008 發(fā)表于 2022-10-22 17:02
用 匯編 寫  ，不是更快嗎？

你這問題說的……，人家好不容易拋棄了匯編，你讓人家吃回頭草?
作者: Y_G_G    時間: 2022-10-23 14:10
jjwangxu2008 發(fā)表于 2022-10-22 17:02
用 匯編 寫  ，不是更快嗎？

我不知道是從什么地方傳出"匯編比C快"的說法的
網(wǎng)上說的匯編效率比C高,那得是匯編寫得好的
匯編寫得不好的,堆出來的代碼,效率要比C慢的
這個帖子討論了很多,我再說一次吧
我只想從多個抖動中快速的找到真實(shí)上升沿或者是下降沿,檢測BLDC無刷電機(jī)的過零點(diǎn)
論壇上,網(wǎng)上都有教程,但很多是低速的,高速的效果都不怎么好
作者: cnos    時間: 2022-10-24 16:49
樓主是需要多快的響應(yīng)速度呢？還是這個響應(yīng)速度是動態(tài)可變的？比如你采樣的速度是多少，出現(xiàn)多少個連續(xù)的0或者1就認(rèn)為信號已經(jīng)穩(wěn)定了。
作者: Y_G_G    時間: 2022-10-24 17:54
cnos 發(fā)表于 2022-10-24 16:49
樓主是需要多快的響應(yīng)速度呢？還是這個響應(yīng)速度是動態(tài)可變的？比如你采樣的速度是多少，出現(xiàn)多少個連續(xù)的0 ...

不是多少個0或者多少個1的問題
而是一個從0變成1,或者是從1變成0的真實(shí)時間
其實(shí)就是無刷電機(jī)過零檢測
10uS一次采樣,那么,檢測的過程也就1-2uS左右吧,時間太長,會影響到10uS的周期,而且,主程序還要一些時間呢
現(xiàn)在暫時是用ADC來檢測了,等到以后有時間了再改進(jìn)一下這個程序
作者: meeagle    時間: 2022-10-24 18:52
給你個參考代碼
  1. MOV R2,#8
  2.                         MOV R3,#0
  3.                 LOOP:RLC A
  4.                         JC $+4
  5.                         INC R3
  6.                         DJNZ R2,LOOP
  7.                         RET
復(fù)制代碼

最后R3返回的值大于16，就是1多于0
調(diào)用這個子程序一共花費(fèi)54個指令周期，
如果你不用循環(huán)體，把代碼寫長一點(diǎn)，那么31個指令周期就夠了
作者: cnos    時間: 2022-10-24 19:09
cnos 發(fā)表于 2022-10-24 16:49
樓主是需要多快的響應(yīng)速度呢？還是這個響應(yīng)速度是動態(tài)可變的？比如你采樣的速度是多少，出現(xiàn)多少個連續(xù)的0 ...

沒錯的，我問的就是過了抖動區(qū)，就是連續(xù)的0和1了。那么，多少個連續(xù)的0或者1可以認(rèn)為是確切變了？
作者: Y_G_G    時間: 2022-10-24 19:53
cnos 發(fā)表于 2022-10-24 19:09
沒錯的，我問的就是過了抖動區(qū)，就是連續(xù)的0和1了。那么，多少個連續(xù)的0或者1可以認(rèn)為是確切變了？

要這么簡單就好了
假設(shè)抖動3次,你再以檢測到兩個1,就判定為一個上升沿
那么,最壞的情況就是,在第一次抖動的時候,就已經(jīng)是過零點(diǎn)了,再經(jīng)過后面4次,就是40uS,等于是你判定為過零的點(diǎn)的時間,比實(shí)際的時間晚了40uS
這個在低速的時候是沒有問題的
但在高速的時候,兩次過零之間的間隔也才100uS甚至更少,根本就檢測不到正常的過零點(diǎn)
而且,這個抖動并不是相對固定的,在低速的時候,可能會出現(xiàn)幾十次的抖動,但在高速的時候,可能沒有或者一兩次抖動,這是我用示波器看過了的
不過,現(xiàn)在我用ADC來檢測了,效果相對要好點(diǎn)
我只是想知道一些算法而已,因?yàn)轳R云家賣的驅(qū)動板,人家也是用比較器檢測過零的,人家一樣能做到近10萬轉(zhuǎn)/分的轉(zhuǎn)速,有點(diǎn)好奇,但網(wǎng)上也是找了好久,都沒有找到相關(guān)的代碼
作者: npn    時間: 2023-1-28 17:16
查表浪費(fèi)內(nèi)存空間，循環(huán)語句浪費(fèi)時間，還是Verilog劃算:
  1. module main(
  2.         input [7:0] in,                        //字節(jié)輸入
  3.         output reg [3:0] out                //二進(jìn)制1的數(shù)量
  4. );
  5. reg [2:0] i;
  6. always @(*) begin
  7.         i = 3'd0;
  8.         out = 4'd0;
  9.         repeat(8) begin
  10.                 if(in[i]) begin
  11.                         out = out + 4'd1;
  12.                 end
  13.                 i = i + 3'd1;
  14.         end
  15. end
  16. endmodule
復(fù)制代碼
作者: coody_sz    時間: 2024-7-25 13:52
查表最快，256個字節(jié)的表。



歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1