想判断一个数中"1"的个数的多少,有没有什么高效的算法 -

标题: 想判断一个数中"1"的个数的多少,有没有什么高效的算法 [打印本页]

作者: Y_G_G 时间: 2022-9-22 22:08
标题: 想判断一个数中"1"的个数的多少,有没有什么高效的算法
最近在搞一个择多算法,用于无刷电机的过零检测,参考了PIC的代码,原理大概是这样的
每10uS读取一次过零端口的状态,然后把端口的电平保存,并左移一位,然后再进行比较,检测这个数里面1的位是多少,用来检测当前端口的电平,实际上就是一个滤波
if(IO) a |=0x01;
a <= 1;
a是个8位数,这样一来,在读取8次之后, a 就是一个完整的8次的IO状态了
我就想知道,有没有什么高效的算法,能快速的检测 a 里面"1"有多少个,或者是说,快速判断 a 里面"1"的个数超过6个
这个又不能用比大小,因为可能会出现这种情况: 0111 1111 或者是 1111 1110,或者其它的组合
这两种情况都是超过了6个"1"的
PIC的方法是只比较3个位,用的是数组的方式,但这种方法在低转速的时候,有时候会检测到假的过零事件
先谢谢了
有什么其它关于无刷电机知识的,也可以相互探讨一下

作者: cnos 时间: 2022-9-22 23:50
这个不就是查表的事情吗，常规256字节的表，半字节4位查就是16字节的表

作者: Hephaestus 时间: 2022-9-23 00:33
计算一个32位数字x含有1的个数：

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

复制代码

在 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
还真没想出太好的办法，对于数位数，我是这么弄的：Count=(a&0x80)+(a&0x40)+...+(a&0x01) 然后看看Count是几了。还有人直接位运算但我老是编译不过。

作者: lkc8210 时间: 2022-9-23 09:49

// **********************************************
u8 bdata CompDat = 0;
sbit Data0 = CompDat^0;
sbit Data1 = CompDat^1;
sbit Data2 = CompDat^2;
sbit Data3 = CompDat^3;
sbit Data4 = CompDat^4;
sbit Data5 = CompDat^5;
sbit Data6 = CompDat^6;
sbit Data7 = CompDat^7;
u8 CountBit1(u8 Dat)
{
u8 Result = 0;
CompDat = Dat;
if(Data0)Result++;
if(Data1)Result++;
if(Data2)Result++;
if(Data3)Result++;
if(Data4)Result++;
if(Data5)Result++;
if(Data6)Result++;
if(Data7)Result++;
return Result;
}
// **********************************************
u8 CountBit2(u8 Dat)
{
u8 Result = 0, Mask;
for(Mask = 0x01;Mask!=0;Mask<<=1)
{
if(Dat&Mask)Result++;
}
return Result;
}

复制代码

STC89C仿真结果

STC15W仿真结果

作者: paladina 时间: 2022-9-23 09:53
在 if(IO) 后加一个语句，新增一个统计变量然后自增， count++；，满8次后等你赋值a=0时同时把count=0；不就解决了，没必要在后面再去计算吧

作者: hhdsdy 时间: 2022-9-23 10:01

