Bit twiddling

The recent thread(http://www.plctalk.net/qanda/showthread.php?t=43018) about finding adjacent ones piqued my interest. Is there an easier, faster way to do this than sequentially searching through every bit pair of interest?

After some experimentation I found something I think works fairly well. For test purposes I used three sixteen-bit words. The processor is a PLC-5

1. AND the two LSBs of the least significant word. Obviously, if both of these are ON the condition is met

2a. Make a copy of the argument(s)

2b. Right-shift the copy by one bit. This is easily done on A-B processors with the BSR instruction. In fact, if the words are contiguous, only one instruction is needed to shift dozens or hundreds of bits.

2c. AND the copy with the original argument into RESULT

2d. Test RESULT for a non-zero condition. This test can be done on individual words or a whole file. Any non-zero result word indicates that two adjacent bits are set.

If you're looking for zeroes you could NOT the argument before processing starts.

A caveat, make sure the bit shifted in to the BSR is always zero or you may get an erroneous hit.

Comments?

I don't see the savings...Whether indexing or Bit shifting, you are still 'moving' through the individual bits to check.

Doug P is asking the right questions and there is an easier way.

I don't see the savings...Whether indexing or Bit shifting, you are still 'moving' through the individual bits to check.

Click to expand...

No!!!

Bit hacks come up from time to time.

Log₂ (X & (NOT(X-1)))

X & (NOT(X-1) gives you a number with only the least significant bit of X set.

Log base 2 of a binary number with only a single bit set will give you the position of that bit. There are several bit hacks online that will give you log₂ withouth actually computing it (too busy to look it up myself).

This method would need to loop only once for every bit set, ie, if 7 bits are set then it will only need to loop 7 times.

Peter Nachtwey said:

No!!!

Click to expand...

Yes!!!

Actually, after re-reading Doug's solution I get it. I missread it that he was checking the two LSBs each time after a shift, not the entire word. Good solution.

Peter Nachtwey said:

there is an easier way

Click to expand...

Peter, do you mean by this that there is an easier way than what I posted? If so, could you point me to it?

1 copy the 3 16 bit registers as you said.
2. shift one copy left, not right. This avoids having to check the first two LSBs. If there are exactly 48 bits it probably doesn't make a different.
3. And the two sets of registers together.
4. There is no need to scan through all the bits one at a time. All that is needed is to now that any bits are set after any AND.
One could just jump to the TwoAdjacentBitsFound lablel after finding the first non zero result after an AND.

My technical writing needs some work. What you describe is essentially what I was trying to get across.

Peter Nachtwey said:

1 copy the 3 16 bit registers as you said.
2. shift one copy left, not right. This avoids having to check the first two LSBs. If there are exactly 48 bits it probably doesn't make a different.

Click to expand...

Yes, depending on the application the end bits probably won't matter. I only included this test for the sake of thoroughness.

Peter Nachtwey said:

3. And the two sets of registers together.

Click to expand...

The heart of the thing.

Peter Nachtwey said:

4. There is no need to scan through all the bits one at a time. All that is needed is to now that any bits are set after any AND.

Click to expand...

Here's where my explanation becomes less clear. It was not my intent to check every bit at this stage, hence step:

2d. Test RESULT for a non-zero condition. This test can be done on individual words (thereby checking sixteen bits at a time) or a whole file. Any non-zero result word indicates that two adjacent bits are set.

Peter Nachtwey said:

One could just jump to the TwoAdjacentBitsFound lablel after finding the first non zero result after an AND].

Click to expand...

Yes. I'd do this with an FSC instruction. When the non-zero test is true the FD bit is set and appropriate action taken.

After thinking on it, the algorithm might be refined, that is, made faster, using a handmade loop rather than file instructions.

Regards

Doug-P said:

Yes. I'd do this with an FSC instruction. When the non-zero test is true the FD bit is set and appropriate action taken.

After thinking on it, the algorithm might be refined, that is, made faster, using a handmade loop rather than file instructions.

Click to expand...

The file instructions execute in machine code whereas the ladder probably has some overhead and the loop certainly does. I would check the execution times before making that assumption.

I know this would execute quickly if written in S7's STL.