Re: Least significant bit?

[EnderWiggenRules@aol.com]

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