Math Equation

J

Thread Starter

Jansen, Joe

Question:

I am trying to determine which bit position is on based on the value of a data word. I would like to do this with a simple(?) formula. If I have 2^x = y, how would I solve for x? This is what I would need.

Thanks for any help!


--Joe Jansen
 
what hardware are you using?
Allen Bradley in their micrologogix family has an instruction called DCD-which decodes a 4 bit value in the source word(0-16)and then turns on a bit in the destination word.This is a very useful and powerful instruction but obviously only useful if you are using rockwell software! they also have a complimentary instruction called ENC-which takes a bit position and converts to a 4 bit integer(0-16)
i hope this may be of some use
marios
 
R

Ralph G. McDonald, P.E.

Hi Joe;

If you are using older or smaller PLCs without advanced math a crude but quick routine follows.
I have used it in AB PLCs

XIC N7:0/0 MOV 0 N7:1 'if bit 0 set puts 0 in return registar
XIC N7:0/1 MOV 1 N7:1 'if bit 1 set puts 1 in return registar
.... same logic for all 16 bits
XIC N7:0/15 MOV 15 N7:1 'if bit 15 set puts 15 in return registar

If your PLC supports subroutines put it in a subroutine, load Y to N7:0 and it returns highest bit number in N7:1

Similar logic applies to Assembler Subroutine only use AND with immediate mask.

Let me know if you have a specific target machine and language and I will check to see if I have any avalable code.


Ralph
 
M

McGuire, Paul

Joe -

The simple formula is:
x = log(base2)( y )

Unfortunately, there are few log(base2) operations available in programming languages. You can get it by doing
x = log(baseX)( y ) / log(baseX)( 2 )

Typically you can get at logs based on 'e' (the transcendental number 2.718281828...) using the ln function, so this would look like:
x = ln(y) / ln(2)
This is what you would use if writing an Excel function, for example.

However, in computer programming, one typically wishes to avoid floating point functions - they are very slow, and sometimes are not even available.

Instead, two approaches you can use that do not involve floating point arithmetic are: - bit shifting / counting - lookup table

If programming in C or C++, you can use the >> operator (that is the integer bit-shift operator, not to be confused with C++ streaming operator) to shift an integer one bit to the right - then test the low bit to see if it is set. Or create a static array of values to match on, and explicitly test for each one, brute force.

-- Paul McGuire
KLA-Tencor Control Solutions
 
H

Hunter Farris

Use a log function to do this calculation. LOG(base2)Y=X . It would be much easier using a word comparison block as apposed to a math block.

Hunter Farris
 
A
Hi, Joe. I don't understand your question. If y is an integer, the answer is trivial: x is the sum of all the powers of two that correspond to the positions in the data word where there is a bit set to one. If y is a floating-point numer, you get the same sort of solution converting it (with a standard conversion routine) to integer form.
Hope to help. Andrea.
 
M

Michael Griffin

Is it safe to assume that only one bit is turned on in the word at one time? If more than one bit is on, the following methods can also be used
to find the most or least significant bit.

a) One way is to right (or left) shift the word and count the number of shifts required to move the bit out of the register. This works easily enough if you have shift, test (or register underflow or overflow), and looping instructions. If you can't loop, you may be able to spread the operation over multiple scans (this is slightly more complicated though). Remember of course to check for zero to avoid infinite loops.

b) One word can be tested with a maximum of 16 compare instructions. AND the word with a series of suitable constants (1, 2, 4, 8, 16, etc.) and check each one for a non-zero result. This is a viable alternative to the previous if you can't shift and test for some reason. It may even have a lower instruction overhead than the previous method depending upon relative
instruction timing for your particular CPU.

c) Some PLCs offer this as a built-in instruction (e.g. encode/decode on a Siemens S7-200).

Of course, if the PLC Archive site was ready, you would probably be able to find several examples of the above in there already.

**********************
Michael Griffin
London, Ont. Canada
[email protected]
**********************
 
B

Blunier, Mark

2^0 = 00000001
2^1 = 00000010
2^2 = 00000100
2^3 = 00001000
2^4 = 00010000
2^5 = 00100000
2^6 = 01000000
2^7 = 10000000

fred = 0
loop
left shift byte
if "1" is pushed out exit loop
fred=fred+1
endloop
power = 7-fred

Mark Blunier
Any opinions expressed in this message are not necessarily those of the
company.
 
W
Joe,

Someone else will invert the equation. But, there are some other ways to do it. If x is always an integer, you can rotate out the bits, counting the
number of shifts until you hit a 1 in the 2^0 bit position.

If the number may have more than one bit set, here's a fairly simple equation that will test an individual bit position:

BitStatus = !(( y - 2 ^ x ) == y)

This could be coded to execute very quickly in assembler.

Hope this helps.

Regards,

Willy Smith
Numatico SA
Costa Rica
 
Hi Joe,

