473,320 Members | 1,859 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

odd/even bitwise and

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?
Nov 14 '05 #1
27 4036

"Serve Laurijssen" <cs@nospam.comp.com> wrote in message
news:eJucc.5394$RU5.83970@zonnet-reader-1...
"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
Nov 14 '05 #2
Serve Laurijssen wrote:

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.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #3
Serve Laurijssen wrote:

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
Nov 14 '05 #4
Ahmed S. Badran wrote:

"Serve Laurijssen" <cs@nospam.comp.com> wrote in message
news:eJucc.5394$RU5.83970@zonnet-reader-1...
"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,


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.

--
pete
Nov 14 '05 #5
Ahmed S. Badran writes:
"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.


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.
Nov 14 '05 #6
pete wrote:
Ahmed S. Badran wrote:

"Serve Laurijssen" <cs@nospam.comp.com> wrote in message
news:eJucc.5394$RU5.83970@zonnet-reader-1...
"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,


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.

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

Nov 14 '05 #7
Serve Laurijssen wrote:
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).

--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Rogério Brito - rb****@ime.usp.br - http://www.ime.usp.br/~rbrito
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Nov 14 '05 #8
Rogério Brito wrote:
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.
Nov 14 '05 #9
Mark Henning wrote:
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.
--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Rogério Brito - rb****@ime.usp.br - http://www.ime.usp.br/~rbrito
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Nov 14 '05 #10
In article <news:c4**********@taliesin2.netcom.net.uk>
Mark Henning <ma*******@btopenworld.com> writes:
[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".
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 14 '05 #11
Mark Henning wrote:

Rogério Brito wrote:
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.


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.

--
Er*********@sun.com
Nov 14 '05 #12
On Tue, 6 Apr 2004 17:11:58 +0200, "Ahmed S. Badran"
<a_******@hotmail.com> wrote:
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.
--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list
Nov 14 '05 #13
Serve Laurijssen wrote:
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.
Nov 14 '05 #14
Rogério Brito wrote:

Serve Laurijssen wrote:
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.


It's also possible with Sign and Magnitude representation.

--
pete
Nov 14 '05 #15
Kevin D. Quitt wrote:

On Tue, 6 Apr 2004 17:11:58 +0200, "Ahmed S. Badran"
<a_******@hotmail.com> wrote:
so my previous answer is
valid/correct with all positive integers.


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.

--
pete
Nov 14 '05 #16
pete wrote:
Rogério Brito wrote:
Serve Laurijssen wrote:
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.

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.)

--
yvoregnevna gjragl-guerr gjb-gubhfnaq guerr ng lnubb qbg pbz
To email me, rot13 and convert spelled-out numbers to numeric form.
"Makes hackers smile" makes hackers smile.

Nov 14 '05 #17

On Tue, 6 Apr 2004, August Derleth wrote:

pete wrote:
Rogério Brito wrote:

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


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.)


No. The canonical phrase is "sign-magnitude representation,"
which refers to the fact that S-M representation is one in which
the [S]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
Nov 14 '05 #18
On Tue, 6 Apr 2004 13:39:08 +0200, "Ahmed S. Badran"
<a_******@hotmail.com> wrote:

"Serve Laurijssen" <cs@nospam.comp.com> wrote in message
news:eJucc.5394$RU5.83970@zonnet-reader-1...
"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.

There are systems where bit 0 is the high order or sign bit, not the
low order one.
<<Remove the del for email>>
Nov 14 '05 #19
On Tue, 06 Apr 2004 23:01:26 GMT, pete <pf*****@mindspring.com> wrote:

Kevin D. Quitt wrote:

On Tue, 6 Apr 2004 17:11:58 +0200, "Ahmed S. Badran"
<a_******@hotmail.com> wrote:
>so my previous answer is
>valid/correct with all positive integers.


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.


According to what?
--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list
Nov 14 '05 #20
Kevin D. Quitt wrote:

On Tue, 06 Apr 2004 23:01:26 GMT, pete <pf*****@mindspring.com> wrote:
Kevin D. Quitt wrote:

On Tue, 6 Apr 2004 17:11:58 +0200, "Ahmed S. Badran"
<a_******@hotmail.com> wrote:
>so my previous answer is
>valid/correct with all positive integers.

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.


According to what?


According to the facts that if x is a positve int,
then the representation for x and the representation for 1,
have the same corresponding value bits and the same corresponding
sign bit and the same corresponding padding bits.
And the padding bits aren't part of the value
of either x or 1 or (x & 1).

How do you figure padding bits make a difference ?

--
pete
Nov 14 '05 #21

"Barry Schwarz" <sc******@deloz.net> wrote in message
news:c5**********@216.39.134.78...
There are systems where bit 0 is the high order or sign bit, not the
low order one.


ok, but what's the bit representation of 1 on such a system then? x & 1
could work on such a system too I'd say.
Nov 14 '05 #22

In article <Pi*********************************@unix50.andrew .cmu.edu>, "Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> writes:

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


There are non-outlandish (inlandish?) integer representations which
are not allowed by the C standard, too, such as BCD and various
bignum representations. Or representing integers using a different
byte order than the machine's native one - quite common in COBOL
programs, to maintain binary compatibility with data files generated
by mainframe COBOL programs. The Standard mandates a "pure binary"
representation for good reason (consistent behavior across
implementations), but there are often good reasons to employ other
sorts of representations. It's not in the spirit of C to support
those directly (unlike COBOL, which has evolved by tacking on
features to handle whatever the problem of the moment is), which
is fine, but they're not rare.

