Bit explanation

ID:180362
 
Jul 13 2001, 12:45 pm
Could someone explain to me exactly how bits and bit shifting in a game work? I don't know if this could really help me, but I'm just curious as to how they work. It would also help if you could point me to a tutorial on them (I know they're not just a BYOND thing).

Thank you.
Jul 13 2001, 12:53 pm
On 7/13/01 4:45 pm Cinnom wrote:
Could someone explain to me exactly how bits and bit shifting in a game work? I don't know if this could really help me, but I'm just curious as to how they work. It would also help if you could point me to a tutorial on them (I know they're not just a BYOND thing).

I wrote up a little "bit" (hardy har har) on this a while ago. It doesn't explain bit shifting but it does discuss some of the basic operations.

http://www.byond.com/forum/ forum.cgi?action=message_read&forum=bugs&message=1081

[Edit-- how embarrassing, I used that exact same "bit" joke in the original post!]
Jul 13 2001, 1:04 pm
In response to Tom
On 7/13/01 4:53 pm Tom wrote:
On 7/13/01 4:45 pm Cinnom wrote:
Could someone explain to me exactly how bits and bit shifting in a game work? I don't know if this could really help me, but I'm just curious as to how they work. It would also help if you could point me to a tutorial on them (I know they're not just a BYOND thing).

While there's never nothing wrong with learning something new, I'll chime in to say that it would be extremely rare to have a situation where you'd want to use bit-shifting.

In general in this "100s of megs of RAM per machine" world, the memory benefits of using bits are far outweighed by the obfuscation of the code.

Code that uses bit-shifting and AND/OR logic left and right is hard to read and understand for mere mortals, hard to debug, difficult to extend, etc.
Jul 13 2001, 1:13 pm
In response to Tom
[Edit-- how embarrassing, I used that exact same "bit" joke in the original post!]

But it just never gets old!
Jul 13 2001, 1:25 pm
In response to Tom
On 7/13/01 4:53 pm Tom wrote:
On 7/13/01 4:45 pm Cinnom wrote:
Could someone explain to me exactly how bits and bit shifting in a game work? I don't know if this could really help me, but I'm just curious as to how they work. It would also help if you could point me to a tutorial on them (I know they're not just a BYOND thing).

I wrote up a little "bit" (hardy har har) on this a while ago. It doesn't explain bit shifting but it does discuss some of the basic operations.

http://www.byond.com/forum/ forum.cgi?action=message_read&forum=bugs&message=1081

[Edit-- how embarrassing, I used that exact same "bit" joke in the original post!]

Thank you, that expains a lot about the comparison of them. But what about the shifting of bits? (I'm hoping I shouldn't know about that from reading your post =)
Jul 13 2001, 1:27 pm (Edited on Jul 13 2001, 1:35 pm)
On 7/13/01 4:45 pm Cinnom wrote:
Could someone explain to me exactly how bits and bit shifting in a game work? I don't know if this could really help me, but I'm just curious as to how they work. It would also help if you could point me to a tutorial on them (I know they're not just a BYOND thing).

Thank you.

Not sure how much you already know on the subject, but here goes.

Whole numbers from 0 to 65535 are often stored in the computer as "16-bit" integers. What this means is that a number takes up 16 bits of information. A bit can only have two possible values: 1 or 0. Everything in a computer is made up of bits, just a whole bunch of 1s and 0s, arranged in the right way, and you get something beautiful, like BYOND. ;-)

So, think of a bit as a tiny little memory slot that can have 1 or 0 in it (sometimes, these are also referred to as on or off). So, a 16-bit number has 16 slots:
<code> . . . . . . . . . . . . . . . . </code>
Each one has a 1 or a 0. It's kinda hard to explain how the order of the 1s and 0s turns it into a number from 1 to 65535 without knowing about different bases. Not sure if you do... but I'll try. ;-)

The rightmost slot means add 1 to the number if the bit is 1, 0 if it is 0. The next slot over means add 2 if the bit is 1. Next means add 4 if the bit is 1, next is 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, and the last slot means add 32768 if the bit is 1, 0 if it is 0. Turns out, you can get every single number from 0 to 65535 by having different combinations of the various slots have a 1 or 0 bit in them.

Some examples:
<code> 0000000000000001 is the number 1. (1 + 0 + 0 + ...) 0000000000000010 is the number 2. (0 + 2 + 0 + ...) 0000000000000011 is the number 3. (1 + 2 + 0 + ...) 0000000000001011 is the number 11. (1 + 2 + 0 + 8 + 0 + ...) </code>
And so on, and so forth. That's how the computer actually sees the number in its memory.

So, when is bit shifting useful? Well, for one thing, one cool consequence of setting up the numbering this way is that to multiply a number by 2, you just shift all of the bits to the left one slot.

For example:

0000000000001011 is the number 11 (1 + 2 + 0 + 8). Shift everything to the left by one slot, and I get 0000000000010110, which is (0 + 2 + 4 + 0 + 16) = 22 = 2 * 11!

By the same token, dividing by 2 happens to be the same as shifting all the bits to the right by one spot. Divide by 4 is a right shift by 2 slots. Multiply by 8 is left shift by 3 slots. And so on.

To be honest, I can't think of a really compelling reason to use bit shifting in a game. You can already multiply and divide using the standard operators, plus you get decimal precision. With 16-bit integers, everything after the decimal place is truncated. But, shifting bits is much faster than generic multiplication. If you need to divide a whole bunch of numbers by 2 or 4 or (any power of 2) and you don't care about decimal precision, this could be a lot more efficient.

But there are other "bitwise" operations you can do. The bitwise AND operator compares two numbers, looking at all 16 slots. For each slot, if both numbers have a bit of 1, the AND result is also a 1 (so, it means "1 AND 1"). If either one or both is 0, the AND result is a 0 (not "1 AND 1"). Here's an example:

var/blah = 23 & 15

What's the result of that operation? Well, let's look at the bits.
<code> 23: 0000000000010111 15: 0000000000001111 </code>
Now, look at each slot. Wherever both numbers have a 1, put a 1 in the answer. Everywhere else, put a 0. So the answer is:<code> 0000000000000111 = (1 + 2 + 4 + 0 ...) = 7 </code>
So blah = 7.

Along the same lines is bitwise OR. Logically, in each slot it returns a 1 if the first bit OR the other bit is a 1.

So, var/blah = 23 | 15 results in blah = 31. Getting there is left as an exercise for the reader. ;-)

Again, though, I don't see much use for this in a game. One common use is if you have a lot of variables (often called flags) that can have two possible values: on or off. Then you could use a single number to represent them all: each bit slot is a different flag. A bit of 1 means on, 0 means off.

Let's say you have a monster mob and you want to track a bunch of things, like: is he scared, is he hungry, is he mad, is he sad, is he afraid of the dark. Assign the "scared" flag to bit position 1, hungry to 2, mad, to 3, sad to 4, and dark to 5. Then you could do something like this:

<code> #define SCARED_FLAG 1 // 00001 #define HUNGRY_FLAG 2 // 00010 #define MAD_FLAG 4 // 00100 #define SAD_FLAG 8 // 01000 #define DARK_FLAG 16 // 10000 mob monster var/status = 0 // he starts out not scared, hungry, mad, sad, or afraid of the dark proc/GetStatus() if (status & SCARED_FLAG) usr << "[src] is scared" if (status & HUNGRY_FLAG) usr << "[src] is hungry" if (status & MAD_FLAG) usr << "[src] is mad" if (status & SAD_FLAG) usr << "[src] is sad" if (status & DARK_FLAG) usr << "[src] is afraid of the dark" proc/MakeMadAndHungry() status |= MAD_FLAG | HUNGRY_FLAG </code>

Normally, though, there's no real advantage to this over just having a separate var for each condition. The only time you really want this is if you have lots (millions?) of monsters to keep track of. In that case, using only one variable instead of 5 different vars will save you about 16 megabytes of memory usage for a million monsters. If you had 16 vars, it would save about 60 megabytes per million monsters. Then it's useful to look into this stuff.

Anyone else think of better uses in games?
Jul 13 2001, 1:37 pm
In response to Air Mapster
On 7/13/01 5:27 pm Air Mapster wrote:
On 7/13/01 4:45 pm Cinnom wrote:
Could someone explain to me exactly how bits and bit shifting in a game work? I don't know if this could really help me, but I'm just curious as to how they work. It would also help if you could point me to a tutorial on them (I know they're not just a BYOND thing).

Thank you.

Not sure how much you already know on the subject, but here goes.

Whole numbers from 0 to 65535 are often stored in the computer as "16-bit" integers. What this means is that a number takes up 16 bits of information. A bit can only have two possible values: 1 or 0. Everything in a computer is made up of bits, just a whole bunch of 1s and 0s, arranged in the right way, and you get something beautiful, like BYOND. ;-)

So, think of a bit as a tiny little memory slot that can have 1 or 0 in it (sometimes, these are also referred to as on or off). So, a 16-bit number has 16 slots:
<code> > . . . . . . . . . . . . . . . . > </code>
Each one has a 1 or a 0. It's kinda hard to explain how the order of the 1s and 0s turns it into a number from 1 to 65535 without knowing about different bases. Not sure if you do... but I'll try. ;-)

The rightmost slot means add 1 to the number if the bit is 1, 0 if it is 0. The next slot over means add 2 if the bit is 1. Next means add 4 if the bit is 1, next is 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, and the last slot means add 32768 if the bit is 1, 0 if it is 0. Turns out, you can get every single number from 0 to 65535 by having different combinations of the various slots have a 1 or 0 bit in them.

Some examples:
<code> > 0000000000000001 is the number 1. (1 + 0 + 0 + ...) > 0000000000000010 is the number 2. (0 + 2 + 0 + ...) > 0000000000000011 is the number 3. (1 + 2 + 0 + ...) > 0000000000001011 is the number 11. (1 + 2 + 0 + 8 + 0 + ...) > </code>
And so on, and so forth. That's how the computer actually sees the number in its memory.

So, when is bit shifting useful? Well, for one thing, one cool consequence of setting up the numbering this way is that to multiply a number by 2, you just shift all of the bits to the left one slot.

For example:

0000000000001011 is the number 11 (1 + 2 + 0 + 8). Shift everything to the left by one slot, and I get 0000000000010110, which is (0 + 2 + 4 + 0 + 16) = 22 = 2 * 11!

By the same token, dividing by 2 happens to be the same as shifting all the bits to the right by one spot. Divide by 4 is a right shift by 2 slots. Multiply by 8 is left shift by 3 slots. And so on.

To be honest, I can't think of a really compelling reason to use bit shifting in a game. You can already multiply and divide using the standard operators, plus you get decimal precision. With 16-bit integers, everything after the decimal place is truncated. But, shifting bits is much faster than generic multiplication. If you need to divide a whole bunch of numbers by 2 or 4 or (any power of 2) and you don't care about decimal precision, this could be a lot more efficient.

But there are other "bitwise" operations you can do. The bitwise AND operator compares two numbers, looking at all 16 slots. For each slot, if both numbers have a bit of 1, the AND result is also a 1 (so, it means "1 AND 1"). If either one or both is 0, the AND result is a 0 (not "1 AND 1"). Here's an example:

var/blah = 23 & 15

What's the result of that operation? Well, let's look at the bits.
<code> > 23: 0000000000010111 > 15: 0000000000001111 > </code>
Now, look at each slot. Wherever both numbers have a 1, put a 1 in the answer. Everywhere else, put a 0. So the answer is:<code> > 0000000000000111 = (1 + 2 + 4 + 0 ...) = 7 > </code>
So blah = 7.

Along the same lines is bitwise OR. Logically, in each slot it returns a 1 if the first bit OR the other bit is a 1.

So, var/blah = 23 | 15 results in blah = 31. Getting there is left as an exercise for the reader. ;-)

