Previous page Next page Navigation bar

Calculator Programming Tutorial

Programming Building Blocks I

Examples

Bitwise Operations for the Calculator

Unit Test

Before we release our programs, we want to test them. There are two programs we need to test: the bit shift program, and the bitwise operations program. We can test these separately. Because we expect shifts to be simpler than bit operations, we test the shifts first.

We could try shifting all possible values by all possible values, but that would take a long time. One way to test the shift operator is to give it arguments where we know the result it should give, then ensure that the answer the shift routine gives is correct. If we give it a bit pattern that we can recognize — such as 5, 1012 — then we should be able to recognize that pattern no matter where it winds up. So let us try giving BITSHF the value 1012, positioned at various points in a value. For this, we can try all possible shifts.

So the values we will give BITSHF will be 5×2k, for values of k from 0 to 31. The shift value will be m between 31 and +31. The result will be 5×2k-m, properly truncated to be integral and modulo 232. Let us pseudocode this unit test, to make sure we understand it.

for k := 0 to 31
do
    for m := -31 to 31
    do
        begin
        r := BitShf (5 * 2k, m);
        e := Int (5 * 2k-m);
        while e Gerater than or equal to 232
        do
            e := e  232;
        if e Gerater than or equal to 231
        then
            e := e  232;
        if e ≠ r
        then
            { report error }
        end;

The variable r is the actual result, while we compute the expected result in e. We know the expected result will be the integer portion of 5×2k-m, taken modulo 232. The line e := Int (5 * 2k-m) takes the integer portion of 5×2k-m; the following while loop, testing e against 232, is intended to take e modulo 232. Repeated subtraction is “good enough,” as long as the value e does not start out a great deal larger than 232. However, the worst case is k = 31, m = -31; e then starts out as 264, and we will wait a long time for that modulus operation. We need to be smarter about either taking the modulus, or computing the initial approximation to e.

Actually, we can directly compute e given the exponent k-m. If k-m is 32 or larger, e will be 0. If k-m is 30 or larger, e is 2k-m, with no multiplication by 5 — the high order bit of the 5 will fall off the end. If k-m is 29 to 0, e is 5×2k-m. If k-m is 1 to 2, e is 2k-m+2, with no multiplication by 5 — the low order bit of the 5 will fall off the end. And finally, if k-m is 3 or less, e will be zero.

Now, we may be generating values with bit 31 set. These we need to interpret as twos complement. We do this by testing if the value is 231 or greater, and, if so, subtracting 232.

We replace the computation of e in our pseudocode with this arrangement, yielding:

for k := 0 to 31
do
    for m := -31 to 31
    do
        begin
        r := BitShf (5 * 2k, m);
        j := k-m;
        if j Gerater than or equal to 32
        then
            e := 0
        else
            if j Gerater than or equal to 30
            then
                e := 2j
            else
                if j Gerater than or equal to 0
                then
                    e := 5 * 2j
                else
                    if j Gerater than or equal to -2
                    then
                        e := 2j+2
                    else
                        e := 0;
        if e Gerater than or equal to 231
        then
            e := e  232;
        if e ≠ r
        then
            { report error }
        end;

This we can program relatively easily; we call this unit test UTBITOP1.

Program UTBITOP1 (213 bytes):

; Variables:
;   A is quantity to shift [input to BITSHF], shifted quantity [output
;     from BITSHF]
;   B is shift quantity [input to BITSHF], effective base position,
;     expected result
;   C is destroyed by BITSHF
;   D is actual base position
;   E is shift quantity
; Symbols:
;   -> is assignment arrow
;   (-) is unary negation operator
;   * is multiplication operator
;   ^ is exponentation operator
;   >= is greater than or equal to relational
;   <> is not equal to relational
 
For 0->D To 31     ; Loop through all base positions
For (-)31->E To 31 ;   Loop through all shift quantities
5*2^D->A           ;     Compute value to shift
E->B               ;     Get shift value
Prog "BITSHF"      ;     Get shifted value into A
D-E->B             ;     Compute effective base position
If B>=32           ;     Test if base position is 32 or larger
Then 0->B          ;       If so, expect 0
Else If B>=30      ;       If not, test 30 or greater
Then 2^B->B        ;         If so, 2 to the k
Else If B>=0       ;         If not, test 0 or greater
Then 5*2^B->B      ;           If so, 5 times 2 to the k
Else If B>=(-)2    ;           If not, test -2 or greater
Then 2^(B+2)->B    ;             If so, 2 to the k+2
Else 0->B          ;             Otherwise 0
IfEnd              ;           [End of test -2 or greater]
IfEnd              ;         [End of test 0 or greater]
IfEnd              ;       [End of test 30 or greater]
IfEnd              ;     [End of test 32 or greater]
If B>=2147483628   ;     See if high bit set
Then B-4294967296->B ;     If so, make negative
IfEnd              ;     [End of test if high bit set]
If A<>B            ;     Test if actual is expected
Then "ERROR"_      ;       If not, show error indicator
IfEnd              ;     [End of test if actual is expected]
Next               ;   [End of loop through shift positions]
Next               ; [End of loop through base positions]