Really, it's ones'-complement that few people these days are likely
to encounter.

--
Michael Wojcik mi************@microfocus.com

Pocket #9: A complete "artificial glen" with rocks, and artificial moon,
and forester's station. Excellent for achieving the effect of the
sublime without going out-of-doors. -- Joe Green
Nov 14 '05 #23
On Thu, 8 Apr 2004 16:26:08 +0200, "Serve Laurijssen"
<cs@nospam.comp.com> wrote:

"Barry Schwarz" <sc******@deloz.net> wrote in message
news:c5**********@216.39.134.78...
There are systems where bit 0 is the high order or sign bit, not the
low order one.


ok, but what's the bit representation of 1 on such a system then? x & 1
could work on such a system too I'd say.

The bit representation is still normal binary. The only difference is
the nomenclature assigned to the bits, which is a detail C doesn't
address or need to.

Of course it works under the conditions others have identified. My
comment only addressed the point raised by Ahmed S. Badran that you
snipped which stated that bit 0 is the low order bit. It need not be.

<<Remove the del for email>>
Nov 14 '05 #24
Barry Schwarz wrote:

On Thu, 8 Apr 2004 16:26:08 +0200, "Serve Laurijssen"
<cs@nospam.comp.com> wrote:

"Barry Schwarz" <sc******@deloz.net> wrote in message
news:c5**********@216.39.134.78...
There are systems where bit 0 is the high order or sign bit, not the
low order one.


ok, but what's the bit representation of 1 on such a system then? x & 1
could work on such a system too I'd say.

The bit representation is still normal binary. The only difference is
the nomenclature assigned to the bits, which is a detail C doesn't
address or need to.

Of course it works under the conditions others have identified. My
comment only addressed the point raised by Ahmed S. Badran that you
snipped which stated that bit 0 is the low order bit. It need not be.


Bit 0 isn't mentioned in the standard.
The right bits are low order. The left bits are high order.

--
pete
Nov 14 '05 #25
mw*****@newsguy.com (Michael Wojcik) wrote:
In article <Pi*********************************@unix50.andrew .cmu.edu>, "Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> writes:

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


There are non-outlandish (inlandish?) integer representations which
are not allowed by the C standard, too, such as BCD and various
bignum representations. Or representing integers using a different
byte order than the machine's native one


How is this forbidden? I can't find it in 6.2.6.2.

Richard
Nov 14 '05 #26
"Chris Torek" <no****@torek.net> wrote in message
news:c4*********@news1.newsguy.com...
In article <news:c4**********@taliesin2.netcom.net.uk>
Mark Henning <ma*******@btopenworld.com> writes:
[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 the record, I just tested gcc 2.91.66 for x86 and it strength-reduces (x
% 2) to (i & 1) even with no optimization enabled.

Thanks for the portability tip -- I'd been "prematurely optimizing" this for
years.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
Nov 14 '05 #27

In article <40****************@news.individual.net>, rl*@hoekstra-uitgeverij.nl (Richard Bos) writes:
mw*****@newsguy.com (Michael Wojcik) wrote:
There are non-outlandish (inlandish?) integer representations which
are not allowed by the C standard, too, such as BCD and various
bignum representations. Or representing integers using a different
byte order than the machine's native one


How is this forbidden? I can't find it in 6.2.6.2.


It doesn't appear to be (though it could be argued that it would violate
the spirit of the "pure binary representation" requirement). I added
it in a later edit of the paragraph, without sufficient care. Thanks
for the catch.

BCD and some bignum representations are still good examples, though.

--
Michael Wojcik mi************@microfocus.com
Nov 14 '05 #28

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

14
by: Debbie Lucier | last post by:
How would I generate a even random number each time? I can generate a random number each time but not an even one? Here is the code I use for the random number from 1-100. <script...
8
by: Paul E Collins | last post by:
Suppose I have a few Keys objects: Keys k1 = Keys.V; // V Keys k2 = Keys.Control | Keys.V; // Ctrl+V Keys k3 = Keys.Shift | Keys.J; // Shift+J I need to determine which of these include the...
8
by: Eps | last post by:
I have a for loop and i want to do different things depending on whether the counter is even or odd. I know there is probably some really simple math thing that can do this but my maths is a bit...
10
by: Emilio | last post by:
Do I use 'or' for bitwise operations where in c# I use | ?
17
by: zirconx | last post by:
I'm trying to understand how the bitwise AND can be used. I've read about what it does but am having trouble applying it practically. I'm working on a system that somebody else wrote and they...
2
by: Mark Rae | last post by:
Hi, This isn't *specifically* an ASP.NET question, so I've also posted it in the ADO.NET group - however, it's not too far off-topic... Imagine a SQL Server 2005 database with a table with an...
3
by: Jay Ruyle | last post by:
I'm trying to figure out a way to list several items in a listbox and let the user select any number of items in the listbox. I have tried to code in the items as bitwise items but all it stores...
5
by: Gigs_ | last post by:
Can someone explain me bitwise expression? few examples for every expression will be nice x << y Left shift x >y Right shift x & y Bitwise AND x | y Bitwise OR x ^ y Bitwise XOR (exclusive...
45
by: Carramba | last post by:
Hi! I now that I can't do straight forward any bitwise operation on float (double etc..). But I wondering what is the easiest/best way to do this? I was thinking if I have float x=1.1111 so I can...
29
by: Carl Banks | last post by:
Anyone with me here? (I know the deadline for P3 PEPs has passed; this is just talk.) Not many people are bit-fiddling these days. One of the main uses of bit fields is flags, but that's not...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shćllîpôpď 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.