The Mugen Fighters Guild

Help => M.U.G.E.N Development Help => Tips, Tricks, Tutorials => Topic started by: Jesuszilla on December 15, 2011, 02:30:27 am

Title: Bitwise variables: Demystified
Post by: Jesuszilla on December 15, 2011, 02:30:27 am
So I'm sure some of you have seen this thread by Winane here (http://mugenguild.com/forumx/index.php?topic=24372.0) about bitwise shifting. If you were anything like me, you would have looked at this and gone, "what the fuck is this," and walked out. Rightfully so, I might add. This wasn't explained in the thread very well at all, so I decided to take it upon myself to do so.

To understand bitwise shifting, you must understand binary notation.

What the hell is binary notation?
Binary notation is a way of breaking down numbers into 0s and 1s. False or true. Off or on. Everything going on in your computer right now, when you get down to the most basic things, is nothing more than a series of switches that say "on" or "off." 1 for on, 0 for off.

An example of binary notation:

1001

That is 9 in binary notation. Why is this? Let's break this down into simpler terms (spaces are there for the sake of readability)

1 0 0 1
8 4 2 1

8 + 0 + 0 + 1 = 9

So, 16 in binary would be:
10000

So, 32 in binary would be what?

Spoiler, click to toggle visibilty

More at Wikipedia. (http://en.wikipedia.org/wiki/Binary_notation)

Now, if you haven't noticed already: powers of two will never cross over. This is the key to understanding...

What the hell is bitwise shifting?

In MUGEN, we are given two sets of variables to use: ints and floats. However, we are limited to 60 int variables (indices 0-59), and 40 float variables (indices 0-39). Unfortunately, this means we end up wasting a lot of those variables for simple things that we want to either be 0 or 1.... hmmmmm!

Well, we could just relocate a lot of those to just one variable! If it's just a 0 or 1, then it's a boolean. It's on or off. We can use bitwise shifting on ONE variable to handle up to 30 booleans! Wow!

So how do I do it?
There are a number of ways. If you know your powers of two, you should be fine with:
[State -2, Powers of Two]
type = VarAdd
trigger1 = !(Var(4)&1)
var(4) = 1
[State -2, Powers of Two]
type = VarAdd
trigger1 = !(Var(4)&2)
var(4) = 2
[State -2, Powers of Two]
type = VarAdd
trigger1 = !(Var(4)&4)
var(4) = 4

[State -2, Test]
type = PlaySnd
trigger1 = (Var(4)&2)>0
value = S11,0

That is, if you are going to make use of ALL 30 slots, you can store up to var(x)&1073741824.

Alternative notation:
[State -2, Exponentiation]
type = VarAdd
trigger1 = !(Var(4)&2**0)
var(4) = 2**0
[State -2, Exponentiation]
type = VarAdd
trigger1 = !(Var(4)&2**1)
var(4) = 2**1
[State -2, Exponentiation]
type = VarAdd
trigger1 = !(Var(4)&2**2)
var(4) = 2**2

[State -2, Test]
type = PlaySnd
trigger1 = (Var(4)&2**1)>0
value = S11,0

Example of how to use this with the assignment operator:
;---------------------
; N-Groove
[State -2, VarSet]
type = Null
triggerall =  Var(20) = 5 && (RoundState = [1,2])
trigger1 = e|| (var(5) :=   (var(5)|2*1)) ; 0 = Dash, 1 = Run
trigger1 = e|| (var(5) :=   (var(5)|4*0)) ; Just Defend
trigger1 = e|| (var(5) :=   (var(5)|8*0)) ; Parry
trigger1 = e|| (var(5) :=  (var(5)|16*0)) ; Super Combo Cancel
trigger1 = e|| (var(5) :=  (var(5)|32*1)) ; Counter Attack
trigger1 = e|| (var(5) :=  (var(5)|64*1)) ; Counter Movement
trigger1 = e|| (var(5) := (var(5)|128*1)) ; Safe Fall
trigger1 = e|| (var(5) := (var(5)|256*0)) ; Air Guard
trigger1 = e|| (var(6) := 1)              ; Small Jump
trigger1 = e|| (var(9) := 1)              ; 1 = Roll, 2 = Dodge, 3 = Neither
trigger1 = e||(var(10) := 5)              ; 1 = C-Gauge, 2 = A-Gauge, 3 = P-Gauge
                                          ; 4 = S-Gauge, 5 = N-Gauge, 6 = K-Gauge
persistent = 1

How the hell does it work?
Recall once again how binary notation is.

0001 = 1
0010 = 2
0100 = 4
1000 = 8

The way this works is how I said at the end of the first section: powers of two never cross over! Simple as that!


Hope this helps a lot of you out!
Title: Re: Bitwise shifting: Demystified
Post by: VirtuallTek on December 16, 2011, 01:08:02 am
Yeah, we generally call it Bit flags.
But 30 booleans? MUGEN doesn't uses 32-bit integers?

Bit manipulation is a very interesting thing. Bit flags is the basic usage of it.
I posted an explanation in another forum about the use of bit-wise operators to store more than one number in one var.
It's a more advanced usage, but is simple at all.

You explained about binary notation, then we can notice that some range of values needs a certain amount of bits to be represented.
Eg.: 0 to 255 needs 8-bits (1 byte).

How I can store more than one value of this range in one var?

Here we will store 3 values of 8 bits each (can be a RGB color or anything you want), and I assume that MUGEN uses 32-bit integers.

Setting one value at a time

First value - var(x) := (var(x) & 4294967040) | value
Second value - var(x) := (var(x) & 4294902015) | (value * 256)
Third value - var(x) := (var(x) & 4278255615) | (value * 65536)

Setting all values at the same time

var(x) := (value1) | (value2 * 256) | (value3 * 35536)

Getting the value

First value - var(x) & 255
Second value - (var(x) & 65280) / 256
Third value - (var(x) & 16711680) / 65536

Why it works?

First, we use the operator & to reset to 0 the bits to be set (or capture all other bits, is the same anyways :P):
Eg.: We want to set the value at bits 8-15, then var(x) := var(x) & 4294967040
4294902015 = 11111111 11111111 00000000 11111111
Understood? We define as 0 all bits we want to discard and to 1 all bits we want to keep.

Then, we set the desired value to the right place using this formula:
value * (2**((target_index - 1) * value_bit_count))
Eg.: target index = 2 (second value)
value * (2**((2-1) * 8)) = value * 256

Simple, no?

Complementing your explanation

Setting a flag: var(x):= var(x) | 4 ;third flag is set to true
Resetting a flag: var(x):= var(x) & ~4 ;third flag is set to false
Checking a flag: var(x) & 4 ;return true if the third flas is true
Checking a flag 2: !(var(x) & 4) ;return true if the third flag is false

Congratulations, nice initiative and great explanation!
Title: Re: Bitwise shifting: Demystified
Post by: Jesuszilla on December 16, 2011, 01:26:40 am
Yes, while it can store a value up to 2147483647, 30 is due to the fact that if you add every value of 2n from n=0 to n=30, it will add up to be 231-1, which is the value of MUGEN'S INT_MAX.

Automated test:
[State -2, Exponentiation]
type = VarAdd
trigger1 = var(6) < 30
var(6) = 1
[State -2, Exponentiation (tick fix)]
type = VarAdd
trigger1 = !(Var(4)&2**0)
var(4) = 2**0
[State -2, Exponentiation]
type = VarAdd
trigger1 = !(Var(4)&2**var(6))
var(4) = 2**var(6)
Title: Re: Bitwise shifting: Demystified
Post by: VirtuallTek on December 16, 2011, 11:59:34 am
And the negative values?
Title: Re: Bitwise shifting: Demystified
Post by: Jesuszilla on December 16, 2011, 11:56:44 pm
What about them? :P

I guess I should also mention in case it wasn't obvious: to reset, you just subtract the value instead of add.

EX:
[State -2, Powers of Two]
type = VarAdd
triggerall = (Var(4)&4)>0
trigger1 = !Time
var(4) = -4
[State -2, Exponentiation]
type = VarAdd
triggerall = (Var(4)&2**2)>0
trigger1 = !Time
var(4) = -2**2

Because of this, we can't really make use of the negative values in the shifting.
Title: Re: Bitwise shifting: Demystified
Post by: VirtuallTek on December 17, 2011, 05:52:04 pm
No, I'm still talking about the 30 booleans, not the shifting.  :)

If MUGEN uses signed integers and the maximum unsigned value is 2147483647, you can use 31 bits as boolean values and the last using -2147483648  ;D
Title: Re: Bitwise shifting: Demystified
Post by: felineki on December 17, 2011, 10:16:54 pm
I noticed that Darkstalkers uses bit flags within one byte in the character RAM to keep track of which normal attacks you have used during a jump (each can only be used once per jump) and had been wondering if there was some way to do the same thing in Mugen in order to cut down on the amount of variables used. Looks like this might come in handy for that.