How to Count true bits in an array of DINTS

TheWaterboy · Feb 22, 2016

I have an array of 100 DINTS and I need to count the BITS that are True.
I tried a nested FOR in Structured Text but it wouldn't allow the second nested var "Y" (i.e. MyDintArray[X].Y)

In a smaller set elsewhere I converted the DINT array to a single BOOL array and that worked. But a 3200 bit array seems like a bad idea at this moment. Any other ideas?

JaxGTO · Feb 22, 2016

I did this once in a PLC-5 about 15 years ago. I know I used a bit of binary math and it was real simple. Ill look in my archives and see if I can find it. I seem to remember I used a single FAL in incremental mode and jumped backwards for the number of words in the array each scan. had maybe 3 or four rungs of math in between.

The quickest would be to just loop through the words, move into a working DINT, then clear a counter, then 32 rungs of XIC bit 0 Add 1 to counter, XIC bit 1 ADD 1 to counter etc.
Then at the end add that counter to the final counter.

Ugly but it would work.

Doug-P · Feb 22, 2016

Counting bits set, Brian Kernighan's way

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

Several other methods are illustrated also.

ASF · Feb 22, 2016

TheWaterboy said:
I tried a nested FOR in Structured Text but it wouldn't allow the second nested var "Y" (i.e. MyDintArray[X].Y)

You have to put the second variable in square brackets as well as using the full stop: MyDintArray[X].[Y]

TheWaterboy · Feb 24, 2016

ASF said:
You have to put the second variable in square brackets as well as using the full stop: MyDintArray[X].[Y]

Huh... Well, I didn't even think of that because it didn't fit the normal requirements for a tag name, but it did clear the syntax error.

However just this one script takes over 1 ms to run according to the monitor so maybe I'll keep looking for that perfect technique with low overhead.

JHarbin · Feb 24, 2016

Doug-P said:
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

Several other methods are illustrated also.

I tested this method in a Redlion G315 display and it works great. Here is the problem, can someone explain what is actually going on with the "v &= v - 1;" line? I understand everything else, but bitwise comparisons are a bit rusty.

Here is the full code, but again, I'm only asking about the one line. I know what the for loop is doing but I'm not sure how it only runs once for each high bit.

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}

TheWaterboy · Feb 24, 2016

First unqualified guess is because the index is zero based ?

I started reading what you sent in the hope of understanding it since I need to convert this to a compact or possibly contrologix routine.
Have you converted this to a routine in AB platforms?

JHarbin · Feb 24, 2016

TheWaterboy said:
First unqualified guess is because the index is zero based ?

I started reading what you sent in the hope of understanding it since I need to convert this to a compact or possibly contrologix routine.
Have you converted this to a routine in AB platforms?

I am thinking that what is happening is that it runs until the bitwise comparison between v and v-1 is 1 and it dumps out of the for loop. Even after the first iteration, c will be greater than 1 (unless there are no high bits at which the loop won't run I would assume). Since c is the count iterations it is also the counts of high bits.

Edit - I modified the logic to do the steps on at a time and I think my description above is accurate, even if my terminology isn't.

JeremyM · Feb 24, 2016

I wrote an AOI, HammingWeight, for this purpose. It simply accepts a DINT and returns the count of 1 bits.

You could nest something like this and pass each element of the array per scan cycle; or perhaps a loop within a scan, whatever.

TheWaterboy · Feb 24, 2016

I didn't think about breaking it up into scans like that. Good idea, I'll try that in a few minutes.

FYI I copied the 100 Dints into a 3200 Bool array and use ST code to scan it. It took almost the same amount of time to loop through the 100 Dint array as it did to scan the single Bool Array. So no savings there.

RussB · Feb 24, 2016

Have you tried eight 400bit, bit arrays, or any other combo?

TheWaterboy · Feb 24, 2016

Thats what Jeremy was suggesting and I'm going to try that next.

JeremyM · Feb 24, 2016

Yes, you are perpetually in loop, so you can take advantage of this to amortize computation if you aren't interested in an atomic result being made available immediately. BUT there's potential overhead - what's the cost of 100 identical function calls? Since this is on a real time controller, this may very well be the corner case, so my point could be moot.

All said, I should probably create an alternative AOI to accept as parameter both a reference to DINT[] and length of the array at that location. Passing entire arrays' contents is inefficient.

SANITY CHECK: is your DINT array as it stands 1 or 2-dimensional?

if one-dimensional, the solution is straightforward:
iterate the array DINT by DINT passing each to the counting function, don't try to iterate bits

Doug-P · Feb 24, 2016

JHarbin said:
"v &= v - 1;" line
v &= v - 1; // clear the least significant bit set
}

Ampersand is the AND operator. Assume v holds the value six - bits one and two set.

v-1 yields five
six ANDed with five yields four - only bit two remains set. Least significant bit has been cleared.

On the next iteration bit two will be cleared and you exit the loop.

JHarbin · Feb 24, 2016

Doug-P said:
Ampersand is the AND operator. Assume v holds the value six - bits one and two set.

v-1 yields five
six ANDed with five yields four - only bit two remains set. Least significant bit has been cleared.

On the next iteration bit two will be cleared and you exit the loop.

Thanks for confirming what I observed. I modified the program to allow me to step through it and that is what I was seeing.

I don't generally need this information - the PAC I normally use has this function built-in if I need it, but based on the number of times I have seen requests for this, I was amazed by the simple and elegant method that you linked to.

How to Count true bits in an array of DINTS

TheWaterboy

Lifetime Supporting Member + Moderator

JaxGTO

Member

Doug-P

Member

ASF

Lifetime Supporting Member

TheWaterboy

Lifetime Supporting Member + Moderator

JHarbin

Member

TheWaterboy

Lifetime Supporting Member + Moderator

JHarbin

Member

JeremyM

Lifetime Supporting Member

TheWaterboy

Lifetime Supporting Member + Moderator

RussB

Lifetime Supporting Member

TheWaterboy

Lifetime Supporting Member + Moderator

JeremyM

Lifetime Supporting Member

Doug-P

Member

JHarbin

Member

Similar Topics