In his infamous rant Why Pascal Is Not My Favorite Programming Language Brian Kernighan says "There is a paucity of operators ... In particular, there are no bit-manipulation operators (AND, OR, XOR, etc.). I simply gave up trying to write the following trivial encryption program in Pascal:

     i := 1;
     while getc(c) <> ENDFILE do begin
             putc(xor(c, key[i]));
             i := i mod keylen + 1
     end

because I couldn't write a sensible 'xor' function."

The amazing part of this statement is that I cannot fathom why he found it so hard to write an xor function. It's simply not that hard. In this post we take up the challenge.

We will assume that Kernighan's compiler did not have the type Byte and this may one source of his problem. However, Byte is simply a subrange of the integers (0 .. 255) so this is easily surmounted. We can also safely assume that he had access to the Boolean operators NOT, OR and AND.

Our project is to write four functions:

          BitNot (n : Byte) : Byte ;
          BitOr (m,n : Byte) : Byte ;
          BitAnd (m,n : Byte) : Byte ;
          BitXor (m.n : Byte) : Byte ;

Our strategy is to create a type

          Type
              BitWiseType = Array [0 .. 7] of Boolean ;

and then copy (and convert) each bit into variables of type BitWiseType where they can easily be handled by the Boolean operators. The conversion from Byte to BitWiseType is a simple adaptation of the mathematician's standard algorithm for converting from decimal to binary: repeatedly divide the number by two until the quotient is zero, taking the remainder as the next binary digit. To go from BitWiseType to Byte we start with a radix of 1, multiply by the least significant bit, then double the radix, go to the next bit and repeat for all bits.

Of course a XOR b is the same as (a AND (NOT b)) OR ((NOT a) AND b) so the final function BitXor can be defined in terms of the previous ones.

Of course Turbo Pascal has NOT, OR, AND and XOR which can be used as either strictly Boolean operators or as bitwise operators. Which definition is intended is determined by context which Pascal's strong typing facilitates. This program is unusual in that there are a finite number of possible inputs, 65536 to be exact, so we can exhaustively test our work. This test phase is the only part of our program where we will the the Turbo Pacal XOR.

  1 Program BitWise ;
  2 {
  3    implements bitwise functions for compilers that do not have them
  4 }
  5    Type
  6       BitWiseType = Array [0 .. 7] of Boolean ;
  7 
  8    Procedure GetBits (Var m : BitWiseType ; n : Byte) ;
  9    {
 10       copies a byte into an array of Boolean
 11    }
 12    Var
 13       i  :  0 .. 7 ;
 14 
 15    begin
 16       for i := 0 to 7 do begin
 17          m[i] := (n MOD 2 = 1) ;
 18          n    := n DIV 2
 19       end
 20    end ;
 21    
 22    Procedure PutBits (m : BitWiseType ; Var n : Byte) ;
 23    {
 24       copies an array of Boolean into a byte 
 25    }
 26    Var
 27       i     :  0 .. 7 ;
 28       Radix :  Byte ;
 29 
 30    begin
 31       radix := 1 ;
 32       n     := 0 ;
 33       for i := 0 to 7 do begin
 34          n := n + radix*Ord(m[i]) ;
 35          Radix := 2*Radix
 36       end
 37    end ;
 38 
 39    Function BitNot (n : Byte) : Byte ;
 40    {
 41       bitwise not
 42    }
 43    Var
 44       i  :  0 .. 7 ;
 45       a  :  BitWiseType ;
 46 
 47    begin
 48       GetBits(a, n) ;
 49       for i := 0 to 7 do
 50          a[i] := NOT a[i] ;
 51       PutBits(a, n) ;
 52       BitNot := n
 53    end ;
 54 
 55    Function BitOr (m,n : Byte) : Byte ;
 56    {
 57       bitwise or
 58    }
 59    Var
 60       i     :  0 .. 7 ;
 61       a,b,c :  BitWiseType ;
 62 
 63    begin
 64       GetBits(a, m) ;
 65       GetBits(b, n) ;
 66 
 67       for i := 0 to 7 do
 68          c[i] := a[i] OR b[i] ;
 69 
 70       PutBits(c, n) ;
 71 
 72       BitOr := n
 73    end ;
 74    
 75    Function BitAnd (m,n : Byte) : Byte ;
 76    {
 77       bitwise and
 78    }
 79    Var
 80       i     :  0 .. 7 ;
 81       a,b,c :  BitWiseType ;
 82 
 83    begin
 84       GetBits(a, m) ;
 85       GetBits(b, n) ;
 86 
 87       for i := 0 to 7 do
 88          c[i] := a[i] AND b[i] ;
 89 
 90       PutBits(c, n) ;
 91 
 92       BitAnd := n
 93    end ;
 94 
 95    Function BitXor (m,n : Byte) : Byte ;
 96    {
 97       bitwise xor
 98    }
 99    begin
100       BitXor := BitOR (BitAnd(m, BitNot(n)), BitAnd(BitNot(m), n))
101    end ;
102 
103 Var
104    m,n,
105    i,j   :  Byte ;
106 
107 begin
108    for m := 0 to 255 do 
109       for n := 0 to 255 do begin
110          i := BitXor (m,n) ;
111          j := m XOR n ;
112          WriteLn (m:5, n:5, i:10, j:5, i - j:10)
113       end
114 end.