Tips And Tricks: Binary Manipulation
Author: Jack Hoxley
Written: 4th May 2001
Contact: [EMail]

Contents of This lesson:
1. Introduction
2. Bit fields
3. Flag combining

1. Introduction

This tutorial isn't greatly important in the grand scheme of things, but I wanted to cover a couple of useful topics that may well help you out at some point. In general VB shields us from the low level binary manipulation (binary is the 010100111010001 stuff!), but there are times that we may want access to them, for example, when directly accessing memory in DirectX we are often required to directly manipulate the raw data - where 3 values are stored in 1 (and we need to get them out)...

2. Bit Fields

You should be familiar with the 'Boolean' datatype - often fundamental to the operation of many programs, particularly games. Well, there's one slight problem with them - they're a bit slow, and they take up a lot of space. Each 'Boolean' datatype is a 16 bit (2 byte) signed number - normally, using an integer of the same size you have 65536 possible values, a Boolean of the same space will only store true/false. Partly because of this, conversion must take place - you assign 1645 to a Boolean value and it'll come back as -1 (true), so there must be something in there that's converting them... which will also slow things down.

Bit fields are a clever way of reducing the size that these Booleans take up. One possible (and often used) method of collision detection is to store a true/false value for every tile/pixel/area in a game world - 100x100 grid = 10000 values, if stored as a Boolean you're already using up 20,000 bytes of memory (19.5kb), whereas, if you were clever, you could fit those 10,000 values into only 1250 bytes (1.2kb) - which is considerably smaller than the original - expand the maths a little further, take a 640x480 image, each pixel has a passable true/false collision flag - that's 307,200 values - stored as booleans it'll be 600kb, stored in my clever little method it'll cost you 37.5kb...

So what is my clever little method then? well, we're going to be storing each boolean flag as a single bit (binary digit), a binary digit is 1 or 0 (on or off), effectively the same as a boolean - true or false, on or off. So it makes sense to use the smallest possible unit. You may now be thinking that there isn't a bit datatype (or anything similiar), thats because there isn't.

We're going to use the "Byte" datatype, it is the smallest possible value, and is unsigned (which means it's never a negative number); as it's a byte it's made up of 8 bits, therefore we can store 8 on/of or true/false values in each byte - if we then make an array of these bytes we can store many thousands very easily - the smaller values that I demonstrated above were taken by dividing the total number of values by 8, 8 of them go into a byte, so the final number is the total number of bytes...

The following piece of code is all that is required to make a simple bit field, calling SetBool( ) will change the current value at that point, and GetBool( ) will return the current value at that point - all you really need.

Private BitField(0 To 99) As Byte '100 bytes = 800 boolean values


Private Function GetBool(N As Long) As Boolean
    If (BitField(N \ 8) And 2 ^ (N - ((N \ 8) * 8))) = 2 ^ (N - ((N \ 8) * 8)) Then GetBool = True
End Function

Private Sub SetBool(N As Long, Val As Boolean)
    If Val = True Then
        BitField(N \ 8) = BitField(N \ 8) Or 2 ^ (N - ((N \ 8) * 8))
    Else
        BitField(N \ 8) = BitField(N \ 8) Xor 2 ^ (N - ((N \ 8) * 8))
    End If
End Sub

AND:

OR:

XOR:

We could now do a quick sum using these, which is the basis of our code. Notice that when we are using GetBool it uses the logical AND operator, well this basically says that, if the source and the destination have the same bits, then the output will have the same as the destination. Or, for a better example:

01111011
00100000
-------- AND
00100000

What a surprise, the result is the same as the second input! so, in VB code we could say:
If (X And Y) = Y then The_Bit_Is_True
which, if you look up to the top of the code again, is exactly what I've done. All the brackets and maths symbols are just so that we can find which byte to read from, and which bit within that byte we are checking.

The Same goes for the Or'ing and the XOR'ing.... The OR is used to set a bit, which, by looking at the truth table above should be fairly obvious. XOR'ing is used to turn a bit off, which you can see from the truth table...

One final thing to do, should you want to use this method for a 2D array you're going to need a way of converting an X,Y coordinate into a single N value. This can be quite easily done using X+(Y*Width), where the array would be a 100x100 array (of 0-99 scale) the formula works out as 99+(99*100) = 9999, the last element in a (100x100)-1 sized array... Just remember to make sure that the bit field array is large enough...

3. Flag Combining

Even if your new to the DirectX world you'll very quickly see that it uses a lot of functions where you can specify lots of options in one parameter, for example, in Direct3D8, to create a Flexible Vertex Format you use notation like:

Take the following example for a generic graphics engine initialisation:

InitGraphics GROPT_STARTFULLSCREEN Or _
                  GROPT_USEHIDETAILMODELS Or _
                  GROPT_USEHIGHTDETAILTEXTURES Or _
                  GROPT_USESPECIALEFFECTS

To implement the second type of function calling, we need this code:

Private Enum Options
    GROPT_STARTFULLSCREEN = 2 ^ 0
    GROPT_STARTWINDOWED = 2 ^ 1
    
    GROPT_USEHWTNL = 2 ^ 2
    GROPT_USEPUREDEV = 2 ^ 3
    
    GROPT_USELOWDETAILMODELS = 2 ^ 4
    GROPT_USEMEDDETAILMODELS = 2 ^ 5
    GROPT_USEHIDETAILMODELS = 2 ^ 6
    
    GROPT_USELOWDETAILTEXTURES = 2 ^ 7
    GROPT_USEHIGHTDETAILTEXTURES = 2 ^ 8
    
    GROPT_USESPECIALEFFECTS = 2 ^ 9
    GROPT_USEDYNAMICLIGHTS = 2 ^ 10
End Enum
    
Private Function InitGraphics(ParamList As Options) As Boolean
    If ParamList And GROPT_STARTFULLSCREEN = GROPT_STARTFULLSCREEN Then
        'initialise fullscreen mode
    ElseIf ParamList And GROPT_STARTWINDOWED = GROPT_STARTWINDOWED Then
        'initialise in windowed mode
    End If
End Function

Look back at the previous section about bit fields, remember that X or Y is used to set a bit and (X and Y)=Y is used to test a bit for on/off status; these are used again here.

Hopefully you've learned something useful here, nothing particularly ground breaking - but it's the sort of thing that can be the perfect solution to that little problem that you've been working on recently...