This is a tutorial about bitwise operators in computer languages. They can be very useful for calculations which require speed and a small amount of memory.
Bits
In bitwise operators, you will mostly have to think of numbers are the computer sees them, in bits, also called the binary system.
To teach you that would take a whole tutorial of its own, but most people around here seem to know it already. If you dont know them, I suggest you find a tutorial or article to explain them, they are quite well known and will probably be easy to find.
Find out why 1111 = 15, why 1001 = 9
Note: For the purposes of this tutorial, all data types, such as byte, short and integer, are unsigned.
Bitwise Shift
These are probably the most well-known operations, what they do is simply shift bits around, they can be shift right, or shift left.
In Scar and pascal, they are SHR (SHift Right) and SHL (SHift Left).
In C-based languages, they are >> (shift right) and << (shift left)
To get these, think of the bits, heres an example
2 shl 1 = 4
what is means is, the bits of 5, shifted to the left by 1, will give 10. See the bits table below
0010 shl 1 = 0100
as you can see, the bits have shifted to the left.
Shift Right does the opposite, shifts every bit to the right
8 shr 2 = 2
1000 shr 2 = 0010
So what do these mean for us? Well, shift-left multiplies the number by a power of 2, so shl 1 times by 2, shl 2 times by 4, shl 3 times by 8. That seems a bit useless, why not just do 2 * 2 = 4, well the answer is speed. Computers find it relativly difficult to multiply and add numbers, and relativly easy to shift bits around, bit-shifts are slightly faster than additions and much faster than multiplications. This is may not seem so important right now, but if you ever make a 3D flight simulator game, it will be very important when you have to update a few thousand pixels 25 times a second, you can only times and divide by powers of two, but if you use it in combination with adding at as well, it can still be faster. Another use for shifts is to combine numbers, such as two bytes can be made into a short integer, but we'll get to that later.
Bitwise Or
This is an operation which takes two number, and applies the OR logical operator on each bit.
Note: do not confuse bitwise 'or' with boolean 'or', they are completely differant operations which just happen to have the same name.
In scar and pascal, it is the same as the boolean or
In C-based languages, it is | (verticle line or pipe)
Look at this logical 'or' table
0 or 1 -> 1
1 or 0 -> 1
1 or 1 -> 1
0 or 0 -> 0
Bitwise OR applies this table to every bit, heres an example.
12 or 2 = 14
1100 or 0010 = 1110
Bitwise or is used to combine bits into one number, more on this later.
Bitwise And
This is an operation which takes two numbers, and applies the AND logical operator on each bit.
In scar and pascal, it is the same as the boolean and
In C-based languages, it is & ('and' sign or ampersand)
Look at this logical 'and' table
0 or 1 -> 0
1 or 0 -> 0
1 or 1 -> 1
0 or 0 -> 0
Bitwise AND applies this table to every bit, heres an example.
12 and 9 = 8
1100 and 1001 = 1000
Bitwise or is used to separate bits from a number, more on this later.
Example - Flags of an object
Here's an example of using bitwise and and or.
Lets say you're making an army game, where differant soldiers have differant qualifications, so one soldier can be able to use granades, also could handle an explosives kit, or perhaps a surface-to-air missile, or maybe be a medic. A soldier can be all these things at once, or non at all. Lets say you want to make a record of these skills, how would you do it?
you could do it with a few booleans like this
SCAR Code:
type
Soldier = record
isGranader: boolean;
canHandleExplosives: boolean;
canUseSurfaceToAir: boolean;
isMedic: boolean;
end;
it could also be an array, with each index carefully used.
SCAR Code:
type
Soldier = record
Skills:array[0..3] of boolean;
end;
//these are the indexes to use in the array
const
SkillGranader = 0;
SkillExplosives = 1;
SkillSurfaceToAir = 2;
SkillMedic = 3;
Then when you need to access the skill, you would do
SCAR Code:
if(mySoldier.Skills[SkillGranader])then
Writeln('Its a granader!');
Now the last way, which could be the most efficent, is to have each bit in a number represent a boolean.
The idea is, you define a 'flag' to represent each skill, these flags have to have bits which are all zeros and one 1. See this example, the bit forms of the numbers are in comments.
SCAR Code:
const
SkillGranader = 1; //0001
SkillExplosives = 2; //0010
SkillSurfaceToAir = 4;//0100
SkillMedic = 8; //1000
in your record, you have one integer variable.
SCAR Code:
type
Soldier = record
Skills: integer;
end;
Lets say you want a soldier to have the skills of granader and medic, you would use the 'or' bitwise operator to combine the two values.
SCAR Code:
mySoldier.Skills := SkillGranader or SkillMedic;
what that does to the bits is shown here.
0001 or 1000 = 1001
So thats the skills encoded, but how do you get them back out again? The answer is to use the bitwise 'and' operator. you need to 'and' the skills and the skill you want to test for, if the result is not zero, it means it is true, see the example.
SCAR Code:
function IsGranader(mySoldier : Soldier): Boolean;
begin
if(mySoldier.Skills and SkillGranader <> 0)
Result:= True;
end;
what that does to the bits is shown here.
1001 and 0001 = 0001
1 is not equal to zero, so the Skills must contain SkillGranader, this is what happens if you test for a skill which isnt contained.
1001 and 0100 = 0000
the number returned is zero, so the skills do not contain SkillSurfaceToAir.
The advantage to this method is the memory usage, in most languages, a boolean is stored in a byte, which contains 8 bits, but only 1 bit is used, 1 is true, 0 is false, so the other 7 bits are wasted. It is also useful for sending over a network, you can send 8 booleans in 1 byte, where as the other methods would have to send 8 bytes.
Bitwise Not
This is an operation which takes a number and reverses every bit
In scar and pascal, it is the same as the boolean not
In C-based languages, it is ~ (tidle)
Look at this logical 'not' table
0 not -> 1
1 not -> 0
Bitwise NOT applies this table to every bit, heres an example.
12 not = 3
1100 not = 0011
Bitwise Xor
This is an operation which takes two numbers, and applies the XOR logical operator on each bit.
In scar and pascal, it is used with xor
In C-based languages, it is ^ (caret)
Look at this logical 'Xor' table
0 or 1 -> 0
1 or 0 -> 0
1 or 1 -> 0
0 or 0 -> 1
Bitwise Xor applies this table to every bit, heres an example.
12 or 9 = 7
1100 or 1001 = 0111
Its roughly equivalent to using bitwise or then bitwise not, but faster of course.
Example - Colours in computers
One place bitwise operators are always used is in encoding colours, you all know how in scar, colour is represented by a single integer from 0 to 16777215. Many of you also know that colour is actually represented as three bytes, from 0 to 255. So how does they get encoded into that big integer, the answer is with bitshifts. To encode a number, you leave the red alone, you shift the green 8 spaces, and the blue 16 spaces and 'or' all three numbers toghether. The bits of the colour end up looking like this.
111100000000111111111111
The red, green and blue components of this colour are 255, 15 and 240.
The win32 integer representing this colour is 15732735, it is just one number, but it contains all three values,
This is a function, written in scar, which changes RGB to win32 colour, I'm willing to bet about £5 that the identical function is in Scar.
SCAR Code:
function RGBToColor(r, g, b: Integer): Integer;
begin
Result:= (r) or (g shl 8) or (b shl 16);
end;
so now you have a number which can efficently be printed out, sent along a network or saved to file, but how do you separate the rgb components out again? Most people try reversing the bit-shifts, but that isnt enough, since its one number, not three. Look at this example.
SCAR Code:
//trying to get the green component
15732735 shr 8 = 61455
well the green component is not 61455 is it, this is because we kept the other bits as well, it works like this.
11110000 00001111 11111111 shr 8 = 11110000 00001111
what we have to do is to use the 'and' operator, we just want to cut out the last 8 bits, to do this, we need a number with the last 8 bits all filled, which happens to be 255. See the table.
11110000 00001111
and
00000000 11111111
=
00000000 00001111
(15)
using 'and' 255 gives us 15, which is the correct green component.
So the procedure is to do the reverse bit-shift, then and the return with 255.
This is a procedure which changes win32 to RGB color, the one in Scar is probably the same.
SCAR Code:
procedure ColorToRGB(Color: Integer; var r, g, b: Integer);
begin
r:= (Color) and 255;
g:= (Color shr 8) and 255;
b:= (Color shr 16) and 255;
end;
And that is all I have to show you about bitwise operators, I know I ran over the part about xor and not, but I just never really saw them being used for anything.