odd/even bitwise and

[Serve Laurijssen]

Some people prefer to use
"if (x & 1)"
to see if a number is odd or even. Is this completely portable according to
the standard?

 

[Ahmed S. Badran]

"if (x & 1)"
to see if a number is odd or even. Is this completely portable according to
the standard?

I don't know what does this have to do with the standard, but the thing is
an odd number will ALWAYS have bit 0 set to '1' and an even number will
always have bit 0 set to '0'. This is a matter of binary representation.

Ahmed

 

[CBFalconer]

Some people prefer to use
"if (x & 1)"
to see if a number is odd or even. Is this completely portable
according to the standard?

Only if x is some form of unsigned integer.

 

[pete]

Some people prefer to use
"if (x & 1)"
to see if a number is odd or even.
Is this completely portable according to the standard?

If x is an unsigned integer type
or a signed type with a non negative value, then it's portable.

 

[pete]

I don't know what does this have to do with the standard,

The answer to the question, is in the standard.

but the thing is an odd number will ALWAYS have bit 0 set to
'1' and an even number will always have bit 0 set to '0'.

That's not true for one's complement
representations of negative integers.

This is a matter of binary representation.

The standard specifies more than one
way to represent negative integers.

 

[osmium]

I don't know what does this have to do with the standard, but the thing is
an odd number will ALWAYS have bit 0 set to '1' and an even number will
always have bit 0 set to '0'. This is a matter of binary representation.

It depends on the hardware. If x is a one's complement representation of 0
the test might fail. It strikes me as code intended to impress someone with
one's erudition, I would not do it.

 

[Ahmed S. Badran]

The answer to the question, is in the standard.


That's not true for one's complement
representations of negative integers.


The standard specifies more than one
way to represent negative integers.

Ok, just to re-elaborate and make the answer complete, I never took negative
numbers into consideration with my previous answer, so my previous answer is
valid/correct with all positive integers. Thanks for pointing that out guys.

Ahmed

 

[=?ISO-8859-1?Q?Rog=E9rio_Brito?=]

Some people prefer to use
"if (x & 1)"
to see if a number is odd or even. Is this completely portable according to
the standard?

No. That is only possible if the representation of the integers use
twos-complement.

To see if a number is odd or even, use the modulus operator (e.g., x%2).

 

[Mark Henning]

No. That is only possible if the representation of the integers use
twos-complement.

To see if a number is odd or even, use the modulus operator (e.g., x%2).

That is the way that I have always done it, although it occurs to me
that AND-ing a value with one may be a significantly simpler computation
than calculating the remainder of a divide by two in the majority of
circumstances. This method might be worth considering for unsigned
integers.

M. Henning.

 

[Chris Torek]

[using % to obtain integer remainder after division] is the way that
I have always [tested for even/odd], although it occurs to me
that AND-ing a value with one may be a significantly simpler computation
than calculating the remainder of a divide by two in the majority of
circumstances. This method might be worth considering for unsigned
integers.

This is true; but at the same time, on any machine where it matters,
any optimizing compiler worthy of the word "optimizing" should turn:

x % constant

into:

x & (constant - 1)

whenever the given constant is a power of two, because these always
produce the same result (for an unsigned x).

For signed integers (and still power-of-two constants), the process
is a bit more difficult -- a typical two's complement signed integer
gives different answers for "x % CONST" and "x & (CONST-1)" when
x is negative. There are bit-twiddling tricks that can be used if
the value is required, though; and if only the "truth-ness" of the
value is of interest, the above transform again works. That is:

if (x % 8)

and:

if (x & 7)

are both true (or false) in the same sets of cases, even when x is
signed, as long as the machine uses two's complement. This allows
an optimizing compiler to "do the right thing".

 

[=?ISO-8859-1?Q?Rog=E9rio_Brito?=]

