We decided we would condition our operands by truncating them to
integers, then taking them modulo 2^{32}.
Taking the operand modulo 2^{32} is, mathematically,
simple.
We need only subtract out all multiples of 2^{32}, then
add 2^{32} if the result is negative.
The multiples of 2^{32} in a given value ξ are given
by 2^{32}Int(ξ/2^{32}).
So ξ-2^{32}Int(ξ/2^{32}) should remove all
multiples of 2^{32}.

While this works well if ξ is either small or large, it is
possible for ξ-2^{32}Int(ξ/2^{32}) to
compute as slightly larger than 2^{32}, 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|ξ| 2^{32}doξ := ξ – 2^{32}* int (ξ/2^{32});

After this process, we will have a value between –(2^{32}-1) and
2^{32}-1.
Adding 2^{32} to the negative values results in a value
between 0 and 2^{32}-1, which is the original operand ξ
modulo 2^{32}.
Our pseudocode for taking an operand modulo 2^{32} is
therefore:

while|ξ| 2^{32}doξ := ξ – 2^{32}* int (ξ/2^{32});ifξ < 0thenξ := ξ + 2^{32};

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 2^{i},
discarding any fractional part, and taking the result modulo 2.
We can set the i-th bit of the result by simply adding in 2^{i},
assuming that the result does not already have a 2^{i} component.
The main computation loop can then be something like this:

μ := 1; ρ := 0;whileμ < 2^{32}dobeginχ := κ;if(int (αdivμ)mod2) ≠ 0thenχ := χdiv4;if(int (βdivμ)mod2) ≠ 0thenχ := χdiv2;if(int (χ)mod2) ≠ 0thenρ := ρ μ; μ := 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 2^{32}.
We could just as easily start the mask μ at 2^{31} 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
2^{32}-1.
However, we want the values 2^{31} through 2^{32}-1
to become their corresponding negative values –2^{31} through
–1.
We can do this by subtracting 2^{32} if the value we get out
is 2^{31} or larger.
This is the reverse of the last step of taking arguments modulo
2^{32}.

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.

Before rushing off to write code, however, we need to recognize there are other bitwise operators we want. We want to do shifts, as well. A left shift by 1 bit is multiplication by 2, and a right shift by 1 bit is almost a division by 2. An arithmetic right shift actually divides by 2, and rounds to negative infinity. Consider: -1 is a string of 32 1 bits, and an arithmetic right shift of this leaves the value unchanged. (The sign bit, 1, is replicated into all vacated positions.) A logical shift, on the other hand, regards its argument as unsigned, and a right shift divides by 2 and truncates. The CFX-9850G calculator does not provide any insight, as it also lacks shift operators. JavaScript also does not provide any insight, as it explicitly provides both types of shift. So we can do whatever is convenient.

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σ > 0dobeginα := αdiv2; σ := σ – 1end;whileσ < 0dobeginα := 2 * α;ifα 2^{32}thenα := α - 2^{32}; σ := σ + 1end;

where α is the value to be shifted and σ is the shift count.

[ Previous page | Top of page | Next page ]

Copyright © 2002 Brian Hetrick

Page last updated 27 January 2002.

Tutorial

Building Blocks I

Control Flow II

Basic I/O

Algorithms

A First Program

Examples

Bitwise Ops

Program

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card