Finding whether a signed and an unsigned integer are both even or both odd

Question

I have an int m and an unsigned int j and want to determine whether they are both even or both odd.

In the past I've been using

if((int(j)+m)%2)

to catch the case that only one is odd. But I'm concerned about the casting to int incorrectly changing the odd-even-ness of j.

Do either of these run into problems?

if(!(j%2)!=!(m%2))
if(bool(j%2)!=bool(j%2))

I know that

if(j%2!=m%2)

doesn't work because 'm%2' will produce -1 when m is negative, which will always evaluate to true no matter what the value of j%2 is.

@IgnacioVazquez-Abrams Because && doesn't have the right behavior. I'm in effect trying to create a logical XOR which is exactly what the `!=` does. — Johnathan Gross, Jul 21 '17 at 03:21
To clarify, the answer you want is a boolean with the two cases: { both even or both odd, one odd and one even } ? — M.M, Jul 21 '17 at 05:30
FYI, the formal term for "odd-even-ness" is "[parity](https://en.wikipedia.org/wiki/Parity_(mathematics))" (not to be confused with [parity bits](https://en.wikipedia.org/wiki/Parity_bit)). — jwodder, Jul 21 '17 at 12:53
@jwodder: That wikipedia article has two conflicting definitions for parity unfortunately. The LSB of a 1's complement negative number will be 0, not 1, if the number is odd. — Ben Voigt, Jul 21 '17 at 14:37

score 64 · Accepted Answer · answered Jul 20 '17 at 18:42

64

Don't use %. This is a problem that calls for bitmasks:

bool same_parity = (i & 0x1) == (j & 0x1);

This works regardless of the sign of i, since the result of that expression will always be 0 or 1.

answered Jul 20 '17 at 18:42

Barry

286,269
29
621
977

22

Is `&` defined in terms of unsigned integer "bits" or _actual_ bits? In a 1s complement system `-1`'s low order bit is actually `0`. 1s compliment systems are pretty obscure, so I don't know off the top of my head how `&` is defined there. – Yakk - Adam Nevraumont Jul 20 '17 at 18:46
26

@Yakk Actual bits. I guess this would only work for 2s complement, but I've never worked on a 1s complement system before so I just pretend they don't exist. – Barry Jul 20 '17 at 18:50
1

I'm less certain than you. It might be defined in terms of abstract machine integer bits, not even actual bits on the abstract machine (as in, what you get when you cast to `unsigned char*` and examine). C++ std is strange and arcane when you leave the lands of ~~sanity~~ 2s complement. Abstract machine integer bits might have 1s complement "hidden", forcing extra branches when you do `&1`. – Yakk - Adam Nevraumont Jul 20 '17 at 18:52
1

@Barry what's the issue with `%`? – Johnathan Gross Jul 20 '17 at 21:23
9

@JohnathanGross You explained the issue with `%` yourself in the question - it doesn't have the semantics you want. You want an `f` such that `f(x)` gives you 0 or 1, but `(%2)` doesn't give you 0 or 1... it gives you 0 or +/- 1. – Barry Jul 20 '17 at 21:41
1

@Barry The original plan was just to add `j` and `m` and find the remainder from division by 2. In that case, it didn't matter if the sign was negative, all I cared about was that it wasn't 0 because that's all that casting to `bool` cares about. – Johnathan Gross Jul 20 '17 at 21:49
4

@Yakk I've thrown in a static_assert so the compiler catches in any system not using 2's complement. My computer uses 2's complement and I doubt this code will ever be used anywhere else. – Johnathan Gross Jul 21 '17 at 03:19
3

@JohnathanGross: Or you could use `& 1u`, or SolutionMill's variant, and then the code will also work for 1's complement. – Ben Voigt Jul 21 '17 at 14:45
Somehow this is one of my most down voted answers. I don't get it. – Barry Jul 22 '17 at 14:20
1

It may well be because some don't agree with your flat-out rejection of `%`, even though it's perfectly legal in a case like this where `%` just obfuscates the code. – Adowrath Jul 28 '17 at 16:56

score 56 · Answer 2 · edited Jul 21 '17 at 08:32

56

if (1 & (i ^ j))
{
// Getting here if i is even and j is odd
// or if i is odd and j is even
}

^ is the exclusive-or bitwise operator, which checks each bit in both numbers if they have the same value. For example, if the binary representation of i is 0101 and j is 1100, then i ^ j will evaluate to 1001, since their first and last bits are different, while the middle bits are the same.

& is the and bitwise operator, which checks each bit in both numbers if they are both 1.

Since just the last bit of each number determines if it's even or odd, i ^ j will evaluate to ...xxx0 if they are both even or odd, and ...xxx1 otherwise (the xs don't matter, we aren't looking at them anyway). Since 1 is actually ...0001, 1 & (i ^ j) evaluates to 0 if i and j are both even or odd, and 1 otherwise.

This works on any combination of unsigned numbers, 2s-complement, and sign-and-magnitude, but not the rare 1s-complement if exactly one is negative.

edited Jul 21 '17 at 08:32

Deduplicator

44,692
7
66
118

answered Jul 20 '17 at 20:30

SolutionMill

667
6
23

1

Ah, you beat me by seconds... This one generates shortest x86 assembly. – Maxim Egorushkin Jul 20 '17 at 20:31
2

That is the simplest, most effective way. – Michaël Roy Jul 20 '17 at 21:09
1

On a 1s complement system, does this return true or false when fed `1` and `-1`? – Yakk - Adam Nevraumont Jul 20 '17 at 21:48
@Yakk: 1s complement system: `0001 ^ 1110` = `1111`, last bit is `1` so it returns `true`. On 2s complement system: `0001 ^ 1111` = `1110`, last bit is `0` so it returns `false`. – CodeManX Jul 21 '17 at 09:11
@CoDEmanX - the situation is actually more complex than that. The C++ standard requires the values involved to be converted into the same type before the XOR operation is performed, which may involve a change in their representation. Your answer is correct if both values start out in the same signed 1s-complement notation, but if they're in different types the result may be different. – Jules Jul 21 '17 at 09:15
6

The assertion that this doesn't work on 1s-complement systems is (probably) incorrect. The operation `i ^ j` is defined in the C++ standard to perform "[t]he usual arithmetic conversions" before the bitwise XOR is performed (in the N3337 draft, see p.117 S5.12). Unless the signed type is capable of representing all possible values of the unsigned type, this means the signed value will be converted to the unsigned type (p.84, S5 paragraph 9). The rules for converting a signed number to unsigned (p.80, S4.7 paragraph 2) require the result to be "congruent to the source integer (modulo 2^n ... – Jules Jul 21 '17 at 09:28
5

... where n is the number of bits used to represent the unsigned type)". This [congruence relationship](http://mathworld.wolfram.com/Congruence.html) will preserve the parity of the values, and hence give the correct result. The same cannot be said, however, if both values are stored in a *signed* type, as demonstrated by @CoDEmanX above. – Jules Jul 21 '17 at 09:32
This would have been my suggestion, and 1s complement concerns are (I think) just distractions. Since `j` is an `unsigned int`, the (`signed`) `int i` will be cast to an `unsigned int` to perform the XOR, preserving its value modulo `UINT_MAX` + 1. As long as `UINT_MAX` is odd, the value mod 2 won't be affected, and everything will work as you hope. Moreover, I'm not sure that `UINT_MAX` is even _allowed_ to be even. – Joshua Green Jul 21 '17 at 10:00
1

If one is only concerted with `int`s (`signed` or `unsigned`) and/or smaller types, one could write the condition as `if (1 & (i ^ (j | 0U)))` to ensure that we're always working in "`unsigned` land." – Joshua Green Jul 21 '17 at 10:00
@MaximEgorushkin From what I can tell on godbolt, using addition rather than xor is able to take advantage of the `lea` to generate shorter code. EDIT: This is only when storing the result in a variable, it does not do this when branching on it. – Random832 Jul 21 '17 at 13:21
@Random832 It does, however, the result of overflowing a signed integer is undefined. Addition makes it overflow. – Maxim Egorushkin Jul 21 '17 at 13:26
2

@MaximEgorushkin You can convert it to unsigned though and overflow is not an issue. – Random832 Jul 21 '17 at 13:28
@Jules: I think the xor operation could fail on a ones'-complement system that uses one more padding bit for "unsigned" than for "int". The present C Standard would require that type "unsigned" dominate over "int" even in those cases, but since there never has been, and probably never will be, any conforming C99 or C11 implementation on anything other than a two's-complement machine, any consideration of other formats would only be relevant in conjunction with older standards. – supercat Jul 21 '17 at 17:09
1

@MaximEgorushkin: Actually, the accepted answer optimizes to the same asm as this with every major x86 compiler except ICC (https://godbolt.org/g/EAL3Hw), once you account for this answer's expression corresponding to `!=` instead of `==`. MM's answer is actually the best, though, because compilers don't look for the transformation that lets them use `lea`. – Peter Cordes Jul 22 '17 at 07:22

M.M · Answer 3 · 2017-07-21T05:41:17.827

19

Adding two integers adds their parity, so the solution is simply:

if ( (j + m) % 2 )

Unsigned wraparound does not disturb this property, since it's done modulo UINT_MAX+1 which is an even number.

This solution does not depend on any implementatation-specific details such as negative number representation.

Footnote: I'm struggling to see why so many other answers are determined to complicate the issue with bit-shifts, bit-complements, XORs, etc. etc. Unfortunately, IMO, it is sometimes glorified in the C or C++ communities to write tricky code instead of simple code.

edited Jul 21 '17 at 05:41

answered Jul 21 '17 at 05:35

M.M

138,810
21
208
365

This code relies on the 'usual arithmetic conversions' to do the right thing, and so whether this is valid, and whether it will stay valid if the types change slightly, won't be as obvious to everyone as it is for some of the other answers. – JeremyR Jul 21 '17 at 07:23
2

@JeremyR You can use Yakk's suggestion of explicltly casting if you would find that more readable. *Every* code relies on the rules of the language though! – M.M Jul 21 '17 at 09:29
2

This produces asm for x86 (https://godbolt.org/g/BC6EFh) that's at least as good as other options, and better in some cases (especially any time both `j` and `m` are needed later), because it can use `lea` as a non-destructive add. It should be about equal on other ISAs like ARM or MIPS. Using `+` is only obvious once you point it out. Fun fact: compilers (other than ICC) can transform between `1 & (i ^ j)` and `(i & 0x1) != (j & 0x1)`, but not from either of those to this. – Peter Cordes Jul 22 '17 at 07:15
`(j + m + 1) % 2` gives you the opposite condition, and can still be computed with one x86 `lea eax, [rsi+rdi+1]` instruction. (plus `and eax,1` or a test/jcc or whatever). The other answers end up with a `not` instruction when actually creating a `bool` in a register instead of branching on it. – Peter Cordes Jul 22 '17 at 07:24
Gotta disagree with the self-aggrandizing footnote here. There is nothing complicated about masking the last bit to check for parity, with the benefit that it works for any inputs. `(j+m)%2` is undefined if both are signed integer types whose sum overflows. – Barry Jul 22 '17 at 16:54
@Barry this question is specifically about a signed and unsigned integer. You could write `(0u + j + m) % 2` to support them both being signed. – M.M Jul 23 '17 at 03:47

Yakk - Adam Nevraumont · Answer 4 · 2017-07-20T18:55:18.940

16

Casting an unsigned int that is larger than INT_MAX to int is not guaranteed to return a sensible value. The result is undefined.

Casting an int to an unsigned int always results in defined behavior -- it does math mod 2^k for some k large enough that every positive int is less than 2^k.

if((int(j)+m)%2)

should be

if((j+unsigned(m))%2)

instead.

if((j%2)==(unsigned(m)%2))

is the easiest way to see if both have the same parity. Moving to unsigned aka mod 2^k is going to keep parity, and in unsigned %2 returns parity correctly (and not negative parity).

edited Jul 20 '17 at 18:55

answered Jul 20 '17 at 18:43

Yakk - Adam Nevraumont

262,606
27
330
524

1

As long as the result is correctly expressed, a good compiler should probably generate optimal code regardless of what you write, and readability is a matter of taste (I would not redundantly parenthesis arguments of `==`, for instance, but I would write ...`%2!=0` rather than rely on implicit conversion to `bool`). However I think a solution with just one `%` is preferable, like your first one. Also note that one can just write `if ((j+m)%2!=0)`, as the signed `m` gets converted to the unsigned type of the other operand `j` automatically, but an explicit cast does make this more explicit. – Marc van Leeuwen Jul 21 '17 at 04:49
1

The result of the cast you describe in your first paragraph is implementation-defined, not undefined. (In both C and C++) – M.M Jul 21 '17 at 05:39
You probably want to take a look at `std::make_unsigned` for maximum generality. – Deduplicator Jul 21 '17 at 08:41

plats1 · Answer 5 · 2017-07-20T19:57:57.770

6

Don't be too smart

Do either of these run into problems?

if(!(j%2)!=!(m%2))
if(bool(j%2)!=bool(j%2))

One problem I see is readability. It might not be obvious to someone else (or your future self) what it is supposed to do or what it actually does.

You could be more expressive by spending some extra lines:

#include <cmath>

const bool fooIsEven = foo % 2 == 0;
const bool barIsEven = std::abs(bar) % 2 == 0;
if (fooIsEven == barIsEven)
{
  // ...
}

Also consider implementing a properly named function that provides a comparison of the parity of two given integral types. This not only cleans your code up but also prevents you from repeating yourself.

Edit: Replaced cast by call to std::abs

edited Jul 20 '17 at 19:57

answered Jul 20 '17 at 19:41

plats1

920
7
9

1

What is `std::abs(INT_MIN)` ? The advantage of the cast is that it actually works. – Ben Voigt Jul 20 '17 at 20:03
@Ben Voigt - Good point. Thanks for pointing it out. According to cppreference.com: "In 2's complement systems, the absolute value of the most-negative value is out of range, e.g. for 32-bit 2's complement type int, INT_MIN is -2147483648, but the would-be result 2147483648 is greater than INT_MAX, which is 2147483647." – plats1 Jul 20 '17 at 20:08
1

This is one those cases where `%` generates horrible code for signed integers because the sign is preserved in the result: https://godbolt.org/g/YSSARf – Maxim Egorushkin Jul 20 '17 at 20:29
1

@MaximEgorushkin I'm sorry, overflow of a signed integer does not guarantee the sign is preserved, unless you specify the compiler and provide the guarantees it gives; the result is in general undefined behavior. – Yakk - Adam Nevraumont Jul 20 '17 at 21:49
@Yakk Does it overflow in `i % 2`? – Maxim Egorushkin Jul 20 '17 at 21:55
@MaximEgorushkin in `std::abs(bar)`. What does that return when passed `MIN_INT`? – Yakk - Adam Nevraumont Jul 21 '17 at 00:36
@Yakk I never mentioned `abs`, neither it is in my code example, not sure why you are addressing the comment to me. – Maxim Egorushkin Jul 21 '17 at 09:24
@MaximEgorushkin I suppose I confused you for the person who posted this answer. Sorry! – Yakk - Adam Nevraumont Jul 21 '17 at 13:18
@Yakk: The sign of the result of a modulo was implementation-defined in C++03, not UB. And now the Standard has defined it. – Ben Voigt Jul 21 '17 at 14:43
1

Why do you need `std::abs(bar)` in order to mod? If you're checking against 0, the original sign of `bar` shouldn't matter, should it? – Brian J Jul 21 '17 at 15:19

score -1 · Answer 6 · answered Jul 20 '17 at 19:43

-1

This can be simplified:

if(!(j%2)!=!(m%2))
if(bool(j%2)!=bool(j%2))

to:

if ((abs(m) % 2) != (j % 2))

be sure to include the math.h

#include <math.h>

Absolute value will take away the sign bit which is the left-most bit in storage.

Converting signed to unsigned is okay, and is defined in C99.

Found this resource.

Bitwise operators also should work with a C99 compiler, and the signed having a lesser max value is converted to greater (signed to unsigned).

answered Jul 20 '17 at 19:43

Jordan Jelinek

136
2
9

1

The C++ way is to use the `` (or `` in this case) library instead of ``. – plats1 Jul 20 '17 at 19:53
1

`abs(int)` returns an `int`. negative `int`s which do not have a positive representation are permitted. Overflow of an `int` is undefined behavior. Can you document that `abs(int)` on `INT_MIN` is defined behavior and produces the result we want? – Yakk - Adam Nevraumont Jul 20 '17 at 21:50
Since this is a C++ answer, do *not* include only ``. You will get only the `double abs(double)` overload of `abs`. Anyway, since it turns out there are better answers that are portably safe, `abs` is a bad solution for this problem (for performance reasons if nothing else). – Peter Cordes Jul 22 '17 at 06:25

Finding whether a signed and an unsigned integer are both even or both odd

6 Answers6

Don't be too smart