On the other hand no such simplification is possible in the second algorithm for division, but (as is often true about ``real'' machines) if is a significantly slower operation than the others, then it may be worthwhile to perform the extra steps.

Since most of our operations are on *binary* computers (so that
*M* = 2^{n}), we have special procedures to multiply and divide by powers
of 2. We now describe these procedures based on some new fundamental
operations.

**left shift**- The operation of multiplication by a power of 2
:where (
*W*×{0,...,*n*- 1}*W*×*W**a*,*k*) (*c*,*d*) which satisfies2^{k . }*a*=*c*^{ . }*M*+*d* **right shift**- The operation of division by a power of 2
:where (
*W*×{0,...,*n*- 1}*W*×*W**a*,*k*) (*c*,*d*) which satisfies*a*^{ . }*M*/2^{k}=*c*^{ . }*M*+*d* **zero**- The operation of finding out whether something is
non-zero; this is also the ``bit-wise and'' operation
:where
*W*{0, 1}*a*0 if*a*is zero and 1 if it is non-zero. **bitwise negation**- The difference from
*M*- 1; this is also the operation of bitwise negation:where*W**W**a**M*-*a*- 1. **integer log to the base 2**- The operation of finding the
integer part of the logarithm to base 2
:where
*W*{0,...,*n*- 1}*a**k*which satisfies 2^{k}*a*< 2^{k}. This also counts the number of right shifts possible without carry. **left shift count**- The number of left shifts possible without carry.
:where
*W*{0,...,*n*- 1}*a**k*which satisfies*M*/2 2^{k}*a*<*M*.

Given a small integer *k* and an integer
(*u*_{1}^{ ... }*u*_{q}), we can
construct
(*v*_{0}^{ ... }*v*_{q}) satisfying
(*v*_{0}^{ ... }*v*_{q}) = 2^{k ... }(*u*_{0}^{ ... }*v*_{q}) as follows.
We compute
(*u*_{i}, *k*) = (*s*_{i - 1}, *t*_{i}),
(*s*_{i}, *t*_{i}, 0) = (*v*_{i}, 0) and
*v*_{0} = *s*_{0}. Similarly, we can easily compute division by 2^{k}. We can
also find the precise power of 2 that divides any integer
(*u*_{1}^{ ... }*u*_{q}) (also called the 2-adic value of this integer). Clearly all
these operations are of order linear in *q*. We can further extend
this procedure quite easily to integers
(*k*_{1}^{ ... }*k*_{r}) of size *r*
with only *r* extra steps (to divide *k* by *M*).

Finally, we can also use the given basic operations to implement comparisons between integers which are linear in the size of the integers concerned.

We summarise our investigations in the following table

Operation | Time taken |

Addition/Subtraction | Linear |

Multiplication/Division by small integers | Linear |

Multiplication/Division | Quadratic |

Multiplication/Division by powers of 2 | Linear |

Comparison | Linear |

2-adic value | Linear |