There are some low-level sets built in that allow bit-by-bit manipulation of memory storage. Of course, to make any use of these, something must be known about the bit and byte level numeric representations on the underlying machine.

A number represented in binary form could be thought of as a set of bit positions enumerated from least significant (lowest number) to most significant (highest number) as shown in figure 9.3 for an eight bit number..

In this case, if the number is thought of as a SET OF [0 .. 7] the elements 6, 5, 3, and 2 are in the set, and the elements 7, 4, 1, and 0 are not in the set. This idea of interpreting storage as a set of bit positions is encapsulated in the following ADT:

The Modula-2 typeBITSEThas the implicit definition

TYPE

BITSET = SET OF [0 .. BitsPerBitset-1]

where the constant BitsPerBitset is implementation defined and the setting of each bit position determines whether the number of that position is an element of the set.

The constant *BitsPerBitset* is usually the same as the number of bits in a WORD, (or some integral multiple of this); often it is 16 or 32 and can be computed as:

BitsPerBitset :=SIZE(BITSET) * SYSTEM.BITSPERLOC

If, for instance, as is often the case, the types CARDINAL, WORD, and BITSET all have the same size (in LOCs) the following program provides an alternative to the pair of mutually recursive procedures in Chapter 4 to print out a CARDINAL in binary form. It forcibly reinterprets a CARDINAL as a BITSET, and then prints out a one or a zero depending on whether that bit is represented in the set or not.

MODULEBitsetDemo; (* Written by R.J. Sutcliffe *) (* to demonstrate the use of bitset *) (* using ISO standard Modula-2 *) (* last revision 1994 03 01 *)FROMSTextIOIMPORTWriteString, WriteLn, SkipLine, ReadChar, WriteChar;FROMSWholeIOIMPORTWriteCard, ReadCard;FROMSYSTEMIMPORTCAST, WORD, BITSPERLOC;CONSTmaxBitNum = BITSPERLOC *SIZE(BITSET) - 1;PROCEDUREWriteWordBin (b: WORD); (* Pre : WORD and BITSET have the same size *)VARbs :BITSET; count :CARDINAL;BEGINbs := CAST (BITSET, b);FORcount := maxBitNumTO0BY-1DOIFcountINbsTHENWriteCard (1,1)ELSEWriteCard (0,1)END;IFcountMOD8 = 0 (* break into groups of 8 bits *)THENWriteChar (" ");END;END;ENDWriteWordBin;VARtheNumber :CARDINAL; answer :CHAR; again :BOOLEAN;BEGINWriteString ("This program tests a procedure to print "); WriteString ("cardinals in binary form"); WriteLn;REPEATWriteString ("Enter the number to be changed "); WriteString ("to binary form ==> "); ReadCard (theNumber); SkipLine; WriteLn; WriteString ("The cardinal "); WriteCard (theNumber, 0); WriteString (" converted to binary form is: "); WriteLn; WriteWordBin (theNumber); (* one must know sizes are equal *) WriteLn; WriteString ("Do another? Y/N "); ReadChar (answer); SkipLine; again := (CAP(answer) = "Y");UNTILNOTagain;ENDBitsetDemo.

Observe that even the bit positioning from left (most significant) to right (least significant) is implementation defined; it is not necessarily the case in in the underlying hardware of all implementations. However, the numbering from *zero* (least signficant) to *bitsperbitset* (most significant) is defined to be the way that ISO standard Modula-2 must produce the results to the program, regardless of the hardware. Here is a sample run from this program module:

This program tests a procedure to print cardinals in binary form Enter the number to be changed to binary form ==>1The cardinal 1 converted to binary form is: 00000000 00000000 00000000 00000001 Do another? Y/NyEnter the number to be changed to binary form ==>10The cardinal 10 converted to binary form is: 00000000 00000000 00000000 00001010 Do another? Y/NyEnter the number to be changed to binary form ==>65535The cardinal 65535 converted to binary form is: 00000000 00000000 11111111 11111111 Do another? Y/NyEnter the number to be changed to binary form ==>1000000The cardinal 1000000 converted to binary form is: 00000000 00001111 01000010 01000000 Do another? Y/Nn

For the purpose of working with other types at the bit level, and provided their representation details are known, it is also possible to declare a more general kind of bitset, this time with a user-specified number of bits, rather than the fixed number allowed by the type BITSET. In addition, the underlying type in the more general case need not be CARDINAL [0..n], but may be any ordinal type (though CARDINAL is the most useful). Of course, if these sets are to be mapped to storage locations, the number of bit positions is most useful as a multiple of BITSPERLOC. Thus, in the above example, one could have declared:

