Advanced Uses of Bitwise Operations

Page: 1 2
ID:160914
 
Jul 11 2008, 5:44 am
I've seen Popisfizzy use bitwise operations a lot and I only understood like 10% of the code he posted. So far, I got the hang of & and |, but now I want to know more about >>, <<, ^, and others that I missed out. I want to know when the operators that I specified would be very useful.
Jul 11 2008, 6:13 am
The first article I read about bit operation and it even explains about the ones you want to know about!

http://www.byond.com/members/ DreamMakers?command=view_post&post=39760

and << are bit shifters, per say, shift the number in the direction you posted - any number not there previousy will be placed with 0s.

Ex:
101 << 2 would return "10100"
10100 >> 2 = 101

You can think ^ as a toggle operator:

6 (1010) ^ 2 (10) = 4 (1000) ^ 2 (10) = 6 (1010) ^ 4 (1000) = 2 (10) ... etc

... Either ways, read the article, it explains a bit more clearly then what I tried to explain >_>
Jul 11 2008, 6:26 am
In response to GhostAnime
Thanks, but I was looking for applications. It would be really nice if I got a scenario in actual programming in which it could be used.
Jul 11 2008, 10:22 am
In response to Kakashi24142
Do a search around - BYOND (and the internet generally) has many tutorials on these.

Kakashi24142 wrote:
It would be really nice if I got a scenario in actual programming in which it could be used.

Basically, bit flags are used to efficiently combine multiple boolean flags* in a single value (and variable). A quick example would be, in implementing an admin system: 
client/var
   worldsay_muted
   muted
   jailed

//extra:
admin/verb/be_mean_to(mob/M)
  M.client.muted = 1
  M.client.worldsay_muted = 1
  M.client.jailed = 1


This example can be done much more cleanly, in a single variable, using bit flags: 
client/var
   pun_status //short for punishment status

//extra:

//#defines are used to make using the numbers clearer. look those up if you don't know about them

#define MUTED 1
#define WSMUTED 2
#define JAILED 4

admin/verb/be_mean_to(mob/M)
  M.client.pun_status |= (MUTED|WSMUTED|JAILED) //turn on multiple flags in that value


*: This means a flag that represents an on/off value, meaning eg 1 or 0.

Well, I've also used bit flags in multiple code examples throughout the forum, this seems to be what you want, I'll link to some more: [link], [link] ID:598223
Jul 11 2008, 3:22 pm
In response to Kaioken
Yea I'm aware of using the & and | and I use it quite a lot, but I was wondering what >>, <<, and ^ can be used for.
Jul 11 2008, 4:47 pm (Edited on Jul 11 2008, 5:27 pm)
Until I get bored, I'm working on a Pokemon game. In this game, like the actual games, there are EVs (Effort Values). When you defeat another Pokemon, you get one or two EVs on up to two values. I'm able to store up to three sets of data for EVs on one field, two bytes, with a single bit leftover.

The way it works is like this:
/*
V - The parts for the value being stored.
E - The EV flag area for storage.
*/
0EEE VVEE EVVE EEVV //Two-byte field, which is what BYOND
                    //uses.

This works because the numbers 0, 1, 2, and 3 only take up, at most, two bits (00, 01, 10, and 11). For the EV's, I use three bits, meaning I can have up to 7 stored. Each set of data takes up a total of five bits.
/*
As stated and shown above, each of these flags takes up, at
most, three bits. Coming from the right-most bit in the
field, those bits are the third, fourth, and fifth bits.
*/
#define EV_HP       4  //1 << 2
#define EV_ATTACK   8  //2 << 2
#define EV_DEFENSE  12 //3 << 2
#define EV_SPEED    16 //4 << 2
#define EV_SP_ATK   20 //5 << 2
#define EV_SP_DEF   24 //6 << 2

/*
To store them, I check to see how many there are. If there
is just one, I store it in the first five bits. If there are
two sets of data, I store the first in the first five bits,
then bitshift the second by five, storing it in the next
five bits. If there are three, then I do the same as above,
but bitshift the third by ten, storing it in the third set
of five bits.
*/
#define one_ev(e, s)                ((e) | (s))
#define two_ev(e, s, f, t)          (((e) | (s)) | (((f) | (t)) << 5))
#define three_ev(e, s, f, t, g, u)      (((e) | (s)) | (((f) | (t)) << 5) | (((g) | (u)) << 10))

