Next: Multiplication Up: Addition Previous: Leading One Prediction   Contents

# Trailing One Prediction

As we saw in Chapter 6, the process of rounding a bit vector often involves determining its degree of exactness. For this purpose, therefore, it is also useful to predict the trailing one of a sum, i.e., the least index at which a one occurs. The following lemmas provide methods for computing, in constant time, an integer that has precisely the same trailing one as the sum or difference of two given operands.

Note that the difference of -bit vectors and is commonly computed as a sum, using the identity -- , which leads to the formula

---

Thus, we are also interested in computing the trailing one of an incremented sum. This problem admits a particularly simple solution.

(top-thm-1) Let and be n-bit vectors, where . For all , if , then

PROOF: First we consider the case . By Corollary 2.2.9,

and exhaustive testing yields

Thus, by Lemmas 3.2.5 and 3.1.13,

We proceed by induction, assuming . Using Lemma 2.2.21 in the form

we may assume that

and need only show that

--

Let - and - . By inductive hypothesis,

----

By Lemmas 2.2.22, 3.2.4, and 3.1.12,
 -- -- ---

Therefore, it suffices to show that

-

Note that since , , and it follows that

Thus, by Lemmas 7.1.19 and 2.2.22 and Corollary 2.2.9,

 - --- -

Our next lemma is applicable to both addition and subtraction, but involves a somewhat more complicated computation.

(top-thm-2) Let and be n-bit vectors, where , and let be a 1-bit vector. Let

----

Then for all , if , then

PROOF: Exhaustive testing yields

and hence, by Corollary 2.2.9,

By Lemmas 3.1.13, 2.4.7, and 2.3.16,
 ---- -----

This establishes the case . For , we proceed by induction. Using Lemma 2.2.21 in the form

we may assume that

and need only show that

Let - - , , and
 ----

By Lemmas 3.1.12 and 2.2.22,
 -- -- -- --

and by Lemmas 2.4.7, 2.4.9, 3.1.6, and 2.2.22,
 -- -- -- --

Thus,

----

By inductive hypothesis,

--

But

--

Thus, it will suffice to show that

-

Suppose first that . Then and it follows that

By Lemma 7.1.15 and Corollary 2.2.9,
 - --- -

Finally, suppose that . Then and hence , which implies that and

By Lemmas 7.1.19 and 2.2.22 and Corollary 2.2.9,
 - --- -

Next: Multiplication Up: Addition Previous: Leading One Prediction   Contents
david.m.russinoff 2015-02-08