Again, though, I don't see much use for this in a game. One common use is if you have a lot of variables (often called flags) that can have two possible values: on or off. Then you could use a single number to represent them all: each bit slot is a different flag. A bit of 1 means on, 0 means off.

Let's say you have a monster mob and you want to track a bunch of things, like: is he scared, is he hungry, is he mad, is he sad, is he afraid of the dark. Assign the "scared" flag to bit position 1, hungry to 2, mad, to 3, sad to 4, and dark to 5. Then you could do something like this:

<code> > #define SCARED_FLAG 1 // 00001 > #define HUNGRY_FLAG 2 // 00010 > #define MAD_FLAG 4 // 00100 > #define SAD_FLAG 8 // 01000 > #define DARK_FLAG 16 // 10000 > > mob > monster > var/status = 0 // he starts out not scared, hungry, mad, sad, or afraid of the dark > > proc/GetStatus() > if (status & SCARED_FLAG) > usr << "[src] is scared" > if (status & HUNGRY_FLAG) > usr << "[src] is hungry" > if (status & MAD_FLAG) > usr << "[src] is mad" > if (status & SAD_FLAG) > usr << "[src] is sad" > if (status & DARK_FLAG) > usr << "[src] is afraid of the dark" > > proc/MakeMadAndHungry() > status |= MAD_FLAG | HUNGRY_FLAG > </code>

