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
PROOF: First we consider the case . By Corollary 2.2.9,
We proceed by induction, assuming . Using Lemma 2.2.22 in the form
-- | |||
-- | |||
--- |
- | |||
--- | |||
- |
Our next lemma is applicable to both addition and subtraction, but involves a somewhat more complicated computation.
PROOF: Exhaustive testing yields
---- | |||
----- | |||
---- |
-- | |||
-- | |||
-- | |||
-- |
-- | |||
-- | |||
-- | |||
-- |
Suppose first that . Then and it follows that
- | |||
--- | |||
- |
Finally, suppose that . Then and hence , which implies that and
- | |||
--- | |||
- |
David Russinoff 2017-08-01