That is the way that I have always done it, although it occurs to me
that AND-ing a value with one may be a significantly simpler computation
than calculating the remainder of a divide by two in the majority of
circumstances. This method might be worth considering for unsigned
integers.

Sure, if you can assume certain things about the platform, then you can
usually make some things slightly more efficient. But then the code is
not portable anymore, which was what started the thread.

And you might argue that the code is a little bit more obfuscated, since
it is not expressing what you wanted in the first place (seeing the
remainder of the division by two).

These small optimizations are what Knuth is talking about when he says
that "premature optimization is the root of all evil".

And, of course, a smart compiler could very well see that the target
platform uses a twos-complement and transform the particular cases of
remainders modulo a power of two into a corresponding bitwise AND
operation. The same for multiplying or dividing by a power of two and
using appropriate shift operations.

 

[Eric Sosman]

That is the way that I have always done it, although it occurs to me
that AND-ing a value with one may be a significantly simpler computation
than calculating the remainder of a divide by two in the majority of
circumstances. This method might be worth considering for unsigned
integers.

What fraction of your program's running time is expended
on determining whether a number is even or odd? One percent
seems high, but let's be generous and suppose your design calls
for a really large number of such determinations. All right,
how much faster might "and" be than "remainder?" Machine-
specific, of course, but let's again be generous and suppose
"modulus" takes whatever it takes while "and" is infinitely
faster, taking zero time. Switching from "modulus" to "and"
would speed up your program by ...

<< May I have the envelope, please? >>

... a WHOPPING one percent! WOW!!!

If your other problems are so insignificant that something
this tiny becomes important, you are to be envied.

 

[Kevin D. Quitt]

so my previous answer is
valid/correct with all positive integers.

Unless, of course, there are padding bits in the integer. The only
correct way to test for mathematical even or odd is to use a mathematical
expression.

 

[Martin Ambuhl]

Some people prefer to use
"if (x & 1)"
to see if a number is odd or even. Is this completely portable according to
the standard?

NO.

 

[pete]

No. That is only possible if the representation of the integers use
twos-complement.

It's also possible with Sign and Magnitude representation.

 

[pete]

Unless, of course, there are padding bits in the integer.

Makes no difference if there are padding bits in the integer.
(x & 1) is true for all positive odd int x, regardless of padding.

 

[August Derleth]

It's also possible with Sign and Magnitude representation.

Wouldn't that be "signed magnitude"? Or are there some other
representations I'm missing out on?

(The ones I know of are signed magnitude, one's complement, and two's
complement.)

 

[Arthur J. O'Dwyer]

Wouldn't that be "signed magnitude"? Or are there some other
representations I'm missing out on?

(The ones I know of are signed magnitude, one's complement, and two's
complement.)

No. The canonical phrase is "sign-magnitude representation,"
which refers to the fact that S-M representation is one in which
the ign of the number is separated from the [M]agnitude. That
is, you have one bit for the sign and the rest for the magnitude,
unlike two's-complement or ones'-complement, in which the sign is
sort of "tied up with" the magnitude in an icky way. ;-)
I believe I've got the apostrophes in the right places above.
Knuth, IIRC, says in TAOCP why he writes the apostrophes where he
does. Ones' complement, plural possessive, because you're XORing
the number with a bunch of ones (111111...) to negate it. Two's
complement, singular possessive, because you're doing something or
other with a power of two.

You're not missing any representation methods allowed by the C
standard, although I'm sure there are many more outlandish ones
out there.

HTH,
-Arthur

 

[Barry Schwarz]

I don't know what does this have to do with the standard, but the thing is
an odd number will ALWAYS have bit 0 set to '1' and an even number will
always have bit 0 set to '0'. This is a matter of binary representation.

There are systems where bit 0 is the high order or sign bit, not the
low order one.


<<Remove the del for email>>

 

[Kevin D. Quitt]

Makes no difference if there are padding bits in the integer.
(x & 1) is true for all positive odd int x, regardless of padding.

According to what?