464,293 Members | 1,183 Online
Need help? Post your question and get tips & solutions from a community of 464,293 IT Pros & Developers. It's quick & easy.

# the fastest way to do an odd/even check?

 P: n/a Hi, I have a question, which is just out of interest. What is the fastest way to do an odd/even check with c++ and if needed assembler. Assume n is an unsigned integer like type (unsigned int, unsigned long int), what is the fastest? using the modulo operator a) if (n%2 == 0) then even b) if (n%2 == 1) then odd c) if (n%2 != 1) then even d) if (n%2 != 0) then odd using the bit shift operator e) if ((n >1) << 1 == n) then even f) if ((n >1) << 1 != n) then odd g) if (((n >1) << 1) - n == 0) then even h) if (n - ((n >1) << 1) == 1) then odd They always told me that checking against '0' is the best for "speed", if you can call it speed here ;-), thus this rules out b and c for sure. But what would it be? I think bitshifts are faster then modulo calculations. Is this right? The most fast would be checking the last bit in the binary array. Is it 1, then it is odd else it is even. Can you do bitchecks in a number with c++? I can think of a rule, assume you want to check bit 5, you can do n & (1<<5) == (1<<5) but this is for sure not faster then just reading the bit. Because you do 64 operations with the & and 64 operations with the checking, which is much more then 2 operations. So I was just wondering. Anybody an idea? Thanks Klaas Feb 1 '07 #1
