Testing Bits in Signed Integers

It's relatively easy to test bits in positive numbers in MapInfo. Using the integer divide and Mod operators you can test any bit with the following expression:

nValue \ 2^(n-1) mod 2

where nValue is an integer containing the bits you want to check, and n is the bit to test, numbered from the right and starting at one. If this expression equals 1 then the bit is set; if it's 0 (zero), the bit is cleared.

Because MapInfo uses signed integers, the problems start when the high bit is set, which turns the value into a negative number and alters the bit pattern. However, it's not random. To read it, you just have to understand how negative integers are coded.

Negative integers are represented in binary as the two's complement of their positive value. This is done because at the binary level, computers are basically adding machines; they actually don't know how to subtract. Essentially the "subtraction" operation is defined as "add a negative number" rather than to subtract a positive number. The two's complement of a number has the interesting property that it represents a negative number yet it can be added directly to another binary number and yield the correct sum.

To illustrate how two's complement works, let's use a signed 4-bit integer so that we can keep it simple. This number can store values from 7 to -8 and has the following bit patterns:

Decimal  Binary
-8       1000
-7       1001
-6       1010
-5       1011
-4       1100
-3       1101
-2       1110
-1       1111
 0       0000
 1       0001
 2       0010
 3       0011
 4       0100
 5       0101
 6       0110
 7       0111

Hopefully you can see the pattern and note that the negative numbers all have their highest bit set. The two's complement of any positive number results in the bit pattern for its negative, and is determined like so. Subtract each bit in the number from one (one's complement) and then add one to the result (two's complement) throwing away any carry bit that may result. The operation is actually just flip bits and add 1, ignoring any carry bit.

For example, let's determine the two's complement of 5.

  1111   (subtract each bit from 1)
- 0101   (5)
  ----
  1010 + 1 = 1011 (this is value for -5)

When trying to read the bit pattern of a negative number the trick is to somehow strip off the high bit yet maintain the same bit pattern to the right of it, and also not overflow the capacity of the integer storage. To do this we simply add our negative number to the highest possible number allowed in the integer storage and then add one to this result. The operation looks a lot like two's complement, but not quite.

   0111  (highest possible positive number in 4-bit integer)
 + 1011  (-5)
   ----
(1)0010 + 1 = 0011  (ignore the carry bit)

Now since we knew the value was negative, we know that the high bit was set, and now all the other bits to the right of this are the same as they were in the negative value, but now we're dealing with a positive number and we can test bits as usual.

Scaling this up to the real world, let's use a MapInfo integer, which is a 32-bit signed integer capable of storing values from -2,147,483,648 to 2,147,483,647 inclusive. (Note the last value is the highest possible positive value, which can be written in hexadecimal as &H7FFFFFFF.) So using the techniques developed above, the code to test bits including negative integers might look like this:

If nValue < 0 Then
  ' Bit 32 is set
  ' Strip off the high bit so we can work on the other bits
  nBitFlags = &H7FFFFFFF + nValue + 1
Else
  nBitFlags = nValue
End if

For n = 1 To 31
  If nBitFlags \ 2^(n-1) Mod 2 Then
    Print "Bit " & n & " is set"
  Else
    Print "Bit " & n & " is not set"
  End If
Next
If nValue < 0 Then
  Print "Bit 32 is set"
Else
  Print "Bit 32 is not set"
End If