Constant Time Execution Equivalents

In what follows are presented some constant time equivalents for relative operators. The Boolean operators ^,! and % are used for that purpose. The operator ^ is the Ex-OR operator and ! is the Not operator and % is the modulus operator.

Equivalent for Equality: if ( n==p) then y = x can be written as y = x * ( ! ( n ^ p ) );
Equivalent for >= : if( n>=p) then y=x can be written as y = x * ( ! ! ( ( n / p ) ^ 0 ) );

Here follows some if statements and their constant time equivalents.

Wrap Around : x = x ++; if (x >= MAX_SIZE) x =0 ; can be written as x = (x+1)%MAX_SIZE;
Wrap About : x = x--; if (x <0) x = MAX_SIZE-1; can be written as x = (x+MAX_SIZE-1)%MAX_SIZE;

Even and Odd Number validation:

To make a number Even: If ( x % 2 ) x --; can be written as x &= ~0x01;
To make a number Odd: If (!(x %2) ) x ++; can be written as x |= 0x01;

The following table summarizes the constant time equivalents and their general expressions for some of the common program statement blocks that we encounter in our daily life.

Program Statement Block

Constant Time Equivalent

x++;

if(x >= MAX_SIZE) x = 0;

x = ( x + 1 ) % MAX_SIZE;

x--;

if(x < 0) x = MAX_SIZE - 1;

x = (x + MAX_SIZE � 1) % MAX_SIZE;

x = x + increment;

if(x >= MAX_SIZE) x = 0;

x = (x + increment) % MAX_SIZE;

x = x - decrement;

if(x < 0) x = MAX_SIZE - 1;

x = (x + MAX_SIZE � decrement) % MAX_SIZE;

x = x + increment;

if(x >=MAX_SIZE) x = UPPER LIMIT;

x = x + increment;

x = (x * (!((x/MAX_SIZE)^0))) + (UPPER LIMIT * (!!((x/MAX_SIZE)^0)));

x = x - decrement;

if(x < MIN_SIZE) x = LOWER LIMIT;

x = x - decrement;

x = (LOWER LIMIT * (!(x / MIN_SIZE)^0))) + (x * (!!(( x / MIN_SIZE)^0)));

if(x % 2) x--;

x &= ~0x01 ;

if(x % 2) x++;

x = (x & (~0x01)) + ((x - (x & (~0x01))) << 1) ;

if(!(x % 2)) x++;

x |= 0x01 ;

if(!(x % 2)) x--;

x = (x | 0x01) - ((x - (x | 0x01)) << 1) ;

Few Boolean Tips:

A number x is a power of two, if and only if the bitwise AND of x with (x-1) is zero. That is, x is a power of 2 if and only if (x & (x-1)) == 0;
When x is a power of 2, only one bit would be set to 1 in its binary representation, say in n th position. For x-1, all bits below n would be set to 1 and hence, x bitwise AND with x-1 would have no common bits set, resulting in Zero.
To convert lower case characters to upper case characters and vice versa, all that is required is just toggling one bit. For example, A=0x41 and a=0x61; Just set a bit to 1 in 0x41 to make it 0x61 and A would get modified to a; No matter which way to convert, just flip the bit using the code below:
```
ConvertCase(char* c)
{
  *c = *c ^ 32;    // *c = *c ^ ('a' - 'A');
}
```

Converting Arithmetic and Relational expressions to Propositional Logic CNF Equations

In the below table are presented few CNF expressions and their equivalent arithmetic expression.

Symbols such as x, y, z, a, b, c etc... each denote a single boolean value that can take either true or false value.

We use ≠ to represent inequality, and ! to denote logical Not. The sign = is used to denote equality (and not assignment). Thus it is same as == of C/C++; For example, the expression if x then y=1 means whenever x is true, y also should be true, which is same as if x then assert(y==1) in C++.

For CNF expressions we use ∧ to represent logical AND, ∨ to represent logical OR, and - to represent complement. Thus x and -(-(x)) should essentially mean the same.

Expression	CNF Equation
if x then y=1	(-x ∨ y)
if x then y=0	(-x ∨ -y)
x ≥ y	(x ∨ -y)
x ≤ y	(-x ∨ y)
x = y	(-x ∨ y) ∧ (x ∨ -y)
x ≠ y	(x ∨ y) ∧ (-x ∨ -y)
x > y	(x ∨ y) ∧ (x ∨ -y) ∧ (-x ∨ -y)
x < y	(x ∨ y) ∧ (-x ∨ y) ∧ (-x ∨ -y)
(x & y) = z	(-x ∨ -y ∨ z) ∧ (x ∨ -z) ∧ (y ∨ -z)
if(x) then (a = b)	(-x ∨ a ∨ -b) ∧ (-x ∨ -a ∨ b)
if(x) then (a ≠ b)	(-x ∨ a ∨ b) ∧ (-x ∨ -a ∨ -b)
if(!x) then (a = b)	(x ∨ a ∨ -b) ∧ (x ∨ -a ∨ b)
if(!x) then (a ≠ b)	(x ∨ a ∨ b) ∧ (x ∨ -a ∨ -b)
if(x & y) then (a = b)	(-x ∨ -y ∨ a ∨ -b) ∧ (-x ∨ -y ∨ -a ∨ b)
if(!x & !y) then (a = b)	(x ∨ y ∨ a ∨ -b) ∧ (x ∨ y ∨ -a ∨ b)
if(x = y) then (a = b)	(-x ∨ -y ∨ -a ∨ b) ∧ (-x ∨ -y ∨ a ∨ -b) ∧ (x ∨ y ∨ a ∨ -b) ∧ (x ∨ y ∨ -a ∨ b)

CNF Expression for Full-Adder

          |i (Carry-in)
          |
        |‾‾‾‾‾|
  x-----|     |----S (Sum)
        | F A |
  y-----|_____|----C (Carry-out)

In the above full-adder, inputs are x, y and i, while the outputs are s and c. Equations are as below:

S ≡ (x + y + i) % 2 ≡ x ⊕ y ⊕ i;

C ≡ (x + y + i) / 2 ≡ x.y + x.i + y.i;

CNF for the Carry-out is:

(x ∨ y ∨ -c) ∧ (x ∨ i ∨ -c) ∧ (y ∨ i ∨ -c) ∧ (-x ∨ -y ∨ c) ∧ (-x ∨ -i ∨ c) ∧ (-y ∨ -i ∨ c)

CNF for the Sum is:

(x ∨ y ∨ i ∨ -s) ∧ (x ∨ -y ∨ -i ∨ -s) ∧ (-x ∨ y ∨ -i ∨ -s) ∧ (-x ∨ -y ∨ i ∨ -s) ∧ (-x ∨ -y ∨ -i ∨ s) ∧ (-x ∨ y ∨ i ∨ s) ∧ (x ∨ -y ∨ i ∨ s) ∧ (x ∨ y ∨ -i ∨ s)

P.GopalaKrishna