TYPECardSet =PACKEDSETOF[0..SIZE(CARDINAL) * BITSPERLOC - 1]

and then cast to an item of this type. Indeed, the type BITSET is just a specific built in subtype of the more general type PACKEDSET. By this means, the binary representation of other types, such as REALs could also be investigated.

In addition, there are some operations in SYSTEM that are intended to manipulate PACKEDSETS (including BITSETS) on the bit level. These include:

PROCEDURESHIFT (val: <packset type>; numToShift :INTEGER) : <same packset type>

which shifts all the bits of the pattern *numToShift* positions to the left or the right, (The bit on one end is shifted to oblivion and a zero comes in at the other end.) and

PROCEDUREROTATE (val: <packset type>; numToRotate :INTEGER): <same packset type>

which rotates all the bits of the pattern *numToRotate* positions to the left or the right, (The bit on one end is shifted to the other end.) The effects of the two are shown in figure 9.4

This capability is most useful when programming at the low system level where individual bits must be manipulated. Note that the effect of a right shift is to divide by 2. This is illustrated in the example below. Note that it does not make use of any special knowledge about the sizes of the types in bits, but computes them from information available from SYSTEM.

MODULEShiftDemo; (* Written by R.J. Sutcliffe *) (* to demonstrate the use of packedset *) (* using ISO standard Modula-2 *) (* last revision 1994 03 02 *)FROMSTextIOIMPORTWriteString, WriteLn, SkipLine, ReadChar, WriteChar;FROMSWholeIOIMPORTWriteCard, ReadCard;FROMSYSTEMIMPORTBITSPERLOC, SHIFT, ROTATE, CAST;CONSTmaxBitNum = BITSPERLOC *SIZE(CARDINAL) - 1;TYPECardSet =PACKEDSETOF[0..maxBitNum];PROCEDUREWriteCardBin (num:CARDINAL);VARcount :CARDINAL; numSet : CardSet;BEGINnumSet := CAST (CardSet, num);FORcount := maxBitNumTO0BY-1DOIFcountINnumSetTHENWriteCard (1,1)ELSEWriteCard (0,1)END;IFcountMOD8 = 0 (* break into groups of 8 bits *)THENWriteChar (" ");END;END;ENDWriteCardBin;VARnum :CARDINAL; answer :CHAR; again :BOOLEAN;BEGINWriteString ("This program illustrates bit shifting "); WriteLn;REPEATWriteString ("Enter the number to be shifted "); ReadCard (num); SkipLine; WriteLn; WriteString ("The cardinal "); WriteCard (num, 0); WriteString (" binary: "); WriteCardBin (num); WriteLn; WriteString ("Shifted one position right yields "); num := CAST (CARDINAL, SHIFT (CAST (CardSet, num), -1)); WriteCard (num, 0); WriteString (" binary: "); WriteCardBin (num); WriteLn; WriteString ("and, then rotated one position right yields "); num := CAST (CARDINAL, ROTATE (CAST (CardSet, num), -1)); WriteCard (num, 0); WriteString (" binary: "); WriteCardBin (num); WriteLn; WriteString ("Do another? Y/N "); ReadChar (answer); SkipLine; again := (CAP(answer) = "Y");UNTILNOTagain;ENDShiftDemo.

Here is a brief run to illustrate:

This program illustrates bit shifting Enter the number to be shifted1The cardinal 1 binary: 00000000 00000000 00000000 00000001 Shifted one position right yields 0 binary: 00000000 00000000 00000000 00000000 and, then rotated one position right yields 0 binary: 00000000 00000000 00000000 00000000 Do another? Y/NyEnter the number to be shifted5The cardinal 5 binary: 00000000 00000000 00000000 00000101 Shifted one position right yields 2 binary: 00000000 00000000 00000000 00000010 and, then rotated one position right yields 1 binary: 00000000 00000000 00000000 00000001 Do another? Y/NyEnter the number to be shifted65535The cardinal 65535 binary: 00000000 00000000 11111111 11111111 Shifted one position right yields 32767 binary: 00000000 00000000 01111111 11111111 and, then rotated one position right yields 2147500031 binary: 10000000 00000000 00111111 11111111 Do another? Y/Nn

Observe the difference between the rotate and the shift when there is a one in the rightmost position.