In Allen-Bradley Enhanced PLCs, you can use DDT (Diagnostic Detect) operation that tells you the position of all the bits that are ON. This will work both for single or multiple ON bits. This is a very powerful operation. Might help.

Sahay
 
F

Francus, West (IndSys, GEFanuc, Albany)

Use a lookup table if these math functions (log, ln, etc.) are not available for your code.

West Francus
 
M

Michael Griffin

At 21:04 27/06/00 -0400, you wrote:
>At 12:33 27/06/00 -0500, Jansen, Joe wrote:
><clip>
>>I am trying to determine which bit position is on based on the value of a
>>data word. I would like to do this with a simple(?) formula. If I have 2^x
>>= y, how would I solve for x? This is what I would need.
><clip>

This is such an interesting subject that I put a little S5 function block together to demonstrate the "brute force" method (reproduced in full at the end of this letter). Take note - this is one of those "it looks like it ought to work, but I haven't actually tested this one" solutions. I'll try it out some day if I ever need it.

The algorithm is basically
L KFx ;x = a possible bit position,
A F255.y ;y = bit to test,
JC =DONE ;If bit was set, then we are done.

The "shift and test" type algorithm would work along the lines of:
SRCH : SRW 1 ;Shift the word right by one bit.
: JC =FINI ;If a bit just shifted out, we are done,
: TAK ;else swap the accumulators,
: I 1 ;increment the search counter,
: TAK ;swap accumulators again,
: JU =SRCH ;and repeat.
FINI :

Note that there is some set-up and clean up which is not shown for this one (more overhead than the "brute force" method, this just shows the
critical loop).

Note that *both* methods terminate after finding the first bit. However, if we examine the instruction timing on these (in micro-seconds):
Method 1: LOAD a constant = 2.4
AND a flag = 2.4
Conditional JUMP = 15

Total = 19.8 micro-sec. per bit.

Method 2: Shift Right = 34.4 (average)
Conditional jump 15 (x2) = 30
Accumulator swap 4.4 (x2) = 8.8
Increment ACCU1 1.2

Total = 74.4 micro-sec. per bit.

The above are timings for an S5-95U. Notice that the "brute force" method is almost 4 times faster! The reason for this is that the "brute force" method mainly uses instructions the PLC is optimised for. A different CPU would give different relative timing (do to different relative instruction performance).

