Bitwise math

Generally, performing arithmetic and other math in a programming language like Robotic requires no understanding of how the computer stores and interprets numbers. 1 + 2 = 3, no matter how 1, 2, or 3 are understood by the program. However, when working with computers, there is a class of operations that can be performed on stored values that DOES take into account how they are stored. These generally fit under the heading of bitwise math.

Common uses for bitwise math in Megazeux include: storing multiple values (often on-off binary flags) in a single counter (common in the old days of MZX, before counters became plentiful); interacting with and editing characters (which can be understood as a graphical representation of on and off bits); and writing and reading counters to and from files, since counters are 32-bit while counter reading and writing supported only 8- and 16-bit operations until recently.

Boolean Algebra

Before exploring all of the details of bitwise math, we need an understanding of the basic types of operations that can be performed. Pure boolean algebra operates on single, binary values of TRUE and FALSE, which are called booleans (hence, boolean algebra). It defines several operations that can be performed on booleans:

• NOT A Often written as !A or ~A, this returns the opposite of the value of A. If A is true, !A is FALSE, and vice versa.
• A AND B Often written A&B or simply AB, this operation returns TRUE if and only if both A AND B are TRUE.
• A OR B Often written A|B or A+B, this operation returns TRUE if and only if either A OR B (or both) is TRUE.
• A XOR B Often written A^B, this operations returns TRUE if and only if either A OR B, but NOT both, is TRUE. XOR is an abbreviation for "Exclusive OR", meaning "only one of these is true". OR can be understood as "Inclusive OR", meaning "any or all of these are true".
• A NAND B, A NOR B, A XNOR B These are equivalent to NOT (A AND B), NOT (A OR B), and NOT (A XOR B), respectively.

MZX supports NOT, AND, OR and XOR through the use of expressions, but as bitwise operations, not boolean ones. They operate on full, 32-bit integer values, not 1-bit boolean values.

Binary Representation

To understand how bitwise math operates on integers, one must understand how integers are interpreted as a string of bits. Apart from some special handling for negative numbers, this is simply the binary (base-2) representation of the number. Most people understand numbers in decimal representation, where there are ten digits, 0-9. Each digit in the number represents a successive power of 10, and is named according to its position counting from right to left: the one's place, the ten's place, the hundred's place, and so on.

Binary representation has only two digits, 0 and 1, which are analogous to bits in computer terms. Thus, a number in binary representation interprets these digits as successive powers of two, according to their position. From right to left, these could be called the one's place, the two's place, the four's place, the eight's place, and so on. Use the following algorithm to convert a number from decimal to binary representation.

let t be a string of 32 digit 0's, counting them as 0 to 31 from right to left
let n be a positive number we wish to convert
while n is greater than zero:
  let p be the largest power of two less than or equal to n
  set the p-th digit of t to 1
  subtract p from n
t is now the binary representation of the original n

To convert from binary to decimal representation:

let t be zero
let n be a binary number with no more than 31 digits
let p be zero
while p is less than the length of n
  if the p-th digit of n is 1, add 2^p to t
  increase p by 1
t is now the decimal representation of n

For reference, the important powers of two are:

20	= 1	28	= 256	216	= 65536	224	= 16777216
21	= 2	29	= 512	217	= 131072	225	= 33554432
22	= 4	210	= 1024	218	= 262144	226	= 67108864
23	= 8	211	= 2048	219	= 524288	227	= 134217728
24	= 16	212	= 4096	220	= 1048576	228	= 268435456
25	= 32	213	= 8192	221	= 2097152	229	= 536870912
26	= 64	214	= 16384	222	= 4194304	230	= 1073741824
27	= 128	215	= 32768	223	= 8388608	231	= 2147483648

As for negative numbers, they are stored in a form called two's complement. This works by having the highest (left-most) bit indicate the sign of the number (0 for positive, 1 for negative), and then inverting (i.e. NOT) all of the bits in a negative number and ADDING one to it to obtain the analogous positive number (or vice-versa). So, to find the binary representation for a negative decimal, first find the representation of the equivalent positive number, change all 1's to 0's and 0's to 1's, and add 1 (cascading as necessary). This always leaves the one's digit the same, while typically changing most or all of the digits two and above, hence the name "two's complement"

Examples

This will be hard to understand without some practice examples, so here are some exercises you can try.

1. Write 491520 as a binary number
   1. Start with 00000000000000000000000000000000
   2. 2¹⁹ > 491520 > 2¹⁸, so we subtract 262144 from 491520 and set bit 18

      491520 - 262144 = 229376 ; 00000000000001000000000000000000

   3. Continuing on in the same manner:

      229376 - 131072 = 98304 ; 00000000000001100000000000000000

      98304 - 65536 = 32768 ; 00000000000001110000000000000000

      32768 - 32768 = 0 ; 00000000000001111000000000000000

2. Write -159 as a binary number
   1. We first convert the number 159. Start with ....00000000
   2. 256 > 159 > 128, so subtract 128 from 159 and set bit 7

      159 - 128 = 31 ; ...00010000000

   3. Continuing on in the same manner:

      31 - 16 = 15 ; ...00010010000

      15 - 8 = 7; ...00010011000

      7 - 4 = 3; ...00010011100

      3 - 2 = 1; ...00010011110

      1 - 1 = 0; ...00010011111

   4. Now flip all bits and add 1:

      11111111111111111111111101100001

3. Convert 01011011 to a decimal number
   1. Start with 0.
   2. The one's place is 1, so add 1.
   3. The two's place is 1, so add 2. The running total is now 3.
   4. The eight's place is 1, so add 8. Total is 11.
   5. The sixteen's place is 1, so add 16. Total is 27.
   6. The sixty-four's place is 1, so add 64. Final total is 91.
4. Convert ...1111011011 to a decimal number
   1. The number is negative, so first flip all bits and add 1: ...0000100101
   2. The one's place is 1, so add 1.
   3. The four's place is 1, so add 4. Total is 5.
   4. The thirty-two's place is 1, so add 32. Total is 37.
   5. Add a negative sign to the number. The result is -37.

Bitwise operators

Now, having explained both boolean algebra and the binary representation, we can explain how bitwise operators work. Put simply, a bitwise operation takes the binary representations of two numbers, and performs the given boolean operation on each pair of bits, interpreting 1 as TRUE and 0 as FALSE. The results of each of these 32 operations are composited into a single number. In addition to the AND, OR, XOR and NOT operators, MZX expressions also implement bitshift operators. These operators are not boolean; instead, they take all the bits in a numbers binary representation and shift them left or right a given number of places. This implies that some bits are lost off of one end of the number, while an equal number are added to the other end. There are many different behaviors for this sort of operation, particularly when implemented by assembly languages, but MZX and most other languages fill the incoming bits as 0's, and throw away the outgoing bits.

Application: Interpreting a Counter as 32 Binary Flags

MZXers have been storing flags in counters for a long time. The earliest methods for doing this were very cumbersome, and even with the INT2BIN counters added in MZXAk, this was still not a convenient procedure until the addition of expressions and bitwise math.