What Is a Bitvector
In normal math a single number only means a single number, right?
No matter what you do 5 = 5 and 10 = 10.
Bitvectors allow a single number to represent multiple other numbers.
Normally if you needed to say something was equal to 1+6+8
You would just say it was worth 15.
But what if you needed to know what numbers went together to make that 15?
15 can be gotten to alot of ways. 7+8, 9+4, 11+2, 1+3+11, almost any
combination, and what if you specifically needed to know 15 = 1+6+8?
That's where bitvectors come in.
Bitvectors are a series of numbers whose sum is able to be converted
back into the original components.
How bitvectors work is off of basic exponential theory.
2^0 = 1 (Any number raised to a power of 0 becomes 1)
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024
*See bottom for full list.
What is important to notice about bitvectors, is they are one decimal
number higher than the sum of ALL exponents before them.
That means if you add the results of 2^0 through 2^9 together, you'll
get 1023, 1 digit off from the next step, 1024.
Why is that important? Because using only powers of 2, you can never
exceed a value higher than the next step.
At a single glance of the number 1023, you know its less than 1024.
So you know all the numbers that make up 1023 are less than 10.
Lets look at our question of 1+6+8
In bitvectors according to our chart that would be: 2+64+256=322
So, we now have the bitvector 322. Let's dissect it again and see
if we can get any value other than what we started with.
We can see clealy 322 is less than 512, so we know 9 isn't a part of
this. 8 on the other hand equals 256, which clearly can be subtracted.
So we mark down an 8 as one of the original components, and look at what's
left. 322-256 = 66
The first thing lower than 66 on our table is 64, so we mark down a 6, and that
leaves us with 2, so we mark down a 1.
That leaves us with 8+6+1, same thing we started with.
And as long as we remove the highest numbers first, there is no way we can find
any other combination of possible answers.
Thus a bitvector is a way of storing a series of unique numbers inside a single
number. As long as you have more than one number, and all the numbers are unique
(none are duplicates, such as more than one of the same number) you can store
the entire series of numbers in a bitvector, where they can easily be extracted
from if needed.
***Extended bitvectors***
An extended bitvector is the same as any other bitvector, but 2 to the power
of any number higher than 31 is too big for some programming languages to handle.
An integer usually stops at around 2 billion to 4 billion, which 2^31 meets or
exceeds, so reaching 2^32 or higher becomes difficult.
An extended bitvector is a series of integers, all linked together in a single
structure. How many of them are in use depend on your MUD, but the average is 4
and can be raised or lowered any time just by changing a single definition and
recompiling cleanly.
What extended bitvectors do, is determine how many times 32 goes into the value
to be converted. For example, if you want to add the numbers 1 and 118 into
a single bitvector, we already know that 1 would be equal to 2^1(=2), but 118
is a little harder because that number is pretty huge.
Integer 1: 00 - 31
Integer 2: 32 - 63
Integer 3: 64 - 95
Integer 4: 86 - 127
So 1 would be set on integer 1, and 118 would be set on the 22nd slot of integer 4
Then when an extended bitvector is being polled, it determines based on the value,
which integer it would be looking in, and converts the value into the local value
of the one its looking for.
So if it were looking for that 118 it would note 118 belonged in the 4th integer,
divide 118 accordinly to find the local value should be 22 (118-96), and check to
see if the value of 22 was in the 4th integer.
********************************************
Powers of 2 up to 2^31
********************************************
[ 0] 1
[ 1] 2
[ 2] 4
[ 3] 8
[ 4] 16
[ 5] 32
[ 6] 64
[ 7] 128
[ 8] 256
[ 9] 512
[10] 1024
[11] 2048
[12] 4096
[13] 8192
[14] 16384
[15] 32768
[16] 65536
[17] 131072
[18] 262144
[19] 524288
[20] 1048576
[21] 2097152
[22] 4194304
[23] 8388608
[24] 16777216
[25] 33554432
[26] 67108864
[27] 134217728
[28] 268435456
[29] 536870912
[30] 1073741824
[31] 2147483648