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, 101_{2} — then we should be able to recognize
that pattern no matter where it winds up.
So let us try giving BITSHF the value 101_{2}, 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×2^{k},
for values of k from 0 to 31.
The shift value will be m between –31 and +31.
The result will be 5×2^{k-m}, properly truncated to
be integral and modulo 2^{32}.
Let us pseudocode this unit test, to make sure we understand it.

fork := 0to31doform := -31to31dobeginr := BitShf (5 * 2^{k}, m); e := Int (5 * 2^{k-m});whilee 2^{32}doe := e – 2^{32};ife 2^{31}thene := e – 2^{32};ife ≠ rthen{ 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×2^{k-m}, taken modulo 2^{32}.
The line e := Int (5 * 2^{k-m}) takes the integer portion of
5×2^{k-m}; the following while loop, testing e against
2^{32}, is intended to take e modulo 2^{32}.
Repeated subtraction is “good enough,” as long as the
value e does not start out a great deal larger than 2^{32}.
However, the worst case is k = 31, m = -31; e then starts out as
2^{64}, 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
2^{k-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×2^{k-m}.
If k-m is –1 to –2, e is 2^{k-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 2^{31} or greater, and,
if so, subtracting 2^{32}.

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

fork := 0to31doform := -31to31dobeginr := BitShf (5 * 2^{k}, m); j := k-m;ifj 32thene := 0elseifj 30thene := 2^{j}elseifj 0thene := 5 * 2^{j}elseifj -2thene := 2^{j+2}elsee := 0;ife 2^{31}thene := e – 2^{32};ife ≠ rthen{ 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 2^{29}.
B, the expected result, is –1610612736, or 5×2^{29}
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×2^{30} and right shift
it by one bit.
We anticipated this would give 5×2^{29}, as seems
reasonable.
But 5 is three bits wide, and the high order bit of 5×2^{30}
would be in the 2^{32} place.
BITSHF properly truncates its arguments to 32 bits wide, keeping the
2^{0} to the 2^{31} places.
So under the rules of the game (keep everything to 32 bits), 5×2^{30},
right shifted, actually *is* 2^{29}, not 5×2^{29}.
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 2^{j}, rather than 5×2^{j},
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 2^{j+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:

ifj 32thene := 0elseifj 30thene := 2^{j}elseifj 0thenifk 30thene := 2^{j}elsee := 5 * 2^{j}elseifj -2thenifk 30thene := 0elsee := 2^{j+2}elsee := 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 2^{60} 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 2^{60} 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 2^{32}, 4294967296, is exact in the calculator.
The remainder after division of the approximate 2^{60} by the
exact 2^{32}, however, is non-zero, as the value 2^{60}
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 1100_{2}
as A, and 1010_{2} 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 1000100010001000100010001_{2}, or 286331153.
So we can pseudocode a test for the bit operation routine as:

forκ = 0to15dobeginα = 286331153 * 12; β = 286331153 * 10; ρ = BitOp (α, β, κ);ifρ ≠ κ * 286331153then{ 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κ = 0to15dobeginα = 286331153 * 12; β = 286331153 * 10; γ = 286331153 * κ;ifγ 2^{31}thenγ := γ – 2^{32}; ρ = 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 ]

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

Test

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card