Author 
Message 
Ralph Silverm #1 / 174

even vs. odd numbers
: : I agree with your first preference. However, from the tone of the original : : posting, I suspect that Jerry Unser is quite new to C. It follows that the : : terse and very efficient example that you give might not lead to his : : further understanding of the problem. : : As for your second suggestion... a decent optimiser would almost certainly : : change this to a bitwise AND operation. BUT  just in case it doesn't I : : don't think I would opt for that technique. : :  : : Andy Knight
: : > : : > >BOOL IsOdd(int x) : : > >{ : : > > return (x & 1) ? TRUE : FALSE ; : : > >} : : > : : > I prefer : : > int IsOdd( int x) : : > { : : > return ( x & 1 ) : : > } : : > : : > or : : > : : > return !(x%2) : : > : : > : : > h.f.s. : : > : : > : : >  : : > Hans Friedrich Steffani : : > Institut fuer Elektrische Maschinen und Antriebe, TU ChemnitzZwickau
: : > http://www.***.com/ ~hfst/ : : > :  : ****************begin r.s. response******************** Quote: >>>>>>>>>>>>>>>>OOOPS
THIS APPLIES TO EVEN INTEGER !!! SENSE IS INVERTED !!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! : 1) what is an odd integer ? : in binary number system an : integer is odd iff : least significant digit is clear : i.e. least significant digit is not set : i.e. least significant digit is zero ( 00 ) : i.e. least significant digit is not : (( 1 ) one) : . <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< : 2) : test like : ( yournumber & 01 ) : masks 'yournumber' with bitpattern : such that zero ( 00 ) value will : result unless least significant bit : is set : ... : 3) suggested test using modulus operator ? : ( like ) !(yournumber%02) : ... : mod operator is generally far less efficient : than bitop and so, generally, : far less to be preferred !!! : ****************end r.s. response********************** : Ralph Silverman
 Ralph Silverman

Tue, 24 Aug 1999 03:00:00 GMT 


Ralph Silverm #2 / 174

even vs. odd numbers
: I agree with your first preference. However, from the tone of the original : posting, I suspect that Jerry Unser is quite new to C. It follows that the : terse and very efficient example that you give might not lead to his : further understanding of the problem. : As for your second suggestion... a decent optimiser would almost certainly : change this to a bitwise AND operation. BUT  just in case it doesn't I : don't think I would opt for that technique. :  : Andy Knight
: > : > >BOOL IsOdd(int x) : > >{ : > > return (x & 1) ? TRUE : FALSE ; : > >} : > : > I prefer : > int IsOdd( int x) : > { : > return ( x & 1 ) : > } : > : > or : > : > return !(x%2) : > : > : > h.f.s. : > : > : >  : > Hans Friedrich Steffani : > Institut fuer Elektrische Maschinen und Antriebe, TU ChemnitzZwickau
: > http://www.tuchemnitz.de/~hfst/ : >  ****************begin r.s. response******************** 1) what is an odd integer ? in binary number system an integer is odd iff least significant digit is clear i.e. least significant digit is not set i.e. least significant digit is zero ( 00 ) i.e. least significant digit is not (( 1 ) one) . 2) test like ( yournumber & 01 ) masks 'yournumber' with bitpattern such that zero ( 00 ) value will result unless least significant bit is set ... 3) suggested test using modulus operator ? ( like ) !(yournumber%02) ... mod operator is generally far less efficient than bitop and so, generally, far less to be preferred !!! ****************end r.s. response********************** Ralph Silverman

Tue, 24 Aug 1999 03:00:00 GMT 


Kaz Kylhe #3 / 174

even vs. odd numbers
Quote:
> 3) suggested test using modulus operator ? > ( like ) !(yournumber%02) > ... > mod operator is generally far less efficient > than bitop and so, generally, > far less to be preferred !!!
Really? When I write ``<unsigned integral expression> % 2'', my compiler generates code which looks like this: ; evaluate <expr> to REG AND REG, #1 For signed quantities, the generated code is a little longer, but it still avoids doing multiplication or division.