Normally, though, there's no real advantage to this over just having a separate var for each condition. The only time you really want this is if you have lots (millions?) of monsters to keep track of. In that case, using only one variable instead of 5 different vars will save you about 16 megabytes of memory usage for a million monsters. If you had 16 vars, it would save about 60 megabytes per million monsters. Then it's useful to look into this stuff.

Anyone else think of better uses in games?


Isn't that also called Binary
Jul 13 2001, 1:38 pm
In response to Nadrew
On 7/13/01 5:37 pm Nadrew wrote:
Isn't that also called Binary

Yup.
Jul 13 2001, 1:39 pm
In response to Deadron
On 7/13/01 5:04 pm Deadron wrote:
On 7/13/01 4:53 pm Tom wrote:
On 7/13/01 4:45 pm Cinnom wrote:
Could someone explain to me exactly how bits and bit shifting in a game work? I don't know if this could really help me, but I'm just curious as to how they work. It would also help if you could point me to a tutorial on them (I know they're not just a BYOND thing).

While there's never nothing wrong with learning something new, I'll chime in to say that it would be extremely rare to have a situation where you'd want to use bit-shifting.

In general in this "100s of megs of RAM per machine" world, the memory benefits of using bits are far outweighed by the obfuscation of the code.

Code that uses bit-shifting and AND/OR logic left and right is hard to read and understand for mere mortals, hard to debug, difficult to extend, etc.


Damn Right I can Barely read Shakespear (dunno IF I spelled that right)
Jul 13 2001, 1:41 pm
In response to Air Mapster
On 7/13/01 5:38 pm Air Mapster wrote:
On 7/13/01 5:37 pm Nadrew wrote:
Isn't that also called Binary

Yup.

Thought so I tryed to learn that and nearly killed people after I got pissed at the people who tryed to teach me not long after I gave up and came here(and on the website part I switched to drag and drop)
Jul 13 2001, 1:45 pm
In response to Air Mapster
Thank you very much. I already had a basic understanding of binary, but that was a great recap and it gave me a better understanding of binary (along with all of the stuff I wanted to know =).
Jul 13 2001, 9:03 pm
In response to Nadrew
Isn't that also called Binary

It's also called base 2!