188610329 发表于 2022-9-23 01:40
if(IO)
{
a |=0x01;

这个简单的方法我昨晚看帖就冒出来了，楼主不可能想不出来，我估计楼主是要判断已经生成后的a，也就是判断任意一个数（一个字节）里1的个数，要极简的方法我没想到。

作者: lkc8210 时间: 2022-9-23 10:17

cnos 发表于 2022-9-22 23:50
这个不就是查表的事情吗，常规256字节的表，半字节4位查就是16字节的表

查表真的快

全字节592-586=6步
半字节607-592=15步

作者: rctty 时间: 2022-9-23 10:56
肯定是要一个中间变量来计算的，一个是和楼上一样，每次进行a判断时b自增，要么就最后用循环判断a
for(i;i<8;i++)
{
if(((a >> i) & 0x01) != 0)
{
b++;
}
}

作者: coody_sz 时间: 2022-9-23 11:27
查表最快，我常用到这个判断，类似权重滤波。256个字节的表而已。

作者: 我会想你的 时间: 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 发表于 2022-9-23 10:01
这个简单的方法我昨晚看帖就冒出来了，楼主不可能想不出来，我估计楼主是要判断已经生成后的a，也就是判 ...

因为,任何其他可能用的方法, 都不会比 if(IO) 的时候，顺便 b++ 来的更 “简” ，所以，我才探讨性的，问一下搂主，是基于什么原因，不能用这个方式。我从来没有认为搂主想不出这个方法。

作者: 一事无成 时间: 2022-9-23 13:57

if(IO){
a|=0x01;
cnt++;
}
if(a&0x80) cnt--;
a=a<<1;

复制代码

作者: xstong 时间: 2022-9-23 14:00
统计数据data中1的个数：counter = 0; while(data) { data &= data - 1; counter++; }，循环次数等于置1位的个数，代码实现，除了查表想不出比这个效率高的方法了。

作者: xianfajushi 时间: 2022-9-23 14:47
如果a不是数组的话可以判断a是否=127即可就这么简单，a可以这样去算，a=0;if(a==0)++a;else a=a*2+1;

作者: ly1972001 时间: 2022-9-23 16:32
要高效嵌入汇编，C的位操作不方便。

作者: 的花朵 时间: 2022-9-23 17:39

Hephaestus 发表于 2022-9-23 00:33
计算一个32位数字x含有1的个数：

相见恨晚的神书啊，好兄弟好兄弟好兄弟

作者: 的花朵 时间: 2022-9-23 17:49

Hephaestus 发表于 2022-9-23 00:33
计算一个32位数字x含有1的个数：

此书中文译本
hacker's delight(中文版)
自行网上搜索获取

作者: Y_G_G 时间: 2022-9-23 22:28

188610329 发表于 2022-9-23 01:40
if(IO)
{
a |=0x01;

是我没有把问题说清楚,不好意思了
这是一个过零检测的滤波算法,因为在过零的时候,会有波动,比较器会一下子输出1,一下输出0
那么我现在要做的就是检测出实际的过零的时间,就是说检测比较器什么时候是"真实的从0变成了1"
这中间的过程大概是这样子的吧:000000000 10101010110110 111111111
中间那一段就是波动的时候
你不能简单的累计有多少个1,比如我定时器定时是10uS,如果都累加的话,当条件符合的时候,距离的真实过零点已经过去了60uS这在无刷电机中时间太长了
择多算法真实的过程是这样的:每次都比较一下这个数中和0和1
当出现这种情况时,就判定为过零:前面的数有超过一半是0的,后面的数超过一半是1的,就认为是有效的一次从0变成1的过程
有时间你可以看一下这里面的算法,后面部分有代码,我只是想升级一下而已

01175a_cn.pdf (512.2 KB, 下载次数: 24)

作者: ly1972001 时间: 2022-9-24 08:37
如果有现成算法，那意味着大部分人都已经无法升级这个算法，除非是数学天才。

作者: hhh402 时间: 2022-9-24 09:51
对于过零检测我用外部中断IO口检测，IO口有跳变马上进入中断，反应最快，比定时检测快。

作者: yzwzfyz 时间: 2022-9-24 10:08
1、一个方案是有0：则作过0处理。响应快，易受干扰。
2、另个方案是，出0后，再有连续N个1：则作过0处理。响应慢，不易受干扰。当N=1时，就是方案一。
楼主可以根据设计的目的，选择N。
另一个要间，是采样的间隔时间。

作者: Y_G_G 时间: 2022-9-24 22:52

hhh402 发表于 2022-9-24 09:51
对于过零检测我用外部中断IO口检测，IO口有跳变马上进入中断，反应最快，比定时检测快。

那是有霍尔的
没有霍尔的,哪能一有中断就处理呀
换相一次之后马上就有一次中断了,如果是低转速有电机,电感量会大点,能有三四的假过零
再到真实过零的时候,新西达电机好点,一般只有一次或者两次波动而已,其它的电机,能有全十多次过零事件
不滤波哪里行呀,IO中断我也用过,感觉好像不怎么好,1万/分之后就开始一顿一顿的,电流也开始莫名的大了,估计就是换相上面的问题
我都烧了快10片IRS2101S了,之前没管列死的问题,估计就是中断频繁错误换相搞坏有,现在,加入死区控制了就好点了

作者: hhh402 时间: 2022-9-25 18:37
过零检测不准确那时硬件的问题，加一组低通滤波就可以解决，过零检测必须是过零才发出信号，如果发出错误信号是硬件问题，更改硬件而不是改程序。单片机编程必须要懂硬件的，单纯懂软件不行。

作者: Y_G_G 时间: 2022-9-26 00:44

hhh402 发表于 2022-9-25 18:37
过零检测不准确那时硬件的问题，加一组低通滤波就可以解决，过零检测必须是过零才发出信号，如果发出错误信 ...

不知道你有没有做过无感无刷电机?
无感无刷电机过零点波动很大的,就算是加了一个104电容也是会有波动的
电容不能加太大了,不然过零滞后时间就太长了
转速1万多的电机,有的100uS就要换相了,人家商用电调连滤波电容都不加的
10万转速的话,过零滤波,PWM调整,换相,定时器计算都要在十几uS之内完成了
所以,要速度快呀,像那种几十行代码的,低转速还行,高转速就不行了
论坛上有的程序,我试了,1万以下转速还行,超过就不行了

作者: hhh402 时间: 2022-9-26 10:14
需要速度用STM32高主频单片机。不过硬件不行靠软件只能够自己玩玩，电机能够转动而已，其他的就谈不上了。

作者: 188610329 时间: 2022-9-26 12:00

Y_G_G 发表于 2022-9-23 22:28
是我没有把问题说清楚,不好意思了
这是一个过零检测的滤波算法,因为在过零的时候,会有波动,比较器会一下 ...

大概的理解了你的目的. 你看对不对?
你定时器中断, 每10us(假定时间) 读一次 IO，存入变量 a, 变量 a 永远只保存最后8次的 IO 状态，然后，你希望通过分析变量 a 知道，最后8次是否有6个以上的1。

如果我上述理解正确的话，个人觉得应当从源头直接开始分析，而不是去分析变量a, (由于你只说是参考PIC，不知道你实际用的什么单片机，我就当51吧，反正你能看明白)
a<<=1;
if(CY) b--;
if(IO)
{
   a |= 0x01;
   b++;
}
// b的值永远和  变量a中 1 的个数保持一致。

作者: Y_G_G 时间: 2022-9-26 17:10

188610329 发表于 2022-9-26 12:00
大概的理解了你的目的. 你看对不对?
你定时器中断, 每10us(假定时间) 读一次 IO，存入变量 a, 变量 a 永 ...

不只是只要判断有多少个1,还得判断有多少个0,用来检测IO从0变成1的一个点
或者是从1变成0
实际上就是上升沿和下降沿检测
但因为速度要求太高,而且IO波动过大,又不能漏掉太多,不然会错过"真实的"过零点,处理时间并不多,就不能用什么复杂的算法
当然,这个是现在暂时用的办法,以后就用ADC了

作者: Y_G_G 时间: 2022-9-26 17:12

hhh402 发表于 2022-9-26 10:14
需要速度用STM32高主频单片机。不过硬件不行靠软件只能够自己玩玩，电机能够转动而已，其他的就谈不上了。
...

无刷电机不要什么高深的硬件呀,一般的就行,有入门的基础就行
而且,TI早就有现成的硬件电路了,下载直接打开就行了
有AD格式的,打板就能用了

作者: 大漠落日 时间: 2022-9-28 13:07
查表最快了，计算慢一点

作者: 188610329 时间: 2022-9-28 20:36

Y_G_G 发表于 2022-9-26 17:10
不只是只要判断有多少个1,还得判断有多少个0,用来检测IO从0变成1的一个点
或者是从1变成0
实际上就是上 ...

因为  b 就是变量a 中1 的个数。
所以，8-b  就是变量 a 中  0的个数。

之所以  建议你 if(IO) 的时候就记录 1/0 的个数，主要是为了把时间分摊到每次检测 IO 电平的时候。既每次定时器中断的时候只需要 ++ -- 一次，也就是花费两个时钟，当真正满足你设定的条件时是 1个时钟就出结果了，真正做到最快响应。反正，不管用什么方式去判断 a 里面有多少 1/0  就算用查表，最少也要用十几个时钟。当然你如果用汇编查表能快点，不过，你不是抛弃汇编了么？所以，也就不考虑了。

横看竖看要在 a 里面的 1 的个数达到标准时，你最快的速度能够知道满足这个条件的话，也就 b++； b-- ；最合适了。

作者: Y_G_G 时间: 2022-9-28 21:53

188610329 发表于 2022-9-28 20:36
因为 b 就是变量a 中1 的个数。
所以，8-b 就是变量 a 中 0的个数。

不是要看个数达到标准的
是要看什么时候出现从0变成1的真实时间点,这才是重点,我之前没有描述清楚
用b++或者b--都会出现0x00和0xff的,因为无刷电机只有过零点才出现变化,其它时间,它会一直是0或者1
if(IO)
{
a |= 0x01;
b++;
}
在没有到过零点的时候,假设IO一直是高电平,b就会有一个从255变成0的过程,低转速的时候,换相时间是比较长的应该是会超过255*10uS=2,55mS
PIC那个方案,用新西达电机能跑1万/分的转速,因为电源没有大于5A的,改天换个大电流的试一下能到多少
这个问题只是讨论一下,以后肯定是要用ADC来计算的

作者: 188610329 时间: 2022-9-29 00:36

Y_G_G 发表于 2022-9-28 21:53
不是要看个数达到标准的
是要看什么时候出现从0变成1的真实时间点,这才是重点,我之前没有描述清楚
用b+ ...

我想，我在28楼的回复，你可能没仔细看。或者，浏览器缓冲的关系，你这里没有刷出来。我再贴一遍吧，

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

你说的 255变0的问题是不会出现的， b永远在 0~8 之间，也永远等于 a 里面 1的个数。
如果你长时间的高电平， a= 0xff 那么b 也是 = 8，你长时间的低电平， a=0x00, 那么 b 也是 = 0；这是完全同步的。和你把 a 拿去做任何算法计算有多少1 是完全吻合的。

当然，我不是强迫你用这个方法，只是我觉得可能你没完全理解  这个代码的记录原理，跟你再说明一下而已。

作者: jjwangxu2008 时间: 2022-10-22 17:02
用汇编写，不是更快吗？

作者: 188610329 时间: 2022-10-22 23:08

jjwangxu2008 发表于 2022-10-22 17:02
用汇编写，不是更快吗？

你这问题说的……，人家好不容易抛弃了汇编，你让人家吃回头草?

作者: Y_G_G 时间: 2022-10-23 14:10

jjwangxu2008 发表于 2022-10-22 17:02
用汇编写，不是更快吗？

我不知道是从什么地方传出"汇编比C快"的说法的
网上说的汇编效率比C高,那得是汇编写得好的
汇编写得不好的,堆出来的代码,效率要比C慢的
这个帖子讨论了很多,我再说一次吧
我只想从多个抖动中快速的找到真实上升沿或者是下降沿,检测BLDC无刷电机的过零点
论坛上,网上都有教程,但很多是低速的,高速的效果都不怎么好

作者: cnos 时间: 2022-10-24 16:49
楼主是需要多快的响应速度呢？还是这个响应速度是动态可变的？比如你采样的速度是多少，出现多少个连续的0或者1就认为信号已经稳定了。

作者: Y_G_G 时间: 2022-10-24 17:54

cnos 发表于 2022-10-24 16:49
楼主是需要多快的响应速度呢？还是这个响应速度是动态可变的？比如你采样的速度是多少，出现多少个连续的0 ...

不是多少个0或者多少个1的问题
而是一个从0变成1,或者是从1变成0的真实时间
其实就是无刷电机过零检测
10uS一次采样,那么,检测的过程也就1-2uS左右吧,时间太长,会影响到10uS的周期,而且,主程序还要一些时间呢
现在暂时是用ADC来检测了,等到以后有时间了再改进一下这个程序

作者: meeagle 时间: 2022-10-24 18:52
给你个参考代码

MOV R2,#8
MOV R3,#0
LOOP:RLC A
JC $+4
INC R3
DJNZ R2,LOOP
RET

复制代码

最后R3返回的值大于16，就是1多于0
调用这个子程序一共花费54个指令周期，
如果你不用循环体，把代码写长一点，那么31个指令周期就够了

作者: cnos 时间: 2022-10-24 19:09

cnos 发表于 2022-10-24 16:49
楼主是需要多快的响应速度呢？还是这个响应速度是动态可变的？比如你采样的速度是多少，出现多少个连续的0 ...

没错的，我问的就是过了抖动区，就是连续的0和1了。那么，多少个连续的0或者1可以认为是确切变了？

作者: Y_G_G 时间: 2022-10-24 19:53

cnos 发表于 2022-10-24 19:09
没错的，我问的就是过了抖动区，就是连续的0和1了。那么，多少个连续的0或者1可以认为是确切变了？

要这么简单就好了
假设抖动3次,你再以检测到两个1,就判定为一个上升沿
那么,最坏的情况就是,在第一次抖动的时候,就已经是过零点了,再经过后面4次,就是40uS,等于是你判定为过零的点的时间,比实际的时间晚了40uS
这个在低速的时候是没有问题的
但在高速的时候,两次过零之间的间隔也才100uS甚至更少,根本就检测不到正常的过零点
而且,这个抖动并不是相对固定的,在低速的时候,可能会出现几十次的抖动,但在高速的时候,可能没有或者一两次抖动,这是我用示波器看过了的
不过,现在我用ADC来检测了,效果相对要好点
我只是想知道一些算法而已,因为马云家卖的驱动板,人家也是用比较器检测过零的,人家一样能做到近10万转/分的转速,有点好奇,但网上也是找了好久,都没有找到相关的代码

作者: npn 时间: 2023-1-28 17:16
查表浪费内存空间，循环语句浪费时间，还是Verilog划算:

module main(
input [7:0] in, //字节输入
output reg [3:0] out //二进制1的数量
);
reg [2:0] i;
always @(*) begin
i = 3'd0;
out = 4'd0;
repeat(8) begin
if(in[i]) begin
out = out + 4'd1;
end
i = i + 3'd1;
end
end
endmodule

复制代码

作者: coody_sz 时间: 2024-7-25 13:52
查表最快，256个字节的表。

欢迎光临 (http://www.51hei.com/bbs/)