/*
To get the first set of data, no bitshifting is needed.
Just binary and by three (0011) to get the first piece (the
value to give) of the first set. To get the EV data, I
binary and by 28 (0001 1100).
*/
#define first_ev_value(x)           ((x) & 3)
#define first_ev_stat(x)            ((x) & 28)
//To get the second set, I bitshift to the right by 5 and
//do the same as above.
#define second_ev_value(x)          (((x) >> 5) & 3)
#define second_ev_stat(x)           (((x) >> 5) & 28)
//Once again, same as above, but bitshift right by 10.
#define third_ev_value(x)           (((x) >> 10) & 3)
#define third_ev_stat(x)            (((x) >> 10) & 28)
Jul 11 2008, 5:23 pm
In response to Popisfizzy
Popisfizzy wrote:
Until I get bored, I'm working on a Pokemon game. In this game, like the actual games, there are EVs (Effort Values). When you defeat another Pokemon, you get one or two EVs on up to two values. I'm able to store up to three sets of data for EVs on one field, two bytes, with a single bit leftover.

If you program EVs, you will be my hero. If you program the IV, DV and breeding systems you will be my god.
Jul 11 2008, 5:25 pm
In response to Hiro the Dragon King
IVs and DVs are, as far as I can tell, the same thing (at least they are according to Bulbapedia), but none of the stuff you just mentioned is difficult. It's just a matter of how long it takes me to get bored and move on, which I estimate will be next week.
Jul 11 2008, 5:43 pm
In response to Popisfizzy
Popisfizzy wrote:
IVs and DVs are, as far as I can tell, the same thing (at least they are according to Bulbapedia), but none of the stuff you just mentioned is difficult. It's just a matter of how long it takes me to get bored and move on, which I estimate will be next week.

The difficulty wasn't what I was referring to. The patience is. I never would have the patience.

P.S. I am not done with it, but if you want it, I started mapping the Johto region in DM using the R/S/E/FR/LG sprites. I'll probably never do anything with it.
Jul 11 2008, 6:10 pm
In response to GhostAnime
The more I learn about bitwise operations...

...the more I hate them and are confused by them.

I'm too lazy to actually think. :(
Jul 11 2008, 6:17 pm
In response to Hiro the Dragon King
This isn't really the place for it, so this is my last reply on the matter, but I'm not making a straight port of any of the games, and I plan on making a new map for a bit more freedom is making things for players to do. Thank you for the offer, but it won't be helpful for what I'm doing.
Jul 11 2008, 7:06 pm
In response to GhostAnime
GhostAnime wrote:
The first article I read about bit operation and it even explains about the ones you want to know about!

I've gone through that article, and like many other people, it just doesn't make sense to me. I think what would be more useful is something along the lines of ZBT - a step by step tutorial for creating your own bitwise operations.

That way, you can program a little bit of code that you don't understand at all, and observe the results, Then you can change the code a little bit, and observe the results, and continue that process. Some people, me included, grasp things much more easily that way (through hands-on interaction) than from just reading an article explaining it.
Jul 11 2008, 7:12 pm
In response to Kakashi24142
Kakashi24142 wrote:
Yea I'm aware of using the & and | and I use it quite a lot, but I was wondering what >>, <<, and ^ can be used for.

<< and >> are shift operators.

Some of their more common uses are for quick multiplication and division (respectively) by powers of 2. The expression (1 << 1) returns 2 (1 * 21); (1 << 2) returns 4 (1 * 22). Inversely, (2 >> 1) returns 1, as does (4 >> 2). These methods of multiplication and division are faster than the normal arithmetic operators, but you must consider that bitwise operators operate on a 16-bit field, as well as the fact that they operate on integers (rounding down in the case of division).

They are also useful, say, if you want to store multiple smaller numbers in a single variable. In BYOND, for bitwise operations, you get a 16-bit field for bitwise operations (as mentioned previously). So if you wanted to store two 8-bit integers (8-bit unsigned integers have a range of 0-255), you could shift one number over 8 bits to the left, and combine them with the bitwise OR operator to form a single 16-bit number. Something like:
var/a = 16
var/b = 200
var/c = (a << 8) | b

proc/GetAFromC()
    return (c >> 8)

proc/GetBFromC()
    return (c & 0xFF)    // Same as (c & 255)


As for a practical use of these shifts and other bitwise operators, I used them extensively in hub://hiead.base64, if you want to snoop around the code a bit. (Disclaimer: I am not responsible if your eyes spontaneously combust from viewing the code).