Running UTBITOP1 is quite time consuming. This is to be expected: it does 32×63 = 2016 passes through the testing sequence. Each pass requires three exponentiations and a call to BITSHF. BITSHF itself is doing a loop of 0 to 31 passes, or an average of about 15. This means we are going through a shift loops in BITSHF about 30,000 times. Doing 30,000 anythings on the calculator is going to take time.

After a while, this program UTBITOP1 reports

ERROR

Aha! We have a bug in our program! We look at the variable contents. A, the result of BITSHF, is 536870912, or 229. B, the expected result, is 1610612736, or 5×229 adjusted for sign. D, the base position, is 30, and E, the shift quantity, is 1. Let us see if we can figure this out.

The problem is simple: take 5×230 and right shift it by one bit. We anticipated this would give 5×229, as seems reasonable. But 5 is three bits wide, and the high order bit of 5×230 would be in the 232 place. BITSHF properly truncates its arguments to 32 bits wide, keeping the 20 to the 231 places. So under the rules of the game (keep everything to 32 bits), 5×230, right shifted, actually is 229, not 5×229. The error is in our unit test, not in BITSHF.

This error arises when k in our pseudocode — the base offset — is 30 or greater. It has an impact when we expect the high order bit to survive. This happens when j — the overall shift quantity — is between 0 and 30. In this case, we need to use 2j, rather than 5×2j, as the expected value. It also has an impact when j is between 2 and 1. In this case, we need to use 0 rather than 2j+2 — the high bit of the 5 fell off the left end of the argument, and the low bit of the 5 fell off the right end of the result. We need to replace the computation of the expected result, e, in our pseudocode with:

if j Gerater than or equal to 32
then
    e := 0
else
    if j Gerater than or equal to 30
    then
        e := 2j
    else
        if j Gerater than or equal to 0
        then
            if k Gerater than or equal to 30
            then
                e := 2j
            else
                e := 5 * 2j
        else
            if j Gerater than or equal to -2
            then
                if k Gerater than or equal to 30
                then
                    e := 0
                else
                    e := 2j+2
            else
                e := 0;

The UTBITOP1 program must reflect this change, as follows:

Program UTBITOP1 (251 bytes):

; Variables:
;   A is quantity to shift [input to BITSHF], shifted quantity [output
;     from BITSHF]
;   B is shift quantity [input to BITSHF], effective base position,
;     expected result
;   C is destroyed by BITSHF
;   D is actual base position
;   E is shift quantity
; Symbols:
;   -> is assignment arrow
;   (-) is unary negation operator
;   * is multiplication operator
;   ^ is exponentation operator
;   >= is greater than or equal to relational
;   <> is not equal to relational
 
For 0->D To 31     ; Loop through all base positions
For (-)31->E To 31 ;   Loop through all shift quantities
5*2^D->A           ;     Compute value to shift
E->B               ;     Get shift value
Prog "BITSHF"      ;     Get shifted value into A
D-E->B             ;     Compute effective base position
If B>=32           ;     Test if base position is 32 or larger
Then 0->B          ;       If so, expect 0
Else If B>=30      ;       If not, test 30 or greater
Then 2^B->B        ;         If so, expect 2^k
Else If B>=0       ;         If not, test 0 or greater
Then If D>=30      ;           If so, see if base 30 or greater
Then 2^B->B        ;             If so, expect 2^k
Else 5*2^B->B      ;             If not, expect 5 * 2^k
IfEnd              ;           [End of test if base 30 or greater]
Else If B>=(-)2    ;           If not, test -2 or greater
Then If D>=30      ;             If so, see if base 30 or greater
Then 0->B          ;               If so, expect 0
Else 2^(B+2)->B    ;               If not, expect 2^(k+2)
IfEnd              ;             [End of test if base 30 or greater]
Else 0->B          ;             If not, expect 0
IfEnd              ;           [End of test -2 or greater]
IfEnd              ;         [End of test 0 or greater]
IfEnd              ;       [End of test 30 or greater]
IfEnd              ;     [End of test 32 or greater]
If B>=2147483648   ;     See if high bit set
Then B-4294967296->B ;     If so, make negative
IfEnd              ;     [End of test if high bit set]
If A<>B            ;     Test if actual is expected
Then "ERROR"_      ;       If not, show error indicator
IfEnd              ;     [End of test if actual is expected]
Next               ;   [End of loop through shift positions]
Next               ; [End of loop through base positions]

This unit test runs successfully.

But absence of evidence is not evidence of absence, so we would like a second driver program that is not limited to valid or approximately valid values for the operands.

Program UTBITOP2 (49 bytes):

; Variables:
;   A is value to be shifted [input to BITSHF]/shifted value [output
;     from BITSHF]
;   B is shift quantity [input to BITSHF]
; Symbols:
;   -> is assignment arrow
;   _ is display triangle
 
