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 than 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. Other counting systems have been used in computers and in the past, such as ternary (base 3) and hexadecimal (base 16). Binary uses two symbols, 0 and 1. You can call them ON and OFF, if you would like to.
The binary counting system as I explained above is similar to how we count, except instead of 0 to 9 in each digits place, we have only 0 and 1. The list below shows the numbers 1 through 10 in binary.
0 // zero
1010 // ten
If you notice the pattern, the numbers increase in length as decimal numbers do. 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 of numbers; for example, hexadecimal uses the characters 0 to 9, and A to F. This provides 16 possible digits in each place.
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. In fact, many of BYOND's built-in functions use numbers that can be easily handled with of bit operators; for example, the built-in directional macros, NORTH, SOUTH, EAST, and WEST, are just #define statements built into DM. They represent 1, 2, 4, and 8. In binary, those represent 1, 10, 100, and 1000 respectively.
Bitwise operators are just operators which manipulate binary numbers. The number will still be in base 10 (decimal) in your code, but the operators act on what the number represents in binary. Here are some basic operators:
Bitwise OR operator | (vertical bar)
This operator compares two bits. If one or both of them are on, the resulting bit is on.
var/a = 4
var/b = 9
var/c = a | b
// c is 13
Bitwise AND operator & (ampersand)
This operator performs the bitwise AND function on two integers. If both of the comparing bits are on, the resulting bit is on.
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 one (and only one) of the compared bits is on, the result bit will be on. Don't mistake this with exponentiation (X to the Yth power), which many languages represent with the ^ character; in DM the exponentiation operator is **.
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.
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 parentheses when you're trying to output them in the same line.
(101101 >> 1)
(101 << 4)
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
What are bit flags and their bitwise operators useful for? One example is restricting movement directions permitted for entering and exiting turfs. We can use BYOND's built-in directions 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.
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 task you might encounter 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 the 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.
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, let's turn this into binary values. Since NORTHWEST = NORTH | WEST = 1 | 8 = 9, we compare 9 to 9 - 1:
9 & (9 - 1)
9 & 8
1001 & 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
If you keep on doing this for cardinal and non-cardinal directions, there is a pattern. Since the non-cardinal directions are combinations of bits, decrementing the number will leave the leftmost bit unchanged. But when you decrement a number which is a power of 2 (and thus only has one bit on), that bit is turned off, and all of the ones to its right are turned on. (This is similar to our decimal system of numbers. If you have 10,000 and subtract 1, you get 9,999.)
This expression does not only apply to directions; it works in any case where we want to know if there is a combination of bits on, or just one bit. This expression will return true if there is more than one bit turned on.
Note that the expression does not need parentheses around it -- they are just there to clarify on what goes on first. Bitwise operators have a pretty low priority in the order of operations, so the subtraction will be evaluated first.
So far, I have only given you examples of 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 which were defined with built-in #define statements. Let's give an example of how you can turn on some bits in this example.
Let's assume sight was 0 before this verb was called, and 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 of 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.
M.sight = 1 & ~1
M.sight = 1 & 0
M.sight = 0
It is also possible to turn on more than one bit 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
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.
Bit flags are fast ways to set and check values. They sport the ability to act as "mini-parameters", and many built-in BYOND values help us take advantage of it (e.g., the directional system and sight variables). Bitwise arithmetic tends to be faster as well; if you do a quick speed test comparing the bitwise shift operator and multiplying a variable by a number, the bitwise way works around 20% faster. It's worth learning how to use bit flags to your advantage.
October 30th, 2005