We first write the routine that converts any value to as near as we can figure would be the 32 bit value corresponding to it if we had 32 bit values.

Program BITCANIN (75 bytes):

; Convert a value for bitwise operations: between 0 (inclusive) ; and 2^32 (exclusive). Do this by discarding all fractional digits ; and taking the result modulo 2^32. ; ; Variables: ; A on entry is value to be converted, and on exit is the converted ; value ; B on entry is arbitrary, and on exit is 2^32 ; Ans on exit is the converted value ; ; Symbols: ; -> is assignment arrow ; / is division operator ; < is less than relational Int A->A ; Discard all fractional parts 4294967296->B ; Get 2^32 While Int (A/B) ; While A has a multiple of 2^32 A-BInt (A/B)->A ; Subtract out all multiples WhileEnd ; [End of while A has a multiple of 2^32] While A<0 ; While A is less than 0 A+B->A ; take equivalent mod 2^32 WhileEnd ; [End of while A is less than 0] A ; Result in A and Ans

Now we write the routine that converts a generated value back out into a signed value.

Program BITCANOU (49 bytes):

; Make a value between 0 (inclusive) and 2^32 (exclusive) a standard ; output for bitwise operations: between -2^31 (inclusive) and 2^31 ; (exclusive). Do this by subtracting 2^32 if the value exceeds 2^31. ; ; Variables: ; A on entry is value to be made standard, and on exit is the value ; made standard ; B on entry is arbitrary, and on exit is 2^32 ; Ans on exit is the value made standard ; ; Symbols: ; > is greater than operator ; => is conditional operator ; -> is assignment arrow Prog "BITCANIN" ; Make 32 bits and get 2^32 into B A>2147483647=>A-B->A ; Map if necessary A ; Return value in A and Ans

Note how the first subroutine is defined as leaving a particular value lying around, and the second subroutine uses this value. This will happen again in our third subroutine, which actually performs the bitwise operations. As with the BOOLOP routine, we ensure the function number is valid, and just generate the 0 function if it is not.

Program BITOP (141 bytes)

; Perform a bit operation on two operands. The first operand must be ; placed into A; the second operand must be placed into B; and the ; bitwise function code must be placed into C. The function code ; is computed from the bitwise truth table as follows: ; ; A B c ; 0 0 1 ; 0 1 2 ; 1 0 4 ; 1 1 8 ; ; The function code is the sum of the c values corresponding to 1 ; results in the output bit. ; ; The values in A and B are truncated to integers and then taken ; modulo 2^32. The value returned in C is the bitwise value of the ; appropriate operation upon A and B, interpreted as a signed 32 ; bit twos-complement value. ; ; A valid function code is an integer between 0 and 15, inclusive. ; Invalid function codes are regarded as equivalent to function 0, ; False. ; ; Variables: ; A on entry is the first operand; on exit is the result ; B on entry is the second operand; is destroyed ; C is entry is the function code; is destroyed ; D is destroyed ; E is destroyed ; F is destroyed ; ; Symbols: ; -> is assignment arrow ; <> is not equal relational ; => is conditional operator ; < is less than relational ; > is greater than relational ; / is division operator B->F ; Save argument 2 to F Prog "BITCANIN" ; Normalize argument 1 A->E ; Save argument 1 to E F->A ; Retrieve argument 2 Prog "BITCANIN" ; Normalize argument 2, get 2^32 in B A->F ; Save argument 2 to F C<>Int C=>0->C ; If C is an invalid value, C<0=>0->C ; replace C with the C>15=>0->C ; false/0 operation 0->A ; Zero result Do ; Loop through bits B/2->B ; Get next lower power of 2 C->D ; Copy operation number Frac (Int (E/B)/2)=>D/4->D ; If bit set in argument 1, right shift operation ; number by 2 bits Frac (Int (F/B)/2)=>D/2->D ; If bit set in argument 2, right shift operation ; number by 1 bit Frac (Int D/2)=>A+B->A ; If result bit is 1, set the bit in result LpWhile B>1 ; [End of loop through bits] Prog "BITCANOU" ; Normalize result, return in Ans as well

Note how this program does not actually compute the various values needed modulo 2; instead, it divides the value by 2, and notes whether the resulting value has a fractional component. If so, the value modulo 2 is 1; otherwise, the value modulo 2 is 0. Note also how operator precedence is used: Int occurs before division, so the expression Frac (Int D/2) is equivalent to Frac (Int (D)/2).

Finally, we can write our shift program.

Program BITSHF (122 byte):

; Performs a bitwise shift on a value. The value to be shifted is put ; into variable A; the shift quantity is put into variable B. The ; shift quantity is positive for a right shift, negative for a left ; shift. ; ; Variables: ; A on entry is the value to be shifted; on exit is the shifted value ; B on entry is the shift quantity; is destroyed ; C is destroyed ; ; The value in A is truncated to an integer and then taken modulo ; 2^32. The value returned is this value, shifted, and interpreted ; as a signed 32 bit twos-complement value. ; ; The value in B is truncated to an integer. ; ; Symbols: ; -> is assignment arrow ; > is greater than relational ; / is division operator ; < is less than relational ; >= is greater than or equal to relational ; => is conditional arrow Int B->C ; Discard fractional part of shift quantity If Abs C>32 ; If shifting more than 32 bits, Then 0->A ; then the result will be 0 0->C ; and we should not do anything else Else Prog "BITCANIN" ; If not shifting more than 32 bits, make input ; value canonical, get 2^32 into B IfEnd ; [End of test on shift magnitude] While C>0 ; While a right shift is called for Int (A/2)->A ; Right shift by one bit C-1->C ; Decrement shift quantity WhileEnd ; [End of right shift loop] While C<0 ; While a left shift is called for 2A->A ; Left shift by one bit A>=B=>A-B->A ; Reduce modulo 2^32 C+1->C ; Decrement shift quantity WhileEnd ; [End of left shift loop] Prog "BITCANOU" ; Make result canonical and put into Ans

[ 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

Code

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card