Even or Odd Number
BlitzMax Forums/BlitzMax Programming/Even or Odd Number
| ||
| What's the quickest way to determine whether a number is even or odd? |
| ||
| Check the first bit in binary...i.e. logically AND it with 1 Odd AND 1 = 1 Even AND 1 = 0 |
| ||
| logically AND it with 1 Use bitwise AND, not logic AND. odd & 1 = 1 even & 1 = 0 |
| ||
| Been working with logic chips a lot recently and there is only logic AND...my mistake >.< . |
| ||
That depends on how the number is stored internally. A more generic way is to use the Mod operator, which returns the remainder after a division. Any number divided by 2 will give a remainder of 0 if it is even, yes?Function IsEven:Int(number:Int) Return (number Mod 2) = 0 End Function |
| ||
| mod is a lot slower than the bitwise operation on any computer. The processor divides and returns the remainder. |
| ||
| That's true but I find it highly unlikely that "Mod" is going to be the bottleneck in a real-world non-number-crunching program. |
| ||
| I am sure you know its very likely to help in contributing to the bottleneck and knowing that will definitely help. |
| ||
| That's not my understanding of a bottleneck. A bottleneck is where one thing is slowing down the whole program. When one thing is slowing down everything else, it doesn't matter how fast or slow the other things are - it makes no difference. If using Mod to determine if a number is odd or even is the bottleneck in your program, there is something very wrong in your code. |
| ||
| if you say so. |
| ||
| After bringing my program from 5 frames a second to more than a hundred on several occasions, I do say so. These are due to powerful optimizations to very specific parts of code - the parts that cause the bottle neck. My game went from supporting a few dozen simultanious units to now supporting several hundred smoothly. The reason it went so slowly is because I am using deterministic calculations which are always the same on every computer - something floats do not guarantee. The first method was woefully inefficient, but after several attempts it is now very efficient. The saying goes, your program spends 80% of its time in 20% of the code. Optimize only what you have to or you will be doing it all year. For scientific number crunchers every millisecond counts but consider a game. Humans cannot perceive more than about 30 frames per second of updating (that's generous, even 20 is still smooth). That gives 33 milliseconds per frame to update the logic. A big complicated function that updates lots of things and takes up 10 milliseconds is something that could definately become a bottleneck. But using Mod instead of the bit check? In a game I'd say that uses up considerably LESS than 1 millisecond of time, virtually immeasurable, unless you were doing something really out of the ordinary. It just doesn't matter so long as your frame is completed within 33 milliseconds - 31 milliseconds or 5 milliseconds a frame, both are the same. If it goes over 33, then just optimise the slowest part of your code to bring it under 33 again. Getting your game finished is more important than a 200fps demo. |
| ||
| I agree with everything Czar said. Apart from the conclusion, Im afraid Im with Jesse here. Whats the point in using a method you know to be slower? ATM you are not going to be the only app/game using the system and making any part of your code less than optimal seems pointless. Having said that I know ppl who thing ease of following the program to be more important than speed, I dont think that would apply here tho. |
| ||
| My dislike of the bitwise method is that it depends on the computer's architecture. It might work fine on your computer, or most people's computers, but one day you might be programming on a new architecture and it doesn't work and you don't know why. The Mod method will always work. |
| ||
| "Might" ? Dud mod is Implemented by the compiler "SHR/SAR" and "SHL/SAL" are implemented in to the processor architecture. who is to say that either one wont be discontinued or eliminated from either or both. from day one that I program and every language I know of has a type of mod and bit shift operation implemented and I have been programming for probably as long as you have been alive. I believe it's a lot more likely that a compiler won't have a mod "function" than the processor not have a bit shift operator.Bit shifts are part of and heavily used in low level programming. I believe that to be the worst excuse I have ever read. No disrespect intended. |
| ||
| I think by not "work" Czar means that it might not give you the expected result. e.g. on a PPC and 68k based systems where the data is stored in reverse order from an x86 architecture (this is one historical reason why PC apps were hard to port to Macs back in the day, as there was also a lot more ASM level code and other things that were highly architecture dependent due to speed). And I don't know the storage order for ARM but if you're developing for anything other than desktop these days you're going to likely run into that... If you want your code to be as portable as possible keep it in the language and off the hardware. If the language magically misses the feature you can code around it, or find an alternative. If the hardware doesn't behave as expected you're going to tear your hair out until you remember "oh yea! that's byte order dependent!" However if you're not planning on supporting other base architectures with the same code down the road then the closer to the hardware you get the better for both optimization and code simplicity (imo). I have times where I would use both. e.g. Writing an app that is likely to jump languages and probably platforms as well and it's not speed dependent such as loading, I would go with a compiler level approach. Something that's going to stick to one platform or for code that will make a difference from a millisecond boost in speed due to looping etc. I would go bitwise. If I was unsure I would go the fast route and leave a comment in the code that it's byte order dependent to same myself correction time later if needed. my 2c |
| ||
| Probably I'm being too cautious, but like ima says I was refering to the way that an integer might be stored on the computer, not whether bitwise operations themselves will change. Mod will always work in the same way as it's defined by the language to return the remainder after a division, regardless of binary representation. Bitwise tricks might not always work the way you expect however, if the way an integer is represented in the computer changes. Bitwise tricks are highly addictive, so be careful you don't become dependant on them, because it might bite you in the backside when you suddenly find yourself on a different architecture. |
| ||
| Please correct me if I'm wrong, but since when do bitwise operators in BlitzMax or C matter when dealing with normal datatypes, like Integer, regardless of how they are stored internally by the CPU system? Isn't this the responsibility of the compiler? What I can find of the current ANSI standard defines that the bitwise AND operator will AND each prealigned bit between to like operators. Which I interpret to mean that no matter how the CPU stores the binary representation of a integer any AND operator will result in the same answer no matter where the code is compiled. --------------------------------------------------------- Brucey is one of the experts on this subject, he'd know the real answer straight off!!!! :D Mark would be able to answer this pretty quickly as well. Hahah. --------------------------------------------------------- Now, if the compiler is NOT taking care of the this then the following code will result in different values depending on what system it is compiled and ran on: SuperStrict Function ReadBit:Long(x:Long, bit:Long) 'Return(0/1) of specific bit(0-63) in value(x) Return (x Shr bit) & 1 End Function Local a:Long=1152921504606846977:Long Print a Print readbit(a,0) Print readbit(a,60) Can someone with access to PPC MAC compile this code and post if they find any difference in the output from a standard 32-bit x86? (Output should be: 1152921504606846977 1 1 -------------------------------------------------------------------------------------- Ok, enough of the sillyness, here is simple code that can very easily be modified to work in probably any programming language regardless of CPU architecture. Local a:Int=23 'Some Number to test for Odd/Even. For Local i:Int=a To 2 Step -2 a=a-2 Next If a=1 Then Print "Odd." If a=0 Then Print "Even." HA! [Edit] P.S. LOL, ok, I realize it only works for positive numbers. Oops. Local a:Int=-23 If a=0 Then Print "Zero." If a<0 Then a=a*-1 For Local i:Int=a To 2 Step -2 a=a-2 Next If a=1 Then Print "Odd." If a=0 Then Print "Even." |
| ||
| Probably I'm being too cautious, but like ima says I was refering to the way that an integer might be stored on the computer... I think Shortwind got it wright. True. It is the job of the compiler to deal with differences as such. Again, who is to say that the maker of the compiler will implement either one or both. we can't predict the future and to be worried about something that has been standard sense day 1, about becoming obsolete, is just pure panic in my opinion. nothing is forever but if we become so concern with stuff like these, well... |
| ||
| I'm talking about the way numbers are represented in binary, not whether bitwise operations and/or mod will or will not be available on some theoretical compiler. For this particular example, it's not much of a concern, but here is another example. http://en.wikipedia.org/wiki/Signed_number_representations Here are FOUR different ways you can represent negative 6 in 5 different and real representations (although most of these are probably obscure representations, that's not the point). 6 1110 1001 1010 0001 A bitwise trick to determine if a number is negative, for example, might work on one computer but fail miserably on another which represents numbers in a different way. That's why it's usually better to use a more generic method, in this case (x < 0), even if it's slower. In this case < is a fast comparison, but even if it weren't, I would still endorse its use. That's because < is defined to work the same way with the "mathematical" value of the number on every computer, ignoring super obscure languages which might not have < for some reason. You don't need to depend upon or even know how integers are stored on a computer. If you can use <, you can detect a negative number. Likewise, with Mod, you don't need to know or even care how numbers might be stored internally on that computer. Your test will ALWAYS work, if a language provides a Mod operator. Of course maybe some obscure language X won't provide a Mod operator, but so what? This is a Blitz forum, a question about Blitz code, and Blitz has Mod. You should only use bitwise checks when speed of a particular operation is critical. Truely critical. And if you do use bitwise checks, you should always bear in mind that numbers might be represented differently on different computers. Even if there is a 99% chance it will be the same and you don't account for that 1%, it's still good karma to at least even be aware of that. But that's something a beginner might not appreciate or even care about until he's more experienced. In any case, the OP did ask for the quickest method, which is the bitwise one. |
| ||
| LOL! |
| ||
| That's what your mum said too. |
| ||
| very mature. |
| ||
| You smell, smelly! |
   |