The XOR operator (^) is used to compare the bits of two operands and return the comparison in the form of a resultant number, which has bits that are 1 for areas where the two operands' bits were different, and 0 if they were the same. Basically, the number it produces has a "1" bit only in places where the compared numbers' corresponding bits differ. There are many uses of this, but I'll give a (very short and incomplete) list here:
  • XOR can quickly swap two numbers. For example, consider the following: 
    var/a = 16
    var/b = 212

    client/verb
        
        SwapNormal()
            src << "Before swap: a=[a], b=[b]"
            
            var/temp = a    // We have to create an extra variable
            a = b
            b = temp
            
            src << "After swap: a=[a], b=[b]<hr>"
        
        SwapXOR()
            src << "Before swap: a=[a], b=[b]"
            
            a ^= b
            b ^= a
            a ^= b
            
            src << "After swap: a=[a], b=[b]<hr>"
  • XOR can quickly set a number to 0. In some processor architectures, XORing a number to 0 can be faster than setting a number to 0 (I'm not sure if there is any claim to this in DM). In any case, given the variable myVar, it can be set to 0 with this statement: myVar ^= myVar
  • XOR is used in many hashing and encryption algorithms. Look them up in your own time.
Jul 11 2008, 7:32 pm
In response to Foomer
Foomer wrote:
I've gone through that article, and like many other people, it just doesn't make sense to me. I think what would be more useful is something along the lines of ZBT - a step by step tutorial for creating your own bitwise operations.

I don't know about any ZBT-like articles on bitwise operators, but I would like to take the chance to point you to the article that kick-started my bitwise knowledge (perhaps in conjunction with Wikipedia). Check out Wizkidd0123's Hello, Operator? (This next link has Hello, Operator? in its original, semi-extinct context).
Jul 11 2008, 10:18 pm (Edited on Jul 11 2008, 10:24 pm)
Consider this usage, which will loop through all directions.
verb/Spin()//Not exactly a spin
    for(var/NS=0,NS<=NORTH,D++)//since SOUTH and NORTH are 1 and 2 just adding
        for(var/EW=0,EW<=WEST,EW<<=1)
            if(NS|EW)
                usr.dir=NS|EW
                sleep(1)
            if(!EW) EW=EAST>>1
Nothing fancy, but it's an example, and I'm sure it'll look weird in-game. (Not the best usage, probably didn't even need to use bit shifting here.) I like the idea of storing multiple values in one variable by bit shifting. (Usage of it.)

On another note, here's an example I thought of for choosing a random direction:
mob/Move(L,D,var/allow=0)
    //mobs are all mentally incapacitated/disoriented
    //so, they always move in a random direction (of the 8)
    if(allow) return ..()
    .=0
    var/r=rand(-1,1)
    var/EW=r>=0 ? EAST<<r : 0
    if(EW) r=rand(-1,1)//save processing power
    var/NS=EW ? (r>=0 ? SOUTH<<r : 0) : SOUTH<<rand(0,1)
    spawn() src.Move(get_step(src,NS|EW),,1)
That simplifies it down, instead of randomly choosing from a list or something else.
Jul 12 2008, 5:14 am (Edited on Jul 12 2008, 11:49 am)
In response to Naokohiro
Thanks everyone for the help. If there are any more tips anyone can give me, go ahead and post.

EDIT:
WOW! I experimented and read a few articles on google on bitwise operations and I finally understand how useful the shift operators are :D! I'll make an article on this as soon as I'm sure I have a good understanding.

2nd EDIT:
After I though about it, the easiest way to get a random dir is like so:
var/dir=(1 << rand(0,3))
dir|=((dir>>2)? (1 << rand(0,2)) : (1 << pick(0,2,3)))
Jul 12 2008, 11:57 am
In response to Kakashi24142
Kakashi24142 wrote:
2nd EDIT:
After I though about it, the easiest way to get a random dir is like so:
var/dir=(1 << rand(0,3))
dir|=((dir>>2)? (1 << rand(0,2)) : (1 << pick(0,2,3)))
You made a couple errors.
var/dir=(1 << rand(0,3))
dir|=((dir>>2) ? (1 << pick(0,2)) : (1 << pick(0,2,3)))
You put rand where you should've put pick on that second line.
Jul 12 2008, 12:59 pm
In response to Naokohiro
Actually, we're both wrong, it's like this:
var/dir=(1 << rand(0,3))
dir|=((dir>>2) ? pick((1 << pick(0,1),0) : pick((1 << pick(2,3)),0))
Jul 12 2008, 3:35 pm
In response to Kakashi24142
As you're getting a random direction, not caring whether it's cardinal or orthogonal, the following will work just as well, with a bit less code:
proc/rand_dir()
    return (1 << rand(0, 3)) | (1 << rand(0, 3))

The possibility of overlapping bits is irrelevant, as it is simply a random direction.
Jul 12 2008, 4:00 pm
In response to Popisfizzy
Oh, I would've had mine like yours had I not considered that fact of overlapping (like NORTH | SOUTH or EAST | WEST). And what does happen if the dir var is set to an unsupported value? Will the persons simple not move at all? For my game, it would screwy since I use a custom movement system.
Page: 1 2