Bit Flags
By: Unknown Person
The use of bit flags in the DM programming language (or any programming language which supports it) can be very useful in some situations. It is very useful if you need to do things fast, and (sometimes) more simple to organize instead of a full-fledged list. Before you can understand how to use bit flags and bitwise operators, you will need to know some binary. If you know binary already, you can skip to the second section.
Binary and Bases
Binary is just another counting system. It is similar to how we count numbers, except the range of one digit is two numbers instead of 10. Binary isn't the only counting system. Some popular counting systems used in computers (and in the past, too) have been used. Like ternary (base 3), hexadecimal (base 16), and so on. Binary uses two symbols, 0 and 1. You can call the ON and OFF, if you would like too.
The binary counting system as I explained above is similar to how we count, except of 0 to 9, we have 0 and 1. Here is list of 1 to 10 in binary.
0 // zero
1
10
11
100
101
110
111
1000
1001
1010 // ten
If you notice the pattern, the numbers increase in length like how we count. It is pretty much the global way to count something (in any base). Our regular counting system is base 10, because it has 10 symbols for each number. You can go above base 10, since you can use letters as representations as numbers. For example, hexadecimal uses the characters 0 to 9, and a to f. This counts to 16, making hexadecimal base 16.
Bits of BYOND
Why use bit flags when programming? We use it because it generates faster code and sometimes can change big blocks of repetitive programming into something smaller. It can also in some situations simplify your programming. If you have realized, BYOND uses many of its built-in functions with numbers which represent binary, and the use of bit operators. For example, the built in directional macros, NORTH, SOUTH, EAST, and WEST are just #define statements built in DM. They represent 1, 2, 4, and 8. If you notice in binary, those represent 1, 10, 100, and 1000 respectively.
Bitwise Operators
Bitwise operators are just operators which manipulates the numbers as binary. The number will still be in base 10 (decimal), but it would do the operations by what it represents in binary. Here are some basics operators:
Bitwise OR operator | (vertical bar)
This operator compares two bits. If both or one of them are on, the resulting bit is on.
0100
| 1001
------
1101
var/a = 4
var/b = 9
var/c = a | b
// c is 13
Bitwise AND operator & (ampersand)
This operator does the bitwise AND function on two integers. If both of the comparing bits are on, the resulting bit is on.
1000
& 1001
------
1000
var/a = 8
var/b = 9
var/c = a & b
// c is 8
Bitwise XOR operator ^ (caret)
This operator returns an exclusive-or function. If the comparing bits are both on, the resulting bit will be off. This includes if both of them are off. Don't mistake this with getting the power of something, because they do something completely different.
1010
^ 1101
------
0111
var/a = 10
var/b = 13
var/c = a ^ b
// c is 7
Bitwise Complement operator ~ (tilde)
This operator returns the integer of the inverted bits. This effect is similar to the ! operator on each bit. Note that even the zeroes up to 16 digits will still be inverted.
~000000010011010 =
111111101100101
~000000001100101 =
111111110011010
var/a = 5 // 0000000000000101
var/b = ~a // 1111111111111010
// b is 65530
Bitwise Shift operators (>> and <<)
The bitwise shift operators shift bits into the left (<<) or right (>>). All bits shifted to the right out of bounds are lost, and are also lost if shifted to the left after 16 bit spaces (65535 in decimal). The shift operator does not loop the bits from the end to the start, and vice versa. Don't mistake this for the << output operator, and make sure you put these bitwise operators in brackets when you're trying to output them in the same line.
(101101 >> 1)
= 10110
(101 << 4)
= 101000
The bitwise shift operators << and >> are respectively equivalent to multiplying and dividing the integer by the amount of bits shifted to the power of 2. Therefore in the example before, b is 20.
var/a =
5 // 0101 = 5
var/b = (a << 2) // 10100 = 20
// b is 20
// 5 * (2**2) = 20
The Usage
What are bit flags and their bitwise operators useful for? One example is restricting movement going in and out certain directions for turfs. We can use how BYOND does directions built in to our advantage. This example will only need the bitwise AND and OR operator. The way to do it is to overwrite turf/Enter() and check the direction of the movable atom which is entering.
turf
var
rin = 0 //
restricted directions going in
rout = 0 // restricted
directions going out
Enter(atom/movable/A)
if(A.dir & rin)
// compare the bit flags of the object's
direction to the restricted ones
return 0 // deny movement if it exists in the rin
list
return ..()
// move normally otherwise
Exit(atom/movable/A) // same for Exit()
if(A.dir & rout)
return 0
return ..()
narrow_wall
rin = NORTH | SOUTH
rout = NORTH | SOUTH
// the rin and rout bit flags read as 0011, since NORTH and
SOUTH
// are 1 and 10 respectively in binary
claustrophobia_room
rin = NORTH | SOUTH | EAST | WEST
rout = 15 // equivalent to above "1111"
This example shows a fast and convenient way to deny movement from multiple directions. It would be easier to use bit flags in this type of system instead of a list of denied directions. The whole point of using bit flags are that you only have a number as a variable. This system also supports non-cardinal directions, and ones you may want to define yourself. (Note that UP and DOWN are already built in BYOND, but undocumented. They are equivalent to 16 and 32.) Also note that doing NORTH | SOUTH is equivalent to typing in 1 | 2 or just 3.
Another useful you might encounter while programming is checking whether a direction is cardinal (non-diagonal) or not. Well, if you knew nothing about bit flags, you would check the direction for north, south, east and west. Or if you were even more savvy, you would make a list full of cardinal directions, and check if their direction is in the list. Well, there is a trick to check if a direction is cardinal. A simple if check of dir & (dir - 1) would do. I will explain how this works.
mob/verb
test()
src.dir = NORTHWEST
if(src.dir & (src.dir - 1))
src << "Your direction is
diagonal."
else
src << "Your direction is
cardinal."
This outputs "Your direction is diagonal." because the statement returns true. If we dissect the fourth line, we can understand it more clearly.
src.dir & (src.dir - 1)
First, lets turn this to their binary values. Since NORTHWEST = NORTH | WEST = 1 | 8 = 9, we compare 9 to 9 - 1
9 & (9 - 1)
9 & 8
1001 & 1000
1001
& 1000
------
1000
Since 9 & 8 equals 8, and it is a true value, it returns true. This means it is non-cardinal. But we still need to prove it will do the opposite if a cardinal direction is put in. Let's plug in EAST and see if it will return 0.
// EAST = 4 = 0100
4 & (4 - 1)
4 & 3
0100 & 0011
0100
& 0011
------
0000
If you keep on doing this for cardinal and non-cardinal directions, there is a pattern. If you notice, every cardinal direction, there is only one bit on. Since the non-cardinal directions are combinations of the bits, there are more than one. When you decrease a number which is divisible by 2 until it hits 1, it turns off that specific bit, and turns on all of the ones behind it. This is similar to our decimal system of numbers. If you have 10,000 and subtract it by 1, you get 9,999. Same for binary and all other forms of counting. If you compare the original number, and the number subtracted by 1, two bits are never the same. On the other hand, if there is more than one bit turned on, there will be at least one bit flag which is the same, which returns true.
This expression does not only apply to directions. It also can tell us if there is a combination of bits on, or just one bit. This expression will return true if there is more than one bits turned on.
On another note, the expression does not need the brackets around it. It is just used to clarify on what goes on first. Bitwise operators have a pretty low priority in the order of operations. Therefore, the expression is equivalent to dir & dir - 1.
More Examples
So far, I have only given you examples on how to manipulate bits to be combined and checked. That would only be semi-useful in the world of bit flags. Let's look at our built-in variable, sight. If you look at the DM Reference, sight uses a series of bit flags to determine what the mob can see and what it can't see. If you notice, the constants SEE_INFRA, SEE_MOBS, SEE_OBJS, and so on are just numbers. They are just numbers which were defined with #define statements. Let's give an example on how you can turn on some bits in this example.
mob/verb
blind_player(mob/M in world)
M.sight |= BLIND // equivalent to 1
Assuming sight was 0 before this verb was called, you can use bitwise operators like normal logical operators with a = sign in front of it, and it will set it to what operator you used. Let's dissect this to get a closer look at it.
M.sight = M.sight | 1
M.sight = 0 | 1
M.sight = 0000 | 0001
M.sight = 1
This is a simple example on how to turn on a specific bit. Note that A |= B is equivalent to A = A | B, which we used in a previous example. Now to turn off a bit, we manipulate the bitwise AND and bitwise Complement operator.
mob/verb
unblind_player(mob/M in world)
M.sight &= ~BLIND // ~BLIND equivalent to inverted 1,
which is 0
When look at it logically, we get this.
M.sight = 1 & ~1
M.sight = 1 & 0
M.sight = 0
It is also possible to turn on more than one bits at the same time. The formula for turning them on is flags |= (flag1 | flag2 | flag3). For turning them off, we use flags &= ~(flag1 | flag2 | flag3). Try dissecting these formulas yourself, and seeing how they work.
Defining our own System
With the convenience of bit flags, you can create your own procedures with the power of bit flags. This is especially convenient for libraries. Let's say in a procedure has different settings that can go with it. Depending on these settings, the proc would act differently, and do different things. The proc will be a text manipulator for text on the HUD which will be able to center text, justify it, and some other stuff you might want to add.
#define JUSTIFY_LEFT 0
#define JUSTIFY_CENTER 1
#define JUSTIFY_RIGHT 2
#define ELIPSIS_TEXT 4
mob/proc
drawtext(t)
var/newtext = format_text(t, JUSTIFY_CENTER | ELIPSIS_TEXT,
20)
// draw text on the screen
proc
add_spaces(txt, n, p)
// txt = text; n = number of spaces; if p == 0 add spaces
before
var/newtext = txt
for(var/i = 1 to n)
newtext = (p ? newtext + " " : "
" + newtext)
return newtext
format_text(t, flags, maxlen)
var/newtext = t
var/cl = maxlen - length(t)
if(flags & JUSTIFY_CENTER)
newtext = add_spaces(newtext, round(cl))
newtext = add_spaces(newtext, round(cl, 1), 1)
else if(flags & JUSTIFY_RIGHT)
newtext = add_spaces(newtext, cl)
if(flags & ELIPSIS_TEXT)
for(var/i = 1, i < length(t), i += maxlen)
newtext = copytext(newtext, 1, i) +
"\n" + copytext(newtext, i+1)
++i
return newtext
This is simply how you can use bit flags instead of using traditional arguments/text settings in a proc. It sometimes simplifies the work for the programmer and the user of a library or demo. If you end up needing to have many arguments which have a setting of 1 or 0, bit flags is the choice for you.
Conclusion
Bit flags are fast ways to do things while programming. They sport the ability to act as "mini-parameters" and the stuff built-in BYOND helps us take advantage of it (i.e. the directional system and some variables.) Bit flags also tend to generate faster code than some of the normal operators. If you do a quick speed test from using the bitwise shift operator and multiplying a variable by a number, the bitwise way works around 20% faster. In conclusion, one should learn how to use bit flags to their advantage.
October 30th, 2005