ID:39760 Feb 29 2008, 5:22 pm (Edited by moderator on Mar 5 2008, 4:57 pm) Keywords: data_structures, math, tutorial 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 1 10 11 100 101 110 111 1000 1001 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 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. 0100 | 1001 ------ 1101 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. 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 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 **. 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 parentheses when you're trying to output them in the same line. (101101 >> 1) = 10110 (101 << 4) = 1010000 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 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. ```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 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. ```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, 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 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. 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. More Examples 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. ```mob/verb blind_player(mob/M in world) M.sight |= BLIND // equivalent to 1 ``` 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. ```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 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#define JUSTIFY_CENTER 1#define JUSTIFY_RIGHT 2#define ELLIPSIS_TEXT 4mob/proc drawtext(t) var/newtext = format_text(t, JUSTIFY_CENTER | ELLIPSIS_TEXT, 20) // draw text on the screenproc 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 & ELLIPSIS_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 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 Feb 29 2008, 5:38 pm I think this line is suppose to have 4 0s at the end, not 3: (101 << 4) = 101000 Feb 29 2008, 5:45 pm Fixed! Thanks. Mar 1 2008, 1:54 pm it socks Mar 1 2008, 2:01 pm It...socks? If you were trying to type "sucks", you're a moron. If you were trying to type "rocks", you're right. Mar 1 2008, 4:01 pm Nonsense! It's far too simple for his complicated mind, dulled by the intellectual experiences he's endured. Mar 4 2008, 3:34 pm I was just glancing through this article, and I noticed that the code is wrong. Someone should fix this with tags. Mar 5 2008, 5:00 pm Dang. Something always slips by me when I try to convert the old articles to this newfangled blog! I've tidied it up (I can't get the DM tag to respect the line breaks properly, but it's at least legible now). Thanks for spotting that! Mar 10 2008, 3:34 pm (Edited on Mar 10 2008, 3:42 pm) I would love to understand everything about how bit flags work but half way through this article I find that I'm pretty much lost. I just don't get all this 1101011 business. Its annoying too because there's so many places where some of the advanced bit functions would come in handy if I knew how to use them. But all I really understand is how to check whether or not a byte has a bit or not. Mar 10 2008, 3:38 pm Heh, yeah, I'll agree there. This article is a bit old, and I would rewrite it if I had the chance of time. I would have liked to expand on the XOR operator, and more real-world usage of bit flags. 