RE: Least significant bit?

["Paul Robson" <probson@powerup.com.au>]

Ender, great summary, but just in case some people were slightly confused, i
think you have a slight mistake in your explanation of option 3:

> So, if
> you were to use an AND mask on the binary numbers 10101010B and
> 11110000B, you would get 10100101B.

The answer should be 10100000B shouldn't it?

you would get 10100101B is you did an AND on the first five bits and NOT XOR
on the remaining three bits :D

Paul Robson



> -----Original Message-----
> From: gameprogrammer-owner@gameprogrammer.com
> [mailto:gameprogrammer-owner@gameprogrammer.com]On Behalf Of
> EnderWiggenRules@aol.com
> Sent: Thursday, 27 July 2000 10:02 AM
> To: gameprogrammer@gameprogrammer.com
> Subject: Re: Least significant bit?
>
>
> OK, I've seen three different methods shown. I'd like to say the
> advantages and disadvantages of each:
>
> 1. Use a modulus command ( the infamous %). In many compilers
> (not ALL, but I won't explain why, bother me about it in another
> e-mail) the modulus character returns the remainder of two
> numbers divided by each other. For example, 5 % 3 = 2, because
> the remainder of 5 / 3 is 2. You can use (N % 2) to determine if
> N is even or odd. If the result is 0, there is no remainder,
> hence, N is even. If the result is 1, the number does not divide
> evenly into two, therefore N is odd. This approach works fine,
> but is slow on most computers. Why? Well, in order to find out
> the remainder, the compiler has to divide the two numbers. What's
> wrong with that? On many compulers, the divide assembler command
> (DIV/IDIV/etc.) is SLOW. In game programming especially, you want
> to avoid divisions at all costs. However, there is an advantage
> to this - it works with float/double numbers. The other two
> approaches will not.
>
> 2. Use a bit shift ("<<", ">>", "SHL", "SHR", etc.). Basically,
> this method works because if you convert your number to binary
> format, the last bit can tell you whether or not your number is
> even/odd. If the last bit is 0, it's even. If the last bit is 1,
> it's odd. Basically, you need to test the last bit. Using a bit
> shift is one possible way to do this. In this approach, you shift
> your number to the left to cancel out all the other bits, then
> back right to test the bit. So, with 8-bit numbers, you would do
> something like ((N<<7)>>7) to isolate the last bit, then test to
> see if it is 0 or 1. There is an optimization to this - I'll get
> to that later. This approach is much faster than the above.
> However, it only works with integers, simply because float/double
> numbers don't treat their bits the same way.
>
> 3. The third approach is to use an AND mask ("&") to test the
> last bit. An AND mask isolates all the different bits between two
> numbers and compares them. If the two corresponding bits in those
> two numbers match, then AND produces a 1 in the corresponding bit
> place in the result. Any other case and it produces a 0. So, if
> you were to use an AND mask on the binary numbers 10101010B and
> 11110000B, you would get 10100101B. This can be put to our
> advantage, for it also tests bits. Let's say you want to test the
> least significant bit (which we do) of the binary number
> 10110101B. If you AND the number with 00000001B, you get 1 as a
> result. Basically, you have just tested the last bit. If the last
> bit is 1 and you AND it with 1, you get 1. If the last bit is 0
> and you AND it with 0, you get 0. But wait, if the last bit is 0,
> you have an even number. Also, if the last bit is 1, you have an
> odd number. This is how AND testing works. If (N&1) is true, you
> have an even number. If it's fa!
> lse, you have an odd. Again, this is faster than modulus testing,
> but doesn't work with float/double numbers.
>
> *4. This is an optimization for method 2. In that method, you
> shifted the bits left to cancel out all the other bits and then
> shifted the bits back again to test. What if you could test the
> bits in their shifted form (or, to put another way, didn't need
> to shift the bits back)? Why would you waste precious cycles
> shifting the dumb bit back when you can test it yourself? Easy
> answer to that - you don't. How? Here: OK, you have a number
> 10101011B, and you want to see if it's even or odd. You shift the
> bits 7 to the left so you end up with 10000000B. According to
> method 2, you would shift the bits back so you would have
> 00000001B and test to see if it is 0 or 1. You don't need to
> though. OK, you have 10000000B, right? And you know the original
> number (10101011B) is odd, right? So why bother shifting back? If
> the MOST significant bit (the left-most) is 1, you have an odd
> number. But why even bother with that test? If, after the
> shifting left, the number is 00000000B, you have an e!
> ven number! So here's the test. If (N<<7) is 0 (N=8-bit number),
> you have an even number. Otherwise, you have an odd number.
>
> Got it? OK. Now... which is faster, 3 or 4? Sorry to tell you
> this, but it's different every single time you code it! (Never
> trust the cycle counts printed in those little books - they only
> tell you the minimum amount of time (usually) it takes to execute
> an instruction). You have to try both cases and time it. But
> these are the methods I have seen in this thread, and I wanted to
> put it all into a nice summary. Just avoid method 1 at all costs,
> unless you're using decimal numbers.
>
> -Ender Wiggin
> =================================================================
> The GameProgrammer.Com mailing list is for the open discussion
> of any topic related to the art, science, and business of
> programming games. This list is especially tolerant of beginners.
> We were all beginners once
>
> To SUBSCRIBE or UNSUBSCꫨ please visit:
> http://gameprogrammer.com/mailinglist.html
>

=================================================================
The GameProgrammer.Com mailing list is for the open discussion
of any topic related to the art, science, and business of
programming games. This list is especially tolerant of beginners.
We were all beginners once

To SUBSCRIBE or UNSUBSCꫨ please visit:
http://gameprogrammer.com/mailinglist.html