gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Beginners > Noob : Bit masking/shifting

#11253 - goro - Tue Sep 30, 2003 8:53 am

Hi,

I'm trying to "wait for n frames" before updating my sprite animation.
(my main character has 6 frames in his walk.)

I have implemented a global timing system that uses vblanks. it has a global "counter",
"frames" and "seconds".

I know the gba is slow at division and a workaround is bit-masking or shifting. something like:-

Code:
bg1.mapData[y * 32 + ((bg1.x_scroll>>3) & 31)]
         =  temp[y * 256 + (bg1.x_scroll>>3)];
I know this code is for scrolling bg's but I think I'm trying to understand the >>3
part.

Please help using simple comparisons to everyday objects such as bread
because I'm a newbie!!

Never mind - I just learned about it -

A shift-right effectively divides a number by 2 and a shift-left multiplies it by two.

ie
Code:

x=7;            // 00000111     value of x is 7
x=x<<1;      // 00001110     value of x is 14


The bitwise number is shifted left and a 0 comes in from the right.

Now to understand how the & part works...

#11255 - yaustar - Tue Sep 30, 2003 11:26 am

& is bitwise AND
| is bitwise OR

Don't know if I can explain this clearly, but I give it a shot

0010 & 0111 = 0010
0110 & 0100 = 0100

& isolates the bits that are the same

0101 | 0111 = 0010
0100 | 0100 = 0000

| isolates the bits that are not the same

Someone correct me if I am wrong
_________________
[Blog] [Portfolio]

#11257 - NoMis - Tue Sep 30, 2003 1:59 pm

& isolates the bits that are the same

0101 | 0111 = 0010
0100 | 0100 = 0000

you made a littel mistake yaustar.

What you showed up there is the exlusive or (^).


The bitwise or operator would produce a result as the following

0101 | 0111 = 0111
0100 | 0100 = 0100

So you must have a bit at least at one of the numbers set to have the coresponding bits in the result.

Here is a table for this

Bitwise OR |

--- 0 | 1
-------------
0 | 0 1
1 | 1 1

Bitwise AND &

--- 0 | 1
-------------
0 | 0 0
1 | 0 1

Bitwise XOR ^

--- 0 | 1
-------------
0 | 0 1
1 | 1 0


The bitwise shifting operatior simply shifting the bits to the left or to the right as far as the number specified behind the operator

011001000 >> 2 = 000110010

When shifting 1 bit to the right it's a division by 2
When shifting 1 bit to the left it's a multiplication by 2

This calculation are 3 times faster than normal calculations (as i remember)



NoMis

#11259 - yaustar - Tue Sep 30, 2003 2:44 pm

Thanks for clearing that up, always had a problem with sets in Maths :p
_________________
[Blog] [Portfolio]

#11261 - poslundc - Tue Sep 30, 2003 2:47 pm

goro wrote:
Now to understand how the & part works...


In the bit of code you supplied, & 31 is effectively the same as saying % 32, ie. modulus 32.

What this means is that if your background scroll value gets bigger than 32, it will be automatically brought back down to zero.

In other words:

0 % 32 == 0
1 % 32 == 1
...
31 % 32 == 31
32 % 32 == 0
33 % 32 == 1
etc.

Modulus is extremely useful in general C programming; however, it is dirt slow on the GBA (because it has no hardware divide). The & (modvalue-1) trick is good for getting the same result when you are taking the modulus of a power of two (such as 32 == 2 ^ 5).

Others have already explained what the & operator does; I'll throw in a quick explanation as well in case you haven't had enough:

& (aka bitwise AND) lets you mask the bits of a number, so that only the bits you want will show through into the result.

Every single bit of the number in question is compared with every corresponding bit of the mask, and then the bit that results is determined by the following table:

Code:

Input Bit  |  Mask Bit  |  Output Bit
-----------+------------+------------
     0     |     0      |      0
     0     |     1      |      0
     1     |     0      |      0
     1     |     1      |      1


In other words, the resultant bit will only be a 1 if both the input bit and the bit in your mask are both 1's.

In the case of your example, 31d = 0000 0000 0001 1111b.

If you were to apply this mask to any other number, all of the bits except for the bottom five would be changed to zero. As a result, any number greater than 31 would disappear, except for the remainder when divided by 32, which is what you want from modulus.

Hope this helps,

Dan.