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.
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.22 in the form
we may assume that
and need only show that
Let - and - . By inductive hypothesis,
By Lemmas 2.2.23, 3.2.4, and 3.1.12,
-- | |||
-- | |||
--- |
Note that since , , and it follows that
Thus, by Lemmas 7.1.19 and 2.2.23 and Corollary 2.2.9,
- | |||
--- | |||
- |
Our next lemma is applicable to both addition and subtraction, but involves a somewhat more complicated computation.
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,
---- | |||
----- | |||
we may assume that
and need only show that
Let - - , , and
---- |
-- | |||
-- | |||
-- | |||
-- |
-- | |||
-- | |||
-- | |||
-- |
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.23 and Corollary 2.2.9,
- | |||
--- | |||
- |