nesdev.org

Posted: **Tue Nov 27, 2007 12:47 pm**

Hi,
i've been reading a few documents, on and off line to help me understand bit-shifting and ANDing(masking really). it's not totaly clicking. not even simple stuff i try in windows calculator. will rodnay zaks' book "programming the 6502" help me to better understand this concept?
and why is is so important? when i look at source code, i'm seeing a lot of shifting and masking in important parts of the code. but i don't understand why it's necessary.

i guess i should be reading hacker's delight or something.....

Posted: **Tue Nov 27, 2007 1:13 pm**

Shifting and masking are useful for interacting with bit fields within a byte. For example, NES PPU attribute tables have four 2-bit fields in each byte.

Posted: **Tue Nov 27, 2007 3:55 pm**

ANDing, EORing and ORing are God-sent methods of bit manipulation.

If you want to clear bits within a byte, you AND the byte with a number that only includes the bits you want to keep. This is most useful in situations where the value of Data is unknown.

Data = ??;
Data &= 0x3C; <-- bits 0, 1 and 7 cleared (not matter if they were set or not)

If you want to flip (i.e. 1 becomes 0 or 0 becomes 1) bits within a byte you EOR the byte with a number that includes the bits you want to flip.

Data = 0xFF;
Data ^= 0x1F; <-- Data becomes 0xE0;

If you want to set bits within a byte, you OR the byte with a number that includes the bits you want to set. This is most useful in situations where the value of Data is unknown.

Data = ??;
Data |= 0x20; <-- bit 5 set (not matter if it was set or not)

*Phew*

Posted: **Tue Nov 27, 2007 6:10 pm**

Code: Select all

    ????????
AND 00010011
------------
    000?00??

    ????????
OR  00010011
------------
    ???1??11

    11001010
XOR 01100110
------------
    10101100

AND is useful for replacing unwanted bits with zeroes so they don't interfere. OR is good for putting things back together, as long as you know the two values have zero bits where the other one is. XOR is used more like ADC and SBC, for doing arithmetic.

Posted: **Tue Nov 27, 2007 6:14 pm**

You'll eventually feel the need to use them. Just wait until you start coding.

Posted: **Wed Nov 28, 2007 12:34 pm**

WedNESday wrote:ANDing, EORing and ORing are God-sent methods of bit manipulation.

If you want to clear bits within a byte, you AND the byte with a number that only includes the bits you want to keep. This is most useful in situations where the value of Data is unknown.

Data = ??;
Data &= 0x3C; <-- bits 0, 1 and 7 cleared (not matter if they were set or not)

If you want to flip (i.e. 1 becomes 0 or 0 becomes 1) bits within a byte you EOR the byte with a number that includes the bits you want to flip.

Data = 0xFF;
Data ^= 0x1F; <-- Data becomes 0xE0;

If you want to set bits within a byte, you OR the byte with a number that includes the bits you want to set. This is most useful in situations where the value of Data is unknown.

Data = ??;
Data |= 0x20; <-- bit 5 set (not matter if it was set or not)

*Phew*

thanks, this page is definately going to be bookmarked, heck i think i'm going to print it,

Data = ??;
Data &= 0x3C; <-- bits 0, 1 and 7 cleared (not matter if they were set or not)

windows calculator only shows six bits. is this calc.ex truncating the 0 at MSB?

Posted: **Wed Nov 28, 2007 1:26 pm**

Laserbeak43 wrote:windows calculator only shows six bits. is this calc.ex truncating the 0 at MSB?

I just tried it in Windows XP's calculator, and yes, it truncates leading zeroes from the displayed numerals.

Posted: **Wed Nov 28, 2007 2:02 pm**

tepples wrote:
Laserbeak43 wrote:windows calculator only shows six bits. is this calc.ex truncating the 0 at MSB?
I just tried it in Windows XP's calculator, and yes, it truncates leading zeroes from the displayed numerals.

thanks

Posted: **Wed Nov 28, 2007 3:20 pm**

Laserbeak43 wrote:thanks, this page is definately going to be bookmarked, heck i think i'm going to print it,

You're welcome. All of the other bits are uneffected, naturally. ORing is useful when changing Name Tables in your PPU code.

Posted: **Thu Nov 29, 2007 3:40 am**

If you need something for experimenting then this one is pretty nice AnalogX PCalc

Posted: **Thu Nov 29, 2007 6:45 am**

dXtr wrote:If you need something for experimenting then this one is pretty nice AnalogX PCalc

