Previous page Next page Navigation bar

Calculator Programming Tutorial

Programming Building Blocks I

Examples

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
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 |ξ| Greater than or equal to 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.

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

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

Home

Programs

Tutorial

Preface

Introduction

Fundamentals

Building Blocks I

Introduction

Comments

Data Types

Numbers

Variables

Expressions

Control Flow I

Control Flow II

Subprograms

Basic I/O

Algorithms

A First Program

Examples

Introduction

Logical Ops

Bitwise Ops

Problem

Program

Code

Test

Pumpkins

Exercises

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card

References

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data