So now that you think you're an expert with manipulating bits, lets put them to good use. The first use I will be going through will be flags. Again, most of the tutorial will be through comments in the code.
Flags
SCAR Code:
program BitwiseFlags;
var
intFlag : Integer;
byteFlag : Byte;
// You don't need to know anything about this function. It simply converts a
// decimal number to binary format for use in this tutorial.
function IntToBin(value : Integer) : string;
begin
repeat
if((value mod 2) = 0) then
result := '0' + result
else
result := '1' + result;
value := value / 2;
until(value = 0);
end;
begin
ClearDebug;
// Okay, so what are flags? They are pretty much booleans.
// You're probably wondering, "Well, if they are pretty much booleans,
// then why don't we just use booleans?"
// You can, of course, keep using booleans. But lets say you have 20 booleans
// in your script - it probably makes your script look bloated and ugly. This is
// a good time to implement bit flags. They're simple to implement.
// We have two variables, intFlag and byteFlag. intFlag is an integer, therefore
// it has 32-bits. That means you can fit 32 booleans inside it. byteFlag is
// a byte so it can hold 8-bits. I actually won't be using intFlag at all in this
// example, I put it here to explain how many bits it has. I will be using byteFlag.
byteFlag := 0; // 00000000; all bits are unset
Writeln('byteFlag = 00000000');
// Currently, all bits are unset. To set a bit (set it to true), we use one
// of the bit operators: OR). If you remember from my explanation, OR will compare
// two integers and if one or both bits equal '1', the resulting bit will equal '1'.
// Lets dive in and set our first bit! We are going to set the bit to the farthest
// left. The number we will have to OR byteFlag with is 128. How did I get 128?
// Goto the place to the farthest right, that place is equivilant to '1' when its set.
// If you move over one position, that number is timed by two (remember what I said
// about SHL and SHR multiplying and dividing the number!). Then the next position
// to the left would be 4, and so on. Eventually when you get to the last position
// (farthest to the left), it will be equal to 128.
byteFlag := byteFlag or 128;
// Here you can see the bit is set.
Writeln('byteFlag = ' + IntToBin(byteFlag));
// Lets set another bit. This time we will set the fourth bit from the right.
// This position is equivilant to the number '8'.
byteFlag := byteFlag or 8;
// Here you can see, the bit is in fact, set.
Writeln('byteFlag == ' + IntToBin(byteFlag));
// Okay, so we learned to set a bit (set it to true). But how do we unset it (set it to false)?
// Well, there are two different ways to do it. One easy way, and one complicated way.
// The easy way is well, easy - but the down fall is that if the bit is already unset,
// it will set it - which is the exact opposite of what we want to do.
// But if you're already sure the bit is set to true, then it will work fine.
byteFlag := byteFlag xor 8;
Writeln('byteFlag == ' + IntToBin(byteFlag));
// Here I will show you what happens when you try to unset it after its already
// unset with XOR.
byteFlag := byteFlag xor 8;
Writeln('byteFlag == ' + IntToBin(byteFlag));
// As you can see, the bit is set again.
// Now, the complicated way to unset a bit, is well, complicated to beginners.
// But it will only unset it and not set it.
// Here is the code that will unset it:
byteFlag := byteFlag and (not(1 shl 3));
Writeln('byteFlag = ' + IntToBin(byteFlag));
// Ta-da! Its unset. And to prove to you that it won't set itself again
// if we try to unset it while its already unset, I'll do it again.
// Before I move on: the number '3' in this is the bit position going from
// right to left (bits 0-7).
byteFlag := byteFlag and (not(1 shl 3));
Writeln('byteFlag = ' + IntToBin(byteFlag));
// So as you can see, that is the correct way to unset bits. Now, let me explain
// how it works. Its basically saying to AND the unset bit of (1 shl 3) which is
// the fourth bit from the right. I told you it was confusing, but you will
// understand it in time. For now, you just need to remember how to unset it.
// Okay, so you now know how to unset and set individual bits (hopefully).
// So how do you use these in conditional statements such as if()then ?
// Its simple. The bits at this point look like so: 10000000
// So lets check if the bit farthest to the left is set or not.
if((byteFlag and 128) = 128) then
Writeln('Farthest bit to the left is set!')
else if((byteFlag and 128) = 0) then
Writeln('Farthest bit to the right is unset!');
// Of course, this program will read out "Farthest bit to the left is set!"
// But how does it work? This statement is AND'ing 128 from byteFlag,
// which will result in 128 (10000000) being returned since its set! (If you don't
// remember what the AND operator does, now would be a good time to look back!)
// So this is pretty much the equivilant of:
// if(128 = 128) then
// Writeln('Farthest bit to the left is set!')
// else if(128 = 0) then
// Writeln('Farthest bit to the right is unset!');
// That's pretty much all for bit flags! There are many uses for it,
// just try not to go overboard with them.
end.
Okay, so now that you have learned how to use bits as booleans, I'm going to teach you how to pack smaller set of bits inside larger set of bits - specifcally, 8 bit bytes into 32 bit integers.
Byte Packing:
SCAR Code:
program BitwisePacking;
var
packedBytes, colorInt, R, G, B : Integer;
byte1, byte2, byte3, byte4 : Byte;
// You don't need to know anything about this function. It simply converts a
// decimal number to binary format for use in this tutorial.
function IntToBin(value : Integer) : string;
begin
repeat
if((value mod 2) = 0) then
result := '0' + result
else
result := '1' + result;
value := value / 2;
until(value = 0);
end;
begin
ClearDebug;
// This example may or may not be useful in everyday scripting at SRL.
// What is bit packing (or byte packing specifically)? Byte packing is taking
// multiple 8 bit bytes and putting them inside one integer. Ever wonder how
// 16777215 equals the color white in Simba? Well, in this tutorial I'll show
// you why. This is also very good for network programming when you have multiple
// bytes you need to send over the network. Sending one integer is better
// then sending multiple bytes of data.
// Lets get started. To start off with: a byte has 8 bits in it, while the average
// integer has 32 bits. That means you can put 4 bytes into 1 integer. You can't
// pack anymore into it obviously, because there isn't any room.
// We are going to be using pretty much all the operators with the exception of XOR.
// Here, we have 4 bytes of data: byte1, byte2, byte3 and byte4.
byte1 := 233; // 11101001
byte2 := 56; // 111000
byte3 := 1; // 1
byte4 := 255; // 11111111
// And here we have an integer, initialized to zero.
packedBytes := 0;
// So how the hell do we get all that data into one integer?
// Lets think of the data like this:
// We are basically going to be seperating packedBytes up into 4 8-bit sections.
// packedBytes - |00000000|00000000|00000000|00000000|
// byte1 byte2 byte3 byte4
// Lets get started with packing byte1
packedBytes := packedBytes or byte1;
Writeln('packedBytes = ' + IntToBin(packedBytes));
// First, we simply OR the byte into the integer.
// The data will now look like this:
// packedBytes |00000000|00000000|00000000|11101001|
// byte1 byte2 byte3 byte4
// Okay so lets pack some more bytes into the integer.
// Before we do this, we have to make more room at the end
// of the integer. So we shift byte1 over 8 bits to make room
// for byte2.
packedBytes := packedBytes shl 8;
Writeln('packedBytes = ' + IntToBin(packedBytes));
// The data now looks like this:
// packedBytes |00000000|00000000|11101001|00000000|
// byte1 byte2 byte3 byte4
// Now that there's room, lets pack another byte in there!
packedBytes := packedBytes or byte2;
Writeln('packedBytes = ' + IntToBin(packedBytes));
// The result now looks like:
// packedBytes |00000000|00000000|11101001|00111000|
// byte1 byte2 byte3 byte4
// Lets pack the last two bytes using the same method!
// We have to make room first.
packedBytes := packedBytes shl 8;
// Now lets add the byte
packedBytes := packedBytes or byte3;
Writeln('packedBytes = ' + IntToBin(packedBytes));
// And the last byte! Lets make room for it:
packedBytes := packedBytes shl 8;
// Now, add it in there!
packedBytes := packedBytes or byte4;
Writeln('packedBytes = ' + IntToBin(packedBytes));
// If all goes well, you should have successfully packed all four bytes into
// the integer and the data should now look like this:
// packedBytes |11101001|00111000|00000001|11111111|
// byte1 byte2 byte3 byte4
// Congratulations on packing your first four bytes into an integer.
// But how the heck do we get them back out? Well, thats a little bit more
// complex, but you should be able to handle it.
// Again, currently the data looks like this:
// packedBytes |11101001|00111000|00000001|11111111|
// byte1 byte2 byte3 byte4
// Lets say we want to get byte4 out. Well, since its already at the end,
// we don't need to do any shifting at all and we can go straight to masking it.
// What masking does is, for lack of a better word, crop specific bits out.
// If you don't mask out the bits you want, you will also get the bits from
// the other bytes. We want only the 8 bits in byte 4.
Writeln('byte4 = ' + IntToBin((packedBytes and $FF)));
// It can be pretty hard or pretty easy to understand, depending on
// the person. Firstly, $FF is the hexadecimal form of the number 128. I like
// using hexadecimals (along with alot of people) for bits in general, but especially
// for masking since sometimes the numbers can get rather large to remember.
// This statement is pretty much saying to AND the first 8 bits out of the packedBytes.
// This statement isn't completely removing the bits from packedBytes, its just
// retreiving them. Again, if you don't remember what AND does, look back. You probably
// shouldn't be here unless you know what it does.
// Okay, that was simple, now lets retreive byte3. This time, before we can mask
// out the bits that we want, we have to shift them to the end.
// In this case, byte3 is 8 positions away from the end. Then, after we shift the bits,
// we can mask it out properly.
Writeln('byte3 = ' + IntToBin((packedBytes shr 8) and $FF));
// We do the same for byte2, except this time we have to shift it 16 positions,
// for obvious reasons.
Writeln('byte2 = ' + IntToBin((packedBytes shr 16) and $FF));
// Now we're on byte1. For this one, its much simpler because there are no bits
// before it - that means we don't have to mask it out. We simply shift it 24
// bits to the right and everything will be good.
Writeln('byte1 = ' + IntToBin((packedBytes shr 24)));
// Congratulations, you just learned to pack/unpack bytes into integers.
// Hopefully you find a use for it, but even more so than that, I hope it
// taught you more about Bits and how they work!
// As I said before, I'll show you how Simba's color packing works.
// Many of you already know how it works, but for those that don't:
// Colors are generally made up of three values: Red(R), Green(G), Blue(B).
// Commonly known as the RGB value.
// Color integers in Simba are just packed RGB values.
// So to pack the color white R=255, G=255, B=255
R := 255;
G := 255;
B := 255;
colorInt := ((((colorInt or R) shl 8) or G) shl 8) or B;
Writeln('colorInt - ' + IntToStr(colorInt));
// Which can also be written in a much more clean way as:
colorInt := 0;
colorInt := (R shl 16);
colorInt := colorInt or (G shl 8);
colorInt := colorInt or B;
Writeln('colorInt - ' + IntToStr(colorInt));
// Congratulations, you've just reached level 72 in Bit Manipulation.
// Challenge! Unpack the color value '16777215'.
end.
Here is some simple encryption with bits
Encryption:
SCAR Code:
program BitwiseEncryption;
const
TextToEncrypt = 'SRL-Forums';
var
key, index : Integer;
encryptedText, decryptedText : string;
// You don't need to know anything about this function. It simply converts a
// decimal number to binary format for use in this tutorial.
function IntToBin(value : Integer) : string;
begin
repeat
if((value mod 2) = 0) then
result := '0' + result
else
result := '1' + result;
value := value / 2;
until(value = 0);
end;
begin
ClearDebug;
// I'm going to show you a very simple way to encrypt strings using bitwise operators
// We are going to use a key to "sign" each character.
// This is only a 8 bit key so as long as someone knows the algorithm,
// It wouldn't be hard to bruteforce 255 possible keys.
// But this is just to get your feet wet. You can make incredible encryption
// methods with the help of bits.
// This is our 8-bit key. The encryption will change depending on what this value is
// set to. This is similar to what the government uses to protect their shit with.
key := $E2; // 8-bit key
// Basically what we are doing here is looping through each character in TextToEncrypt
// and XOR'ing it with our genious key, if you don't remember what XOR does, look back
// into the beginning of this tutorial. That's it. Now the only way someone can
// decrypt your shit is by bruteforcing 255 combinations.
for index := 1 to Length(TextToEncrypt) do
begin
encryptedText := encryptedText + Chr(Ord(TextToEncrypt[index]) xor key);
end;
Writeln(encryptedText);
// And to decrypt, you do the exact same thing.
for index := 1 to Length(encryptedText) do
begin
decryptedText := decryptedText + Chr(Ord(EncryptedText[index]) xor key);
end;
Writeln(decryptedText);
// Note that this is very simple encryption and I can't be arsed to create
// anything better at the moment. You can make some pretty leet encryption
// algorithms but I'll leave you to do that.
end.
Swapping two integers without third temporary variable:
SCAR Code:
program BitwiseSwap;
var
intX, intY : Integer;
// You don't need to know anything about this function. It simply converts a
// decimal number to binary format for use in this tutorial.
function IntToBin(value : Integer) : string;
begin
repeat
if((value mod 2) = 0) then
result := '0' + result
else
result := '1' + result;
value := value / 2;
until(value = 0);
end;
begin
ClearDebug;
// In this example, I'll show you how to swap two integers without a
// temporary/middleman variable. Its extremely simple but you have to understand
// how XOR works to understand the mechanics. So go back and read what XOR does.
// We have two variables: intX, intY.
intX := 53; // 110101
intY := 101; // 1100101
Writeln('intX = ' + IntToStr(intX) + ' (' + IntToBin(intX) + ')');
Writeln('intY = ' + IntToStr(intY) + ' (' + IntToBin(intY) + ')');
// Currently the bit data of intX and intY looks like this:
// intX - 110101
// intY - 1100101
// First we XOR intX against intY. This pretty much makes it where both variables
// reside in intX temporarily, and can easily be undone by XOR'ing either value.
intX := intY xor intX;
// So now the data looks like this:
// intX - 1010000
// intY - 1100101
// Now we do the same thing, except with intY
intY := intX xor intY;
// So now the data looks like this:
// intX - 1010000
// intY - 0110101
// Now we undo our first operation by XOR'ing intX and intY again.
intX := intY xor intX;
// Now the data looks like this:
// intX - 1100101
// intY - 0110101
Writeln('intX after swap = ' + IntToStr(intX) + ' (' + IntToBin(intX) + ')');
Writeln('intY after swap = ' + IntToStr(intY) + ' (' + IntToBin(intY) + ')');
// The 2 integers are now effectively swapped without a third temporary variable.
end.
That about sums everything up. Hopefully the 4 examples were enough to show you exactly how bits work and how they're useful in different situations.
If you spot any errors, let me know and I'll fix them asap. If you have any questions, please ask.