nice thanks a lot

Posted: **Thu Nov 29, 2007 10:24 am**

I don't think anyone has mentioned one of the most common uses of shifting+AND:

Left shifting mimics a multiply-by-2 operation. If you notice:

Code: Select all

$16 = 0001 0110
$2C = 0010 1100

$16 left shift 1 = $2C = $16 * 2

Therefore you can left shift once to multiply by 2, twice to multiply by 4, 3 times to multiply by 8, etc.

Right shifting works similarly, and mimics a divide-by-2 operation.

AND can also be used as a pseduo-modulous operation. That is, it can give you the remainder after a division:

9 mod 4 = 1
because
9/4 = 2 remainder 1

you can simulate this with AND by ANDing with the mod number-1. That above example would translate to:

9 AND 3 = 1 (3 is one less than the 4 you'd mod with)

but be sure note that this only works with power-of-two numbers. 2, 4, 8, 16, 32, etc. You cannot use AND to do a "mod 5" operation or something similar.

For a practical example -- let's say a game has a background animation routine. It will cycle through 4 different steps of animation, changing steps every 8 frames. To accomplish this, this routine makes use of a frame-counter... which is just a number in RAM that the game increments every frame:

Code: Select all

LDA frame_counter  ; load the frame counter

LSR A
LSR A
LSR A   ; divide it by 8 (we only want it to advance every 8 frames)

AND #$03  ; mod by 4

; A is now 0, 1, 2, or 3 -- indicating which frame of animation to use

Posted: **Thu Nov 29, 2007 3:52 pm**

wow! great sets of tutorials! it's all getting a bit clearer

Disch wrote: you can simulate this with AND by ANDing with the mod number-1. That above example would translate to:

9 AND 3 = 1 (3 is one less than the 4 you'd mod with)

so you're saying 3 is four? is that because to the asembler, 0 is 1 when counting?

Code: Select all

LDA frame_counter  ; load the frame counter

LSR A
LSR A
LSR A   ; divide it by 8 (we only want it to advance every 8 frames)

AND #$03  ; mod by 4

; A is now 0, 1, 2, or 3 -- indicating which frame of animation to use

nice! i'd like to try this out one day, when i finaly figure out how to assemble a rom!!
(i should be able to do it)

Posted: **Thu Nov 29, 2007 4:25 pm**

Laserbeak43 wrote:so you're saying 3 is four? is that because to the asembler, 0 is 1 when counting?

No. You use 3 instead of 4 because AND is not the same thing as Mod -- it just so happens that it has the same results when used this way. Look at the details of how this works:

Example:

$1D mod 8 = 5 which can be mimiced with:
$1D AND 7 = 5

why mod works:

Code: Select all

  $1D / 8 = 3 (rounded down)
  3 * 8 = $18
  ($1D - $18) = 5  <--- 5 is the remander after division

AND, however, works differently:

Code: Select all

  $1D = %0001 1101
  $07 = %0000 0111
  ----------------
  $05 = %0000 0101  <-- result of AND

Mod effectively returns a value of [0..n-1] (where n is the divisor). Ex: when dividing by 8, the highest remainder you can have is 7 (a remainder of 8 or higher would make no sense).

AND, however, returns a value of [0..n]. It is entirely possible to AND a number by N and get N back.

I must stress again, though, that AND can only be used in this way when you want to mod by a power-of-2 value. The reason for this is because there can't be "gaps" in the bits you're ANDing. For an example:

$17 mod $0A = $03
because:
$17 - (($17 / $0A) * $0A) = $03

however... $17 AND $09 = $01 !!!! because:

Code: Select all

  $17 = %0001 0111
  $09 = %0000 1001  <-- notice the "gap" of zeros
  -------------^^-
  $01 = %0000 0001  <-- result of AND

Posted: **Thu Nov 29, 2007 5:41 pm**

Think of the equivalent in decimal. You want to get the ones digit of a value. So you divide by 10 and take the remainder. Another way is to keep only the last digit.

1234 / 10 gives remainder of 4
0004 there's the 4

If you want to find the remainder after 100, keep the last 2 digits

1234 / 100 gives remainder of 34
0034 there's the 34

If you instead wanted the remainder after dividing by 9, you wouldn't be able to use this shortcut. So with base 10, you can use it only if your divisor is a power of 10. With base 2, you can use it only if your divisor is a power of 2.

nesdev.org

bit-shifting and ANDing(masking)

bit-shifting and ANDing(masking)