BIT manipulation

Bit manipulation, as you may have guessed, involves manipulating bits - more specifically, changing things on a binary level. Therefore, as a prerequisite you should already be familiar with binary, and different sizes of data (bit, nibble, byte, word, etc).

Firstly, why would this be important? Specifically, I'll be talking about BASIC, but you can apply this information to any language.

In a language such as assembly, bit manipulation is easy - direct access to any bit is built in. For example, you can assign a register to a binary value, like so:

mov ah, 10101010b

not so in BASIC and some other high level languages: the smallest amount of data you can assign is a word (in qbasic/quickbasic the smallest data type is the INT - 16 bits. for other dialects of BASIC this may not be the case):

variable% = 170

You do not have the luxury of assigning a binary number, as with ASM. This can pose a problem in some places where you HAVE TO change certain bits. For example, sometimes it's necessary when dealing with graphics. If you're using 16-bit color, it's usually in a 5-6-5 format: 5 bits red, 6 bits green, 5 bits blue. How do you set a 5-bit or 6-bit value? Well, since they're all going into a word (16-bit number) in the end, don't think of them as 5 or 6 bit numbers, think of them as part of the 16-bit number. Let's make a 16-bit color by putting together each component color

Starting from the lowest bit is blue which occupies 5 bits. The highest possible number we can store in 5 bits is 31, or 11111b. The same is true, then for red. Green, since it has 1 more bit, can have one more power of 2 to deal with: 6-bits can hold the number 63, or 111111b. Therefore, if we were to pick component values, we would be limited to those ranges. Let's choose some random component values

Some BASIC code:

red% = 10
green% = 31
blue% = 15

Now, how can those be combined into one WORD (an int%). As you should know, a binary shift left is the same as a multiplication by 2. (as I said, such knowledge is a prerequisite for this page). Well, BASIC doesn't have a Shift function. However, it DOES have multiplication, so we could make a shift function.

FUNCTION Shift% (var%, numshifts%)
mulval% = 2 ^ numshifts%
var% = var% * mulval%
Shift% = var%
END FUNCTION

There we have a shift function. It simply takes a number and multiplies it by 2 however many times numshifts% says too. Ex: if numshifts% is 1, var% is multiplied by 2 ( 2 = 2 * 1 = 2^1 ). If numshifts% is 4, var% is multiplied by 16 ( 16 = 2*2*2*2 = 2^4 ). If numshifts% is 7, var% is multiplied by 128 ( 128 = 2*2*2*2*2*2*2 = 2^7)... and so on..

By shifting the bits we can align them so we can then put them into one variable.

Right now, here's what each variable looks like in binary (remember, each is 16 bit)

However, we them to look like this if we're going to add them together:

Thefore we can see that we want to leave red% alone, shift green over 5 places, and blue over 11 places.
We could multiply green% by 32 (32 = 2*2*2*2*2 = 2^5), or just use our shift function, which does the same thing
The same goes for blue. To shift using the shift function, simply:

green% = Shift%(green%, 5)
blue% = Shift%(blue%, 11)

then, just add them together:

col16bit% = red% + green% + blue%

if you want to visually see the math:

So there you have it - you can now do Shifts in QB. However, what if you wanted to mask off some bits, or toggle bits?
Luckily, QB has boolean operators for this (if you're not familiar with boolean operators read this)

First, let's write a Function to mask off all bit positions except one, in effect, returning the value of a single bit.
Although we have some assistance from BASIC, we still have to use multiplication to get the bit we want. Suppose we have some number - let's use 44.

44 is 101100b

If we call the rightmost, or lowest, bit bit #0, then we can seethat

bit 0 is 0
bit 1 is 0
bit 2 is 1
bit 3 is 1
bit 4 is 0
bit 5 is 1

Suppose we wanted to get bit 3. If it was a 0, we'd want our function to return 0, and if it's a 1, it should return one.
Getting the bit is easy enough, because of the AND operator. The AND operator is perfect for masking off bits, because esentially all you have to do is set-up a mask in a variable - set the bits you don't want to 0, and the ones you do want to 1. In this case, our mask would look like (remember, there are extra leading zeros because we're dealing with 16 bit variales):

mask% = 0000000000001000

if we were to AND this with a value or variable, the only possible bit to come out as 1 would be bit 3, because

[anything] AND 0 = 0.

However, it doesn't have to come out 1 just because bit 3 is one. it will only come out 1 if bit 3 of the mask and bit 3 of the variable or value in question are both 1.

This is because

1 AND 1 = 1

anything else equals 0

So, use AND to compare the mask to 44:

now, just shift that to the right 3 times and you have the resulting bit: 1.

Of course, a shift to the right is just the opposite of a shift to the left. If a left shift is multiplication by a power of 2, a right shift (or the reverse) must be division by a power of two. Hopefully this is obvious how to do so I wont go over it.

We saw how to create a mask by hand, but, how do you write a function to return any bit?

Simply enough, you can create a mask by taking the number 1 and shifting it left a given number of times. If you want to return bit 0, for example, shift it left 0 times. If you want to return bit 2, shift it left 2 times.... and so on. Once you mask off all but the wanted bit, you must shift it back to the right however many times you shifted left.

Some code:

' this code uses the shift% function from earlier
' remeber, we're considering the rightmost bit to be bit 0
FUNCTION Getbit% (var%, bitnum%)
mask% = Shift%(1, bitnum%)
Getbit% = (var% AND mask%) / 2^bitnum%
END FUNCTION

The second line of the function masks, shifts back to the right, and returns the value all in one step.

That covers two topics: Shifts and masking. Now, toggling a bit.

This is very similar to the past two. Toggling a bit means changing it to the opposite: 1 goes to 0, 0 goes to 1. And again, there is an operator that does this: XOR.

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0

Two things we can see from that table. Anything, XORing with 0 doesn't changing anything. and 1 XORed with itself switches to 0. This is perfect because we could XOR a bit with 1 forever and with would always flip back and forth from 0 to 1

0 XOR 1 = 1
1 XOR 1 = 0
0 XOR 1 = 1
and so on...

As before, we'll be toggling one bit, so we'll need to move the bit into position - which can be accomplished with the shift function. We can create a mask like before: Anything we want to toggle should be 1, anything to be left alone should be 0.
Let's illustrate this with the number 24, which is 11000b. Let's toggle bit 4 (the leftmost bit).

And once again, some code:

' remember, as always, the rightmost bit is considered bit 0
FUNCTION Toggle% (val%, bitnum%)
togglemask% = Shift%(1, bitnum%)
returnval% = val% XOR togglemask%
END FUNCTION

That's it!