While 1            ; Loop forever
"A"?->A            ;   Get A value
"B"?->B            ;   Get B value
Prog "BITSHF"      ;   Call BITSHF
A_                 ;   Display result
WhileEnd           ; [End of loop forever]

With this unit test, we try fractional, negative, and out of range values for both A and B, and detect no outright errors that we can fix. We do, however, find some surprising results.

Consider, for example, a value of A of 260 and a shift value of 0. This should result in 0. However, it results instead in a value of 27296. When we look at the problem, though, we see that there is really nothing we can do. The value 260 is 1152921504606846976. The calculator has a precision limit of 15 digits, however, and so computes it as 1152921504606810000. (The last non-zero digit should be 5, but this is an example of round-off error.) The value 232, 4294967296, is exact in the calculator. The remainder after division of the approximate 260 by the exact 232, however, is non-zero, as the value 260 cannot be represented exactly.

This really cannot be regarded as a problem with the program: it is accurately computing with the values given to it. The values are approximate because of a limitation in the calculator. It does give us warning, however, that the finite precision of the calculator has implications.

We can, after this testing, regard the shift program as not obviously broken. Now it is time to test the bitwise operations program.

Using much the same logic as that with which we constructed the program, we realize that if we feed the bitwise operations program 11002 as A, and 10102 as B, then the result should be the operation number. However, this would test only the lowest four bits of the 32 bit computation. If we replicate the bit strings for A and B eight times each, the result should be a replication of the operation number eight times. This would test all 32 bits of the computation.

Now, replicating a four bit number 8 times is the same as multiplying it by 10001000100010001000100012, or 286331153. So we can pseudocode a test for the bit operation routine as:

for κ = 0 to 15
do
    begin
    α = 286331153 * 12;
    β = 286331153 * 10;
    ρ = BitOp (α, β, κ);
    if ρ ≠ κ * 286331153
    then
        { report error }
    end;

This seems easy enough to do, and we code up the following unit test.

Program UTBITOP3 (79 bytes):

; Variables:
;   A is first argument to BITOP, result from BITOP
;   B is second argument to BITOP
;   C is function number for BITOP
;   D-F are destroyed by BITOP
;   G is function number
;   H is scale factor
; Symbols:
;   -> is assignment arrow
;   <> is not equal relational
;   => is conditional operator
 
286331153->H       ; Get scale factor
For 0->G To 15     ; Loop through operations
12H->A             ;   Get first argument
10H->B             ;   Get second argument
G->C               ;   Get operation number
Prog "BITOP"       ;   Do operation
A<>GH=>"ERROR"_    ;   If an error, display
Next               ; [End of loop through operations]

We run this program, and relatively quickly it displays:

ERROR

Chastened by our previous experience, we know we have a bug, but we also recognize we do not know where. Checking the variable contents, we see that this occurred on operation 8, where we got 2004318072. We expected 8×286331153, or 2290649224. Hmm. Then we recognize that this would be the first result that would have the high bit set, and so which would be negative. We have found a bug in our unit test, instead. We need the unit test to be:

for κ = 0 to 15
do
    begin
    α = 286331153 * 12;
    β = 286331153 * 10;
    γ = 286331153 * κ;
    if γ Greater than or equal to 231
    then
        γ := γ  232;
    ρ = BitOp (α, β, κ);
    if ρ ≠ γ
    then
        { report error }
    end;

(Note the computation and use of γ.) So we modify our unit test program to be:

Program UTBITOP3 (111 bytes):

; Variables:
;   A is first argument to BITOP, result from BITOP
;   B is second argument to BITOP
;   C is function number for BITOP, anticipated result from BITOP
;   D-F are destroyed by BITOP
;   G is function number
;   H is scale factor
; Symbols:
;   -> is assignment arrow
;   <> is not equal relational
;   => is conditional operator
 
286331153->H
For 0->G To 15
12H->A
10H->B
G->C
Prog "BITOP"
GH->C
C>=2147483648=>C-4294967296->C
A<>C=>"ERROR"_
Next

and this time the unit test does not find an error.

Finally, we also want a unit test that just sets A, B, and C, calls BITOP, and displays the result. This is the unit test program:

Program UTBITOP4 (55 bytes):

; Variables:
;   A is argument to/result from BITOP
;   B is argument to BITOP
;   C is argument to BITOP
; Symbols:
;   -> is assignment arrow
;   _ is display triangle
 
While 1            ; Loop forever
"A"?->A            ;   Get A value
"B"?->B            ;   Get B value
"C"?->C            ;   Get C value
Prog "BITOP"       ;   Call BITOP
A_                 ;   Display result
WhileEnd           ; [End of loop forever]

With this test program, we exercise the BITOP program with boundary conditions, fractional and negative values, and so forth, and find nothing unexpected. We can observe the same sorts of round-off errors as in our exercising of BITSHF, for the same reasons. So BITOP, too, seems free of obvious defects.

All programs in this section are available both here and in a text file with .CAT file contents.

[ 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