Fri, 27 Aug 1999 03:00:00 GMT 


Ralph Silverm #4 / 174

even vs. odd numbers
: [...] : >Setting aside the issue of negative integers on onescomplement, I would : >still suggest that... : > : > return (x & 1) ; : > : >..is likely to generate even more questions from the originator of the : >query. : Why is that a bad thing? : >Unless I'm sadly mistaken, my solution DOES work on twoscomplement : >machines. Fair enough; it's wrong on a onescomplement system but if : >Jerry is new to C, then he's probably never going to have to deal with a : >onescomplement system. : Is that really an excuse? "x % 2" is perfectly obvious to anybody who : understands division. : >Let's be realistic. It seems to me that there are a large number of : >regular contributors to this newsgroup whose main aim in life is to : >"flame" anything and everything they see... and I find that rather sad. : They can't flame something that is correct, could they? : >If someone makes a mistake, then let them know. Don't be rude about it. : >Surely this is all about trying to help people. Perhaps I'm : >oldfashioned. : Rudeness is one thing (wrong about comp.lang.c and me), but correctness : is an entirely different thing. It's unwise to confuse the two. People : don't extend the extra effort to be correct just in order to be rude to : you.  ***********begin r.s. response***************** regarding ' ... negative integers ... ' ( posting cited above ) ... in application of bitwise operator e.g. & generally, integer should be unsigned ... e.g. ( ((unsigned)x) & 01 ) ... such should obviate validity issue treated in posting cited above ... ***********end r.s. response******************* Ralph Silverman

Fri, 27 Aug 1999 03:00:00 GMT 


Colin Andrew Perciv #5 / 174

even vs. odd numbers
: : Is that really an excuse? "x % 2" is perfectly obvious to anybody who : : understands division. Forgive my ignorance, but I, being a poor 3rd year math major (with a GPA of 4.15), don't understand division. At least, that is what one could conclude from the fact that it isn't obvious to me whether "x % 2" means real division, integer division, or modulo division. Colin Percival

Fri, 27 Aug 1999 03:00:00 GMT 


Vesa Karvone #6 / 174

even vs. odd numbers
Quote:
> > 3) suggested test using modulus operator ? > > ( like ) !(yournumber%02) > > ... > > mod operator is generally far less efficient > > than bitop and so, generally, > > far less to be preferred !!! > Really? When I write ``<unsigned integral expression> % 2'', my compiler > generates code which looks like this: > ; evaluate <expr> to REG > AND REG, #1 > For signed quantities, the generated code is a little longer, but it still > avoids doing multiplication or division.
Wow, a semioptimizing compiler! A kin to one of our good old friends, one can now say that your C compiler optimizes like shit (assuming typical binary representation) ;) ;) "An optimizing programmer can always beat a C programmer.", Vesa Karvonen

Fri, 27 Aug 1999 03:00:00 GMT 


Steven Hua #7 / 174

even vs. odd numbers
Quote:
>:: Is that really an excuse? "x % 2" is perfectly obvious to anybody who >:: understands division. > Forgive my ignorance, but I, being a poor 3rd year math major (with a GPA >of 4.15), don't understand division. > At least, that is what one could conclude from the fact that it isn't >obvious to me whether "x % 2" means real division, integer division, or >modulo division.
Firstly, I believe I wrote that, though you attribute it to Ralph Silverman. Secondly, I was *not* talking about the notation. I was talking about the concept of using modulo division by two to determine if an integer is odd or even, which should be immediately obvious to one who understands the concept of remainders in division. Do you agree? If you took the statement in context, you'd realize all previous proposals were C code.

Fri, 27 Aug 1999 03:00:00 GMT 


Lawrence Kir #8 / 174

even vs. odd numbers
Quote:
>: : Is that really an excuse? "x % 2" is perfectly obvious to anybody who >: : understands division.
Actually "Steven" Huang wrote that. Quote: > Forgive my ignorance, but I, being a poor 3rd year math major (with a GPA >of 4.15), don't understand division. > At least, that is what one could conclude from the fact that it isn't >obvious to me whether "x % 2" means real division, integer division, or >modulo division.
Certainly you have to know that C defines % as a remainder operator for integer division. The point is however that it should be obvious to anybody who understands division that the remainder of X divided by 2 (where X is an integer) indicates whether X is odd or even.  


