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)
Variable name | Binary |
red% | 0000000000001010 |
green% | 0000000000111111 |
blue% | 0000000000001111 |
However, we them to look like this if we're going to add them together:
Variable name | Binary |
red% | 0000000000001010 |
green% | 0000011111100000 |
blue% | 0111100000000000 |
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:
0000000000001010 | |
0000011111100000 |
|
+ | 0111100000000000 |
= | 0111111111101010 |
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 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 see
that
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's 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:
44: | 0000000000001101 |
Mask: | 0000000000001000 |
Result: | 0000000000001000 |
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).
24: | 0000000000011000 |
Mask: | 0000000000010000 |
XORed Result | 0000000000001000 |
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! If there's any other bit manipulations you'd like, and are having trouble coming up with how to do them, go ahead an e-mail me and I'll add it to this tutorial.