Previous page Next page Navigation bar

Calculator Programming Tutorial

Programming Building Blocks I


Bitwise Operations for the Calculator

Program Analysis

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 |ξ| Greater than or equal to 232
    ξ := ξ  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 |ξ| Greater than or equal to 232
    ξ := ξ  232 * int (ξ/232);
if ξ < 0
    ξ := ξ + 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
    χ := κ;
    if (int (α div μ) mod 2) ≠ 0
        χ := χ div 4;
    if (int (β div μ) mod 2) ≠ 0
        χ := χ div 2;
    if (int (χ) mod 2) ≠ 0
        ρ := ρ μ;
    μ := 2 * μ
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.

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 σ > 0
    α := α div 2;
    σ := σ  1
while σ < 0
    α := 2 * α;
    if α Greater than or equal to 232
        α := α - 232;
    σ := σ + 1

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

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 27 January 2002.

Brian’s Casio Calculator Corner







Building Blocks I



Data Types




Control Flow I

Control Flow II


Basic I/O


A First Program



Logical Ops

Bitwise Ops









Data Structures I


Program Attributes

Building Blocks II

Algorithm Analysis


Data Structures II

Abstract Types


Problem Analysis

Reference Card



Site Information

Your Privacy

Site Map


Site Technical Data