Fri, 27 Aug 1999 03:00:00 GMT 


Ralph Silverm #9 / 174

even vs. odd numbers
: >: : Is that really an excuse? "x % 2" is perfectly obvious to anybody who : >: : understands division. : Actually "Steven" Huang wrote that. : > Forgive my ignorance, but I, being a poor 3rd year math major (with a GPA : >of 4.15), don't understand division. : > : > At least, that is what one could conclude from the fact that it isn't : >obvious to me whether "x % 2" means real division, integer division, or : >modulo division. : Certainly you have to know that C defines % as a remainder operator : for integer division. The point is however that it should be obvious to : anybody who understands division that the remainder of X divided by 2 (where : X is an integer) indicates whether X is odd or even. :  : 
:   ****************begin r.s. response****************** use of division type operator modulus % is, generally, one of the least efficient arithmetic operations on integer datatypes ... use of bitwise operator is one of the most efficient integer operations ... as indicated elsewhere ... use of bitwise op for this purpose should be done on unsigned integer type ... hence ... cast might be indicated ... even in such a case ... reasonably, bitwise method is preferable ... ( yourunsignedintvalue & 01 ) ****************end r.s. response******************** Ralph Silverman

Sat, 28 Aug 1999 03:00:00 GMT 


Alicia Carla Longstree #10 / 174

even vs. odd numbers
Quote:
> Colin Andrew Percival writes:
> >: : Is that really an excuse? "x % 2" is perfectly obvious to anybody who > >: : understands division. > Actually Steven Huang wrote that. > > Forgive my ignorance, but I, being a poor 3rd year math major (with a GPA > > of 4.15), don't understand division. > > At least, that is what one could conclude from the fact that it isn't > > obvious to me whether "x % 2" means real division, integer division, or > > modulo division. > Certainly you have to know that C defines % as a remainder operator > for integer division.
[snip out true part] Why does he *have* to know. When this operator was first presented to me it was as the modulus operator. I am not a math whiz but I do know that there is a difference (however small) between the modulus function and the remainder after integer division. It is certainly possible that the poster was, also, given a incorrect definition for this operator.  ********************************************
******************************************** The first element of greatness is fundamental humbleness (this should not be confused with servility); the second is freedom from self; the third is intrepid courage, which, taken in its widest interpretation, generally goes with truth; and the fourththe power to love although I have put it last, is the rarest. Margot Asquith

Sat, 28 Aug 1999 03:00:00 GMT 


Mike McCar #11 / 174

even vs. odd numbers
[finding out if odd by x & 1 on signed integers] )***********begin r.s. response***************** ) ) regarding ) ' ... negative integers ... ' ) ( posting cited above ) ... ) in application of ) bitwise operator ) e.g. ) & ) generally, ) integer should be ) unsigned ) ... ) e.g. ) ( ((unsigned)x) & 01 ) ) ... ) such should obviate ) validity issue treated in ) posting cited above ... Nope, not true. Casting to unsigned does not change the bits. And the LSB will not tell you whether a signed integer is odd. This would work, however: unsigned y; y = abs(x); if (y & 1) /* x was odd */ BUT, there may be numbers which are not negatable. Mike   char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);} This message made from 100% recycled bits. I don't speak for DSC. < They make me say that.

Sun, 29 Aug 1999 03:00:00 GMT 


Mike Rubenste #12 / 174

