Tidbits, finding the bit number or index

Join Date
Apr 2002
Location
No income tax, no capital gains tax. Freedom!
Posts
8,337
I have watched for many years how people come up with ways of finding the bit numbers of bits that are set. RSLogix5000 has a FBC which works and that is good enough for most cases but what do you do if you don't have a FBC inctruction? I have seen people shift bits right until the carry is set and I have seen people shift a 1 left and count how many times they must shift but that takes time and worse yet it is a loop. What is needed is a good way to find the bit number of a set bit that is simple and doesnt't require looping or floating point. One shouldn't use floating point because it actually is doing a lot of work when executing ln() and exp() functions.

To find the index or number of a bit set one must first reduce the set of bits to just one. It is easy to find least significant bit set in a register of bits.
This takes just one rung or maybe two depending on the PLC.

The next trick is to find the bit number of the bit set. This too is easy but it takes a few more rungs but at least it doesn't require looping.

If more than one bit is set then isolate the bit
Code:
dintBit = dintBits and ( not dintBits + 1 )
Now there is only one bit set in dintBit.
Find the bit number or index using the follow procedure:
Code:
BitNumber = 0
if ( dintBit and 0AAAAAAAAH <> 0 )
   BitNumber = BitNumber + 1
if ( dintBit and 0CCCCCCCCH <> 0 )
   BitNumber = BitNumber + 2
if ( dintBit and 0F0F0F0F0H <> 0 )
   BitNumber = BitNumber + 4
if ( dintBit and 0FF00FF00H <> 0 )
   BitNumber = BitNumber + 8
if ( dintBit and 0FFFF0000H <> 0 )
   BitNumber = BitNumber + 16
A PLC should be able to implement this in 6 rungs. A S7 should be very efficient.

This can be extended by adding another check for 64 bit registers. There are 64 bit Power PC, AMD and Intel processors.
Does it make any difference what order the bits are tested?

One can see this is much faster than looping or shifting a bit left. I didn't see any reason to post this before because I thought all PLCs had ENCode and DeCoDe instructions.

Don't lose this.
 
CroCop said:
Peter,

Is there any reason you couldn't place all of the ifs in one rung?
Go ahead if you can. I was suggesting a generic algorithm for finding the bit index. I was leaving the implementation details as something to be worked out by the programmer and his PLC. One a S7 I would do this in STL and who needs even one rung?

Oh, BTW, there must be one bit and only one bit set before the index routing will work. I usually check after find the least signficant bit set. If the result is zero then I skip finding the index and usually return a -1.
 
I use the Control Logix almost 100% of the time, so I'm guessing I could put it in ST & call it as a subroutine when I need it......
 
Peter Nachtwey said:
Code:
BitNumber = 0
if ( dintBit and 0AAAAAAAAH <> 0 )
BitNumber = BitNumber + 1
if ( dintBit and 0CCCCCCCCH <> 0 )
BitNumber = BitNumber + 2
if ( dintBit and 0F0F0F0F0H <> 0 )
BitNumber = BitNumber + 4
if ( dintBit and 0FF00FF00H <> 0 )
BitNumber = BitNumber + 8
if ( dintBit and 0FFFF0000H <> 0 )
BitNumber = BitNumber + 16
Does it make any difference what order the bits are tested?
My observations indicate: No, the order does not matter.

Interestingly, the algorithm produces the same results if both the masks and the zero sense are inverted, ie.
 
AAAA -> 5555
CCCC -> 3333
etc.
and {dintBit and (MASK) <> 0} -> {dintBit and (MASK) = 0}




Peter Nachtwey said:
Don't lose this.
Made a hardcopy in my little book of knowledge.
 
Integer calculation of LOG2(N)

Here is an AB program that will calculate the index of the highest bit in any non-zero 16 bit integer, or Log base 2 of the integer. It will work if multiple bits are set, however it will only return the index of the highest bit.

This program was tested on a SLC5/05 and should work on any AB PLC.

This does it in 4 steps.

IF (N & FF00h) then right shift N 8 places and add 8 to count.
IF (N & 00F0h) then right sift N 4 places and add 4 to count.
IF (N & 000Ch) then right sift N 2 places and add 2 to count.
IF (N & 0002h) then add 1 to count.

It can be extended to 32 bit integers in 5 setps by adding
IF (N & FFFF0000h) then right shift N 16 places and add 16 to count.
as the first step. The method could be expanded to 64 bits or more and across word boundaries with a little work.

Here's the rub with AB however: The SLC 5/03 and up, and ML family of AB PLCs all support the ENC instruction which will do it for you, so this would be doing it the hardway on those processors.

Enhanced PLC5s and CLX all support the LN instruction, and LN(N)/LN(2) is a lot easier to program (though its not a purely integer operation as this program is)

If you are using long words on a ML, or if you are performing the operation on a SLC 5/01/02 or non-enhanced PLC5 then this is a method to consider.

The method will work on any PLC if the ooperation is translated properly.
 
Last edited:
Peter, you are still the Man! I knew there had to be a clever logical way to do this. I've already implemented it in an M90 program and changed the demo program I posted at the Downloads section.

Got any more of these nifty tricks up your sleeve?

TM
 
Alaric has been studying.

TimothyMoulder said:
Got any more of these nifty tricks up your sleeve?

TM

Yes, but for bit tricks just look at the link Alaric posted. It looks pretty good.

BTW, this info is not new I have known these tricks for 20+ years.
They have been 'general knowledge' as far a I know. I have always been amused by people trying to do bit manipulation the hard way. Hopefully Alaric's link will help spread this 'general' knowledge.
 
BTW, this info is not new I have known these tricks for 20+ years.

Actually, it goes back a lot further than that. In my last year at Uni in Glasgow in '65-'66 I took their "Computing" course as one of options (it was the first year the course was offered. Memory being the scarce (and expensive!) resource that it was then, a substantial part of the course was concerned with these extremely efficient ways of achieving a result. To this day I still to "Shift Left" rather than multiply by 2 (4, 8, etc.). Sadly, with the concentration on OOP and methods for improving the efficiency of team programming, a lot of useful knowledge has got lost on the way.

Intersting site that, Alaric!
 
Quite right RMA , the problem is we tend to forget them - read an interesting post on RSD's forum a while back , involving simultaneous equations - and reminded myself that I could still do maths !!

This is an interesting problem for S7 if we take Siemens and low high byte swaps .
 

Similar Topics

For the last day or so I have been reading on here about how to discover what bit is true in an integer. Most of the info is from Peter Nachtwey...
Replies
12
Views
13,763
I didn't want to hijack the thread so I started this one. It isn't strictly related to PLC but the techniques could be useful in PLCs too...
Replies
3
Views
5,943
How does one find the least significant bit WITHOUT: 1 checking for a bit being set in each bit position. 2 looping. 3 using lookup tables. 4...
Replies
19
Views
5,782
Assume there is a set of 16 bits in N7:0. What is the result in N7:1 SUB 0 N7:0 N7:1 AND N7:0 N7:1 N7:1
Replies
8
Views
5,580
Hi all, I'm in the process of upgrading a PanelView1200 HMI program to be developed in FactroyTalk View Studio. The filetype for PanelView 1200...
Replies
7
Views
223
Back
Top Bottom