I would estimate though that the "brute force" method uses approximately twice the memory (230 bytes) of the "shift and test" method (I'm guessing at the size of the second one). This means there is the potential for a trade off between speed and size (at least for an S5 PLC).
This is the sort of fiddly little algorithm which S5 statement list is particularly good at.

One other advantage the "brute force" method does have though, is that its so simple, it would be pretty difficult to get it wrong and do something silly like lock yourself into an infinite loop. This sort of consideration may be important when you don't have a lot of time for testing a new function block you've written.

=================================================================

BITS - FIND THE ORDINAL POSITION OF THE FIRST BIT IN A WORD.
28-JUN-00. M. GRIFFIN Siemens S5-95U
This function block will find the position in a word of the first
bit (starting from the lowest order bit), and output this position
(0 to 15) in the BPOS parameter. If no bits were set (the input
word was zero), then the ZERO parameter is set and the BPOS
parameter is set to 255.

SEGMENT 1

NAME: BITS
DECL: INPT I, W ;WORD TO SEARCH FOR THE FIRST BIT SET.
DECL: BPOS Q, BY ;POSITION OF BIT FOUND.
DECL: ZERO Q, BI ;TRUE IF NO BITS FOUND.
: ;Reset the error flag.
: A =ZERO
: RB =ZERO
:
: L =INPT ;Get the input work,
: T FW254 ;and save it in a scratch flag word.
:
: L KF +0 ;Set the first bit position constant.
: A F255.0 ;Is the first bit set?
: JC =DONE ;If yes, then we are done.
:
: L KF +1 ;Else, set the next bit position...and repeat for
: A F255.1 ;the remaining possible bit positions.
: JC =DONE
:
: L KF +2
: A F255.2
: JC =DONE
:
: L KF +3
: A F255.3
: JC =DONE
:
: L KF +4
: A F255.4
: JC =DONE
:
: L KF +5
: A F255.5
: JC =DONE
:
: L KF +6
: A F255.6
: JC =DONE
:
: L KF +7
: A F255.7
: JC =DONE
:
: L KF +8
: A F254.0
: JC =DONE
:
: L KF +9
: A F254.1
: JC =DONE
:
: L KF +10
: A F254.2
: JC =DONE
:
: L KF +11
: A F254.3
: JC =DONE
:
: L KF +12
: A F254.4
: JC =DONE
:
: L KF +13
: A F254.5
: JC =DONE
:
: L KF +14
: A F254.6
: JC =DONE
:
: L KF +15
: A F254.7
: JC =DONE
:
: L KF +255 ;If no bits were set, then default the result
: ;out of range,
: AN =ZERO ;and set the error flag.
: S =ZERO
:
DONE : T =BPOS ;Send the result to the output parameter.
:
: BE

**********************
Michael Griffin
London, Ont. Canada
[email protected]
**********************
 
Math answer to math question:
Joe, your equation (as stated);y=2^x
Therefore: x=log(2)y simply.

Someone gave sharp and right reply.
Fixed point or floating point arithmetic
are slightly differently implemented in computer
approximations.
One excellent source for the elementary approximations is:
SOFTWARE MANUAL FOR THE ELEMENTARY FUNCTIONS
by William J. CODY, JR
Argonne National Laboratory.[Prentice Hall]
This book sold out as printed (until recently
was not on reprint) I have only a xeros copy from McGill university (Montreal).
Generaly, at least three extra bits are carried
in floating point, the order of operations is considered. Approximations is an art. It also largely depends upon the arithmetic architecture
of the particular machine.
Not as easy.
Be cautious if you attempt comparing two
numbers. It reverts to substracting one from the other. If they are very close, then, their difference may show infinite !!!
 
C

Christopher Griffin

The quickest algorithm I can think of is reproduced in C as follows, of course it would run quicker if in assembler and if the loop were
unwrapped, and redundant operations removed.

/* assume 16 bit word */

extern int_16 WORDTOTEST;
int_16 MASK[]={0xff00, 0xf0f0, 0xcccc, 0xaaaa};
int resulting_bit;
int loop;

resulting_bit=0;
for(loop=0;loop<4;loop++)
{
resulting_bit=resulting_bit<<1;
if(WORDTOTEST & MARK[loop] !=0)
{
WORDTOTEST = WORDTOTEST & MARK[loop];
resulting_bit++;
}
else
{
WORDTOTEST = WORDTOTEST & ~(MARK[loop]);
}
}

This algorithm will terminate after log2(N) iterations, where N is the number of bits. resulting_bit will contain the number of the most
significant set bit, and WORDTOTEST will contain the actual bit.

The algorithm allows WORDTOTEST to contain more than one set bit !

Run it by hand to see how it works !
 
A
> The quickest algorithm I can think of is reproduced in C as follows,
> of course it would run quicker if in assembler and if the loop were
> unwrapped, and redundant operations removed.

...

Now, not to pick on you here, but I don't think that putting it assembler would be worth it. Compilers do a pretty darn good of optimizing code
(depending on the compiler of course), and time spent putting the thing to assembly and unrolling the loops could be used for other things.

Also, C is much more likely to be readable to the next person to come across your code, and that the moment you write it in assembly, you through away any chance of using the same code on a different hardware architecture.

I'm curious. How many people doing using PCs in automation write in assembly?
 
S
> I'm curious. How many people doing using PCs in automation write in assembly? <

I plead guilty to using assembler on various platforms for time critical stuff. I have worked with a few compilers on different platforms and would usually say that I can write code between 10-30% tighter and faster in assembler than the compiler.

I don't vouch for readability or maintainability though...

Debian GNU User
Simon Martin
Project Manager
Isys
mailto: [email protected].cl

There is a chasm of carbon and silicon the software cannot bridge
 
S
Aside from the few CPUs that have instructions specifically for this sort of thing, c will do just fine. The question as stated had *one* bit set. Brute force will yield a surprisingly fast chunk of code since there is no overhead due to loops and extra variables:

if ((Word2Test & 0x8000) != 0)
{
result = 16;
}
else if ((Word2Test & 0x4000) != 0)
{
result = 15;
}
else if ((Word2Test & 0x2000) != 0)
{
result = 14;
}

... etc..... etc .....

A switch/case statement is also worth considering and is probably equivalent, given a good compiler... and maybe less typing and more readable to boot.

If the data bits are randomly placed in all locations, the number of comparisons can be reduced by changing the above to a binary search
(something like):

if (Word2Test <= 0x0080)
{ /* eliminate half the choices, must be in bottom
byte */
if (Word2Test <= 0x0008)
{ /* eliminate another half */
if (Word2Test <= 0x0004)
{ /* eliminate anther half */
if (Word2Test < 0x0002)
{ /* only 0 and 1 remain */
if (Word2Test < 0x0001)
{
result = 0;
{
else
{
result = 1;
}
}
else
{ /* was greater than = 2 */
if (Word2Test < 0x0003)
{
result = 2;
{
else
{
result = 3;
}
}


etc... etc... etc...

In fact, a compiler with a good optimizer will turn a switch/case statement into the binary tree for you!

KISS = keep it simple Sylvester -- simple code lets the compiler optimizers do their thing.

Cheers! and happy bit fiddling, steve
 
The fastiest way is:
if Y = 2^X then:

{
X = 0;
if (Y & 0xFFFF0000) X |= 0x10;
if (Y & 0xFF00FF00) X |= 0x08;
if (Y & 0xF0F0F0F0) X |= 0x04;
if (Y & 0xCCCCCCCC) X |= 0x02;
if (Y & 0xAAAAAAAA) X |= 0x01;
}

Ehud
 
Top