6 Replies

 P: n/a * Klaas Vantournhout: Hi, I have a question, which is just out of interest. What is the fastest way to do an odd/even check with c++ and if needed assembler. Assume n is an unsigned integer like type (unsigned int, unsigned long int), what is the fastest? using the modulo operator a) if (n%2 == 0) then even b) if (n%2 == 1) then odd c) if (n%2 != 1) then even d) if (n%2 != 0) then odd using the bit shift operator e) if ((n >1) << 1 == n) then even f) if ((n >1) << 1 != n) then odd g) if (((n >1) << 1) - n == 0) then even h) if (n - ((n >1) << 1) == 1) then odd They always told me that checking against '0' is the best for "speed", if you can call it speed here ;-), thus this rules out b and c for sure. But what would it be? I think bitshifts are faster then modulo calculations. Is this right? The most fast would be checking the last bit in the binary array. Is it 1, then it is odd else it is even. Can you do bitchecks in a number with c++? I can think of a rule, assume you want to check bit 5, you can do n & (1<<5) == (1<<5) but this is for sure not faster then just reading the bit. Because you do 64 operations with the & and 64 operations with the checking, which is much more then 2 operations. So I was just wondering. Anybody an idea? The assumptions about speeds of various operations above are plain wrong. It depends on the compiler and the computer (and more). Also, the assumptions about number of operations involved in bit shifting are plain wrong. Don't try to optimize at this level: let the compiler do it. If you think you have to optimize, first /measure/. And that doesn't mean measuring operations, it means measuring where your code spends its time, i.e. getting hard data on what may benefit from optimization. Even better, don't try to optimize basic operations, at all, but do choose reasonably efficient algorithms. Finally, please read the FAQ before posting. The FAQ contains much good advice, I believe also about the above. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Feb 1 '07 #2

 P: n/a On Feb 1, 3:29 pm, Klaas Vantournhout 1) << 1 == n) then even f) if ((n >1) << 1 != n) then odd g) if (((n >1) << 1) - n == 0) then even h) if (n - ((n >1) << 1) == 1) then odd These does not look particularly fast to me, many operations. But it might be faster than modulo, I don't know how that's done in the CPU. They always told me that checking against '0' is the best for "speed", if you can call it speed here ;-), thus this rules out b and c for sure. But what would it be? I think bitshifts are faster then modulo calculations. Is this right? On some CPUs there's a special register for the value 0 while other values might have to be loaded into a register first. The most fast would be checking the last bit in the binary array. Is it 1, then it is odd else it is even. Can you do bitchecks in a number with c++? Bitwise compare: if (n | 0x1) then odd this is probably the fastest way. I can think of a rule, assume you want to check bit 5, you can do n & (1<<5) == (1<<5) Better would be if (n | 0x10) > but this is for sure not faster then just reading the bit. Because you do 64 operations with the & and 64 operations with the checking, which is much more then 2 operations. 64 operations? Shifting is 1 operation and & is one operation and compare is 1, since there are two shifts that adds up to 4 operations. So I was just wondering. Anybody an idea? If you are wondering these kinds of things you should either go and read up some on how computers works and assembly programming. Or you are trying to optimize something, in which case I'd advice you to do some profiling before trying to speed up that operation, it's most probably not the slowest one in a program. If you want to know how these things work on modern CPUs you can download a lot of stuff from Intel: http://www.intel.com/products/proces...uals/index.htm Feb 1 '07 #3

 P: n/a Erik Wikström wrote: If you are wondering these kinds of things you should either go and read up some on how computers works and assembly programming. Or you are trying to optimize something, in which case I'd advice you to do some profiling before trying to speed up that operation, it's most probably not the slowest one in a program. If you want to know how these things work on modern CPUs you can download a lot of stuff from Intel: http://www.intel.com/products/proces...uals/index.htm Thanks for your response Erik, It was for sure not my intention of optimizing this, but it was just a curiosity! You are absolutely right that this is more related to the compiler, assembler and the CPU. If that process would have been the slowest process in the code ... then I can imagine that something is seriously wrong with the code ;-) regards Klaas Feb 1 '07 #4

 P: n/a On Feb 1, 9:29 am, Klaas Vantournhout 1) << 1 == n) then even f) if ((n >1) << 1 != n) then odd g) if (((n >1) << 1) - n == 0) then even h) if (n - ((n >1) << 1) == 1) then odd They always told me that checking against '0' is the best for "speed", if you can call it speed here ;-), thus this rules out b and c for sure. But what would it be? I think bitshifts are faster then modulo calculations. Is this right? The most fast would be checking the last bit in the binary array. Is it 1, then it is odd else it is even. Can you do bitchecks in a number with c++? I can think of a rule, assume you want to check bit 5, you can do n & (1<<5) == (1<<5) but this is for sure not faster then just reading the bit. Because you do 64 operations with the & and 64 operations with the checking, which is much more then 2 operations. So I was just wondering. Anybody an idea? Thanks Klaas I worked at one job where this was a standard interview question, but that was many languages, many computers, and many years ago. It started a discussion of all the ways one could test for odd/even. Some languages contain an "IsOdd" method. The usual method at the time was to divide by 2, multply by two and see if you have the same number (even) or not (odd). Back then, there were different method of storing numbers so the shift method was not portable. When the moduler operation became standard, some people shifted to that. btw: The slowest method that I ever saw implemented was to subtract 2 over and over again until the number was less than two and then the result was compared to 1. Needless to say, the implementer became an ex-programmer. Feb 1 '07 #5

 P: n/a "Erik Wikström" using the modulo operatora) if (n%2 == 0) then evenb) if (n%2 == 1) then oddc) if (n%2 != 1) then evend) if (n%2 != 0) then odd I would assume all of those to take the same amount of time on a modern CPU, though see my comment on comparing against 0 a bit down. >e) if ((n >1) << 1 == n) then evenf) if ((n >1) << 1 != n) then oddg) if (((n >1) << 1) - n == 0) then evenh) if (n - ((n >1) << 1) == 1) then odd These does not look particularly fast to me, many operations. But it might be faster than modulo, I don't know how that's done in the CPU. .... Bitwise compare: if (n | 0x1) then odd this is probably the fastest way. This is probably the fastes of all operations mentioned here. Any decent compile should recognize that n|1 is always true. >I can think of a rule, assume you want to check bit 5, you can don & (1<<5) == (1<<5) Better would be if (n | 0x10) Both look terrible, but the second is plain wrong. To test a single bit you have to use & instead of |. Using | with a non-zero constant will give a non-zero result. My prefered way to test the state of the single bit is if (n & (1 << x)) // even if x is 0 If the compiler cannot replace such constant sub-expressions at compile time, it shouldn't be used at all. Even the oldest C compilers could do that. To the OP: Most modern compilers should recognize what expressions like n%2 or n&1 are suposed to do and optimize them, probably to the same code. So use whatever is more readable to you and those (humans) who are supposed to read your code. Using % looks like a mathmatican's approach, & like an assembly language programmer's. The shifting orgy in e - g, however, looks like a mad sicentist's code. Heinz Feb 1 '07 #6

 P: n/a "Heinz Ozwirk" Better would be if (n | 0x10) Both look terrible, but the second is plain wrong. To test a single bit you have to use & instead of |. Indeed. Besides, 1<<5 == 0x20, not 0x10 > To the OP: Most modern compilers should recognize what expressions like n%2 or n&1 are suposed to do and optimize them, probably to the same code. For unsigned integers, perhaps, but certainly not always for signed integers as -1 % 2 == -1 on most architectures. - Sylvester Feb 2 '07 #7

### This discussion thread is closed

Replies have been disabled for this discussion.