even vs. odd numbers
Quote:
> [finding out if odd by x & 1 on signed integers] > )***********begin r.s. response***************** > ) > ) regarding > ) ' ... negative integers ... ' > ) ( posting cited above ) ... > ) in application of > ) bitwise operator > ) e.g. > ) & > ) generally, > ) integer should be > ) unsigned > ) ... > ) e.g. > ) ( ((unsigned)x) & 01 ) > ) ... > ) such should obviate > ) validity issue treated in > ) posting cited above ... > Nope, not true. Casting to unsigned does not change the bits. And the > LSB will not tell you whether a signed integer is odd. > This would work, however: > unsigned y; > y = abs(x); > if (y & 1) /* x was odd */ > BUT, there may be numbers which are not negatable.
Wrong. Casting to unsigned may change the bits. The rules for converting a signed integer to unsigned insure that the low order bit will be 1 if the original was odd. For two's complement representation, converting to unsigned does not change the bits, but for one's complement or signedmagnitude it does. For example, 1 is converted to all (meaningful) bits 1 in the unsigned representation. Michael M Rubenstein

Sun, 29 Aug 1999 03:00:00 GMT 


Lawrence Kir #13 / 174

even vs. odd numbers
Quote:
>> Certainly you have to know that C defines % as a remainder operator >> for integer division. >[snip out true part] >Why does he *have* to know.
Maybe my English was a little too idiomatic. I meant it was prerequisite to know, i.e. if you didn't know that % is the remainder operator in C then a mathematical knowledge of division isn't going to help you. Quote: > When this operator was first presented to >me it was as the modulus operator. I am not a math whiz but I do know >that there is a difference (however small) between the modulus function >and the remainder after integer division. It is certainly possible that >the poster was, also, given a incorrect definition for this operator.
You can view % as a modulus operator if you wish. You would the the same results here.  


Sun, 29 Aug 1999 03:00:00 GMT 


Lawrence Kir #14 / 174

even vs. odd numbers
Quote: > use of division type operator > modulus > % > is, generally, one of the least > efficient arithmetic operations > on integer datatypes ...
That depends on the language. In a compiled language like C, (i % 2) == 0 can be trivially optimised to appropriate bit operations by the compiler. As a programmer you don't have to worry about it, just concentrate on writing clear, correct code. Quote: > use of bitwise operator is one > of the most efficient integer > operations ...
Which is why compilers make a lot of effort to use them where possible. Certainly your observation is much more relevant to comp.lang.asm.x86 readers. Quote: > as indicated elsewhere ... > use of bitwise op for this > purpose should be done on > unsigned integer type ... > hence ... > cast might be indicated ... > even in such a case ... > reasonably, > bitwise method is preferable ... > ( yourunsignedintvalue & 01 )
For unsigned types any reasonable C compiler would produce the same code for (val % 2) and (val & 1).  


Sun, 29 Aug 1999 03:00:00 GMT 


Lawrence Kir #15 / 174

even vs. odd numbers
... Quote: >) e.g. >) ( ((unsigned)x) & 01 ) >) ... >) such should obviate >) validity issue treated in >) posting cited above ... >Nope, not true. Casting to unsigned does not change the bits. And the >LSB will not tell you whether a signed integer is odd.
Ralph is correct here. Conversion between integral types is defined on value rather than bit pattern. The rules for converting a negative value to an unsigned type happen to mean that there is no change in bit pattern if the signed value is represented as 2's complement. However in any other signed number representation the compiler would be *required* to change the bit pattern. Since unsigned arithmetic works modulo an even number (in fact a power of 2), an even negative number is guaranteed to map to an even unsigned number and similarly for odd numbers. For example in 16 bit signmagnitude format 1 is represented as: 100000000 00000001 When converted to 16 bit unsigned format the value is (UINT_MAX+1)1 which is UINT_MAX i.e. 111111111 11111111 (also the representation of 2's complement 1) Of more interest to this thread 1's complement 1 is represented as: 111111111 11111110 which again gets converted to unsigned: 111111111 11111111 Quote: >This would work, however: > unsigned y; > y = abs(x); > if (y & 1) /* x was odd */ >BUT, there may be numbers which are not negatable.
Right, abs(INT_MIN) may result in overflow and hence undefined behaviour. Also x in Ralph's solution can be of *any* integral type, even long or unsigned long.  


Sun, 29 Aug 1999 03:00:00 GMT 


