Bitwise AND and you: how to store many flags as a single value

じ☆ve冰风

Hi there, sports fans! The new Jump into Javascript is on its way (along with the Trilobytes freebie plugin) but for now, I'm here with a tutorial on a little trick you may not be aware of: bitwise AND! (&)

First of all, for anyone not yet aware of this, computers don't really understand numbers the way we do. Base 10 is a foreign concept to them; they work in base 2, or binary. What we see as the integer 7, for example, would be 111 to a computer (or rather, something like 0000 0111 when dealing with full bytes, but that's a topic for another time). Where our number system has a 1s place (10 ^ 0), a 10s place (10 ^ 1), a 100s place (10 ^ 2) etc. with each place being the next power of 10 up (for example, the integer 409 means there are 4 100s, 0 10s and 9 1s) binary goes up in powers of 2: it has a 1s place (2 ^ 0), a 2s place (2 ^ 1), a 4s place (2 ^ 2), an 8s place (2 ^ 3), a 16s place (2 ^ 4) etc. So 111, 7, is really "one 4, one 2, one 1".

So how does this help us when storing flags? Simple! Since there are only two possible values for a binary digit, each one effectively acts as a switch. It's either 0 (off) or 1 (on). We can take advantage of this to stuff many switch values into one number.

Let's say you have 4 NPCs that have to be talked to, and then a 5th NPC that will offer a quest once you've spoken to those 4. Now you could use switches for that, but that's an allocation of 4 game switches just for one quest, which isn't great economy. Or you could use a variable that goes up by 1 every time you speak to an NPC, and that's great, but what if, when you haven't talked to them all, we want the 5th NPC to tell you *which ones* you still need to talk to? With a variable, we don't have that information. We could use self switches, sure, but that's not flashy and impressive like this is about to be.

So the first thing to do is to assign each NPC a value; that value being the next "place" up in the base 2 hierarchy. So our first NPC is 1, the second is 2, the third is 4, and the fourth is 8. This allows us to verify any combination of NPC interactions: if the value is 5, we know you've spoken to the first and third NPCs. If it's 10, we know you've spoken to the second and fourth. If it's 11, you spoke to the first, third and fourth...and so on.

And sure, we could use base 10 comparisons here. We could reduce the value by the one we're checking for, and check whether it's still > 0, and if so we know that NPC was spoken to. But there's a far easier way to do that: bitwise AND.

To put it in the simplest possible terms, a bitwise AND operation compares two binary digits, and returns the resulting value when the only bits that are ON (1) are the ones where they were on in both of the digits. For example:

4 & 10

0100 & 1010

This would give us 0, because there is no bit in either number that's also 1 in the other number. In 4, only the 4 bit is on. In 10, the 8 and 2 bits are on.

3 & 7

0011 & 0111

This would give us 0011, or 3, because the only common bits are the 2 and the 1.

So how does this help us to verify flags? Well, if we take our NPC interactions variable and do a bitwise AND operation with the value of the NPC we're checking for, we'll get back that value if the relevant bit is on. So let's say our variable is 10 and we want to check whether you've spoken to the second NPC:

10 & 2

1010 & 0010

Since 2 is the only common bit, we'd get back 0010, telling us that this NPC has indeed been interacted with.

Now with only four values, that doesn't look massively impressive, but let's say we want to track...20 NPCs. Think about the expenditure that would take in terms of switches. With flags, it's simple: our value is going to be anywhere from 0 to 524,288.

Let's say it's 32,330 (0111 1110 0100 1010). This tells us that we've interacted with NPC 2 (2), 4 (8), 7 (64), 10 (512), 11 (1024), 12 (2048), 13 (4096), 14 (8192), and 15 (16384). You can check any one specific NPC with a bitwise AND operation for the associated flag. So if you want to know if you've interacted with NPC 11, you'd do your interaction variable & 1024.

This technique is in fact used in the base engine, believe it or not: in tilesets. Bitwise and operations are used to determine passability as each aspect of a tile is assigned a binary digit. For example, "star passability" is 16.

So there you have it! Bitwise AND can be a very powerful tool in your arsenal if you know how to wield it. But really, as long as you can multiply a number by 2, it's not hard to do. Do you use bitwise AND in your own development? If so, what do you use it for?


本贴来自国际rpgmaker官方论坛作者:Trihan处,因国际论坛即将永久关站,为了存档多年珍贵资料,署名转载到本论坛存档,由于官方帖子为英文原帖，需要中文翻译请点击论坛顶部切换语言为中文就可以将帖子翻译成中文浏览,方便大家随时查看,原文地址：https://forums.rpgmakerweb.com/threads/bitwise-and-and-you-how-to-store-many-flags-as-a-single-value.165338/