We decided we would condition our operands by truncating them to integers, then taking them modulo 232. Taking the operand modulo 232 is, mathematically, simple. We need only subtract out all multiples of 232, then add 232 if the result is negative. The multiples of 232 in a given value ξ are given by 232Int(ξ/232). So ξ-232Int(ξ/232) should remove all multiples of 232.
While this works well if ξ is either small or large, it is possible for ξ-232Int(ξ/232) to compute as slightly larger than 232, due to round off. So we may need to perform this operation twice. The simplest approach is to place the operation in a loop, and do it as many times as required. We can write pseudocode to do this as follows:
while |ξ| 232 do ξ := ξ – 232 * int (ξ/232);
After this process, we will have a value between –(232-1) and 232-1. Adding 232 to the negative values results in a value between 0 and 232-1, which is the original operand ξ modulo 232. Our pseudocode for taking an operand modulo 232 is therefore:
while |ξ| 232 do ξ := ξ – 232 * int (ξ/232); if ξ < 0 then ξ := ξ + 232;
We can use the same technique as with the logical operators program, and use a function number that encodes the bitwise operation to be performed. We can determine the i-th bit of a value by dividing by 2i, discarding any fractional part, and taking the result modulo 2. We can set the i-th bit of the result by simply adding in 2i, assuming that the result does not already have a 2i component. The main computation loop can then be something like this:
μ := 1; ρ := 0; while μ < 232 do begin χ := κ; if (int (α div μ) mod 2) ≠ 0 then χ := χ div 4; if (int (β div μ) mod 2) ≠ 0 then χ := χ div 2; if (int (χ) mod 2) ≠ 0 then ρ := ρ μ; μ := 2 * μ end; return ρ;
Now, we can also recognize that the bits of the result can be computed in any order. The above program fragment starts the mask μ at 1 and left shifts it by one bit repeatedly until it is 232. We could just as easily start the mask μ at 231 and right shift it by one bit repeatedly until it is 0.
The value we get out of our operation be an integer between 0 and 232-1. However, we want the values 231 through 232-1 to become their corresponding negative values –231 through –1. We can do this by subtracting 232 if the value we get out is 231 or larger. This is the reverse of the last step of taking arguments modulo 232.
Our calculator program is starting to take shape now. We need to convert two operands to a form we can use — this implies either repeated code or a subroutine. We will use a subroutine. We need to compute the binary function — we will use logic similar to that above. We need to convert the result back out to a twos complement value — we will again use a subroutine.
As our internal form is unsigned, and as we do not want to be bothered with rounding to negative infinity rather than truncating, we arbitrarily decide we will do logical shifts.
It would be convenient to do all the shifting in one operation: mathematically, we could just multiply or divide by the appropriate power of 2, and be done. If the calculator were binary, this would work. However, the calculator actually is decimal. In the worst case, we need 10 digits to express the operand, and another 10 digits to express the shift factor. While we might squeak by on a right shift, we will simply run out of precision on a left shift. We need to do shifts one bit at a time, and adjust the intermediate result to be in our chosen range after each shift, as annoying as that is.
It would also be convenient for all shifting to take place in a single routine. The routine needs to differentiate between a right shift and a left shift. Fortunately, the shift value can be either positive or negative. We arbitrarily decide a positive shift count means a right logical shift, while a negative shift count means a left shift.
The pseudocode for our shifting routine will therefore be something like:
while σ > 0 do begin α := α div 2; σ := σ – 1 end; while σ < 0 do begin α := 2 * α; if α 232 then α := α - 232; σ := σ + 1 end;
where α is the value to be shifted and σ is the shift count.
Copyright © 2002 Brian Hetrick
Page last updated 27 January 2002.
Building Blocks I
Control Flow II
A First Program
Data Structures I
Building Blocks II
Data Structures II