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 type BITSET has 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.
MODULE BitsetDemo;
(* Written by R.J. Sutcliffe *)
(* to demonstrate the use of bitset *)
(* using ISO standard Modula-2 *)
(* last revision 1994 03 01 *)
FROM STextIO IMPORT
WriteString, WriteLn, SkipLine, ReadChar, WriteChar;
FROM SWholeIO IMPORT
WriteCard, ReadCard;
FROM SYSTEM IMPORT
CAST, WORD, BITSPERLOC;
CONST
maxBitNum = BITSPERLOC * SIZE(BITSET) - 1;
PROCEDURE WriteWordBin (b: WORD);
(* Pre : WORD and BITSET have the same size *)
VAR
bs : BITSET;
count : CARDINAL;
BEGIN
bs := CAST (BITSET, b);
FOR count := maxBitNum TO 0 BY -1
DO
IF count IN bs
THEN
WriteCard (1,1)
ELSE
WriteCard (0,1)
END;
IF count MOD 8 = 0 (* break into groups of 8 bits *)
THEN
WriteChar (" ");
END;
END;
END WriteWordBin;
VAR
theNumber : CARDINAL;
answer : CHAR;
again : BOOLEAN;
BEGIN
WriteString ("This program tests a procedure to print ");
WriteString ("cardinals in binary form");
WriteLn;
REPEAT
WriteString ("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");
UNTIL NOT again;
END BitsetDemo.
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 ==> 1 The cardinal 1 converted to binary form is: 00000000 00000000 00000000 00000001 Do another? Y/N y Enter the number to be changed to binary form ==> 10 The cardinal 10 converted to binary form is: 00000000 00000000 00000000 00001010 Do another? Y/N y Enter the number to be changed to binary form ==> 65535 The cardinal 65535 converted to binary form is: 00000000 00000000 11111111 11111111 Do another? Y/N y Enter the number to be changed to binary form ==> 1000000 The cardinal 1000000 converted to binary form is: 00000000 00001111 01000010 01000000 Do another? Y/N n
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:
TYPE CardSet = PACKEDSET OF [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:
PROCEDURE SHIFT (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
PROCEDURE ROTATE (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.
MODULE ShiftDemo;
(* Written by R.J. Sutcliffe *)
(* to demonstrate the use of packedset *)
(* using ISO standard Modula-2 *)
(* last revision 1994 03 02 *)
FROM STextIO IMPORT
WriteString, WriteLn, SkipLine, ReadChar, WriteChar;
FROM SWholeIO IMPORT
WriteCard, ReadCard;
FROM SYSTEM IMPORT
BITSPERLOC, SHIFT, ROTATE, CAST;
CONST
maxBitNum = BITSPERLOC * SIZE(CARDINAL) - 1;
TYPE
CardSet = PACKEDSET OF [0..maxBitNum];
PROCEDURE WriteCardBin (num: CARDINAL);
VAR
count : CARDINAL;
numSet : CardSet;
BEGIN
numSet := CAST (CardSet, num);
FOR count := maxBitNum TO 0 BY -1
DO
IF count IN numSet
THEN
WriteCard (1,1)
ELSE
WriteCard (0,1)
END;
IF count MOD 8 = 0 (* break into groups of 8 bits *)
THEN
WriteChar (" ");
END;
END;
END WriteCardBin;
VAR
num : CARDINAL;
answer : CHAR;
again : BOOLEAN;
BEGIN
WriteString ("This program illustrates bit shifting ");
WriteLn;
REPEAT
WriteString ("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");
UNTIL NOT again;
END ShiftDemo.
Here is a brief run to illustrate:
This program illustrates bit shifting Enter the number to be shifted 1 The 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/N y Enter the number to be shifted 5 The 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/N y Enter the number to be shifted 65535 The 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/N n
Observe the difference between the rotate and the shift when there is a one in the rightmost position.