How to divide an odd number to leave two integers?

Question

If I have an odd number, how would I divide it in two and leave two integers, with the first being one more than the second. For instance 9 would produce 5 and 4?

do you want the expressions to produce the correct answer if 1. the number is even (or will it never be needed?), and 2. if the number is negative? — gbulmer, Mar 23 '12 at 15:46

Fred Foo · Accepted Answer · 2012-03-23T16:32:52.723

17

The "smaller half" of int x is x/2. The "bigger half" is x/2 + x%2 or x - x/2.

Note that "smaller" and "bigger" refer to the absolute value, so in the case of negative x, bigger < smaller.

Of course, if x is always odd and positive, then x%2 will be 1 and the bigger half can also be computed as x/2 + 1.

edited Mar 23 '12 at 16:32

answered Mar 23 '12 at 15:40

Fred Foo

355,277
75
744
836

3

`x - x/2` would be somewhat simpler for the second part, given that you just calculated `x/2` ;-) – David Heffernan Mar 23 '12 at 15:41
@DavidHeffernan: good point, added it. I do believe that integer division on the x86 always produces the modulus in a register as well, so a smart compiler might optimize the `x%2` into a register access. – Fred Foo Mar 23 '12 at 15:42
Unlikely that performance is that relevant and you still have to perform an addition, just as per my version. – David Heffernan Mar 23 '12 at 15:48
@larsmans - integer division by 2 is a piece of cake for any decent compiler: this is just a shift right. No need of an integer `div`. – mouviciel Mar 23 '12 at 15:54
2

@mouviciel: "this is just a shift right" -- assuming an unsigned type. There's a little more to it for signed types because of round-towards-zero. In this example, we might know that the value will always be positive and so it doesn't matter, but if the compiler doesn't know that then it can't make that transformation even if it wants to. – Steve Jessop Mar 23 '12 at 15:57
1

@mouviciel for negative integers, `x / 2` and `x >> 1` are different – ouah Mar 23 '12 at 15:58
@Steve Jessop - I agree. nothing indicates that input should be unsigned. – mouviciel Mar 23 '12 at 16:05

mouviciel · Answer 2 · 2012-03-23T16:25:22.157

5

What about this?

int a = 9;
int c = a/2;
int b = a-c;

edited Mar 23 '12 at 16:25

answered Mar 23 '12 at 15:42

mouviciel

66,855
13
106
140

1

But if a is even, the result is not what is wanted. – Richard J. Ross III Mar 23 '12 at 15:42
4

@Richard Number is odd according to question. – David Heffernan Mar 23 '12 at 15:44
1

The spec indicates that a is odd. – mouviciel Mar 23 '12 at 15:45
@DavidHeffernan the question states `If I have an odd number`. So, the results should be `x / 2` if it's an even number. – Richard J. Ross III Mar 23 '12 at 15:45
3

@RichardJ.RossIII The question states that the input is odd. Read it again. – David Heffernan Mar 23 '12 at 15:46
The question I'm reading says "**If** I have an odd number..." which sounds like there is some possibility the number might be even. Besides, why bother using a solution that works *only* for odd numbers, when a solution that also works for even numbers is just as easy? – Brian Mar 23 '12 at 15:54
@Brian - I read: _If I have_ as: _Given the assumption that_. There is no spec about what to do if the input does not meet the spec. Maybe it is a critical error that needs a hard reset of the board. This is definitively something to be discussed with the client and not something that can be assumed by a developer. – mouviciel Mar 23 '12 at 15:58
I read the *if I have* as a spec as well, but this will not work for a negative odd number. – Fred Foo Mar 23 '12 at 16:20
@mouvicel, good point, but if failure on even numbers were part of the spec, it should be coded as a separate validation step. I like your answer as it is now because it is correct for all input, regardless of whether the spec currently considers that input to be valid. – Brian Mar 23 '12 at 17:43

Richard J. Ross III · Answer 3 · 2012-03-23T15:57:35.133

3

This would be my recommended way:

int low = floor(x / 2.0f);
int high = ceil(x / 2.0f);

I find it to be more concise than the x/2 + x%2 version. This version also benefits from the fact that the output will be correct if you happen to run it using an even number.

EDIT:

People seemed to complain about me using floating point for integers, well here is a completely bitwise based version:

int a = 9;

int b = a >> 1;
int c = b | (a & 0x1);

The only caveat with #2 is that if the input is negative, the results will not be what is expected.

edited Mar 23 '12 at 15:57

answered Mar 23 '12 at 15:42

Richard J. Ross III

55,009
24
135
201

2

-1 You use `floor` and `ceil` with floating point input. Your inputs are integers. – David Heffernan Mar 23 '12 at 15:45
@DavidHeffernan good point, fixed, now remove your down vote! – Richard J. Ross III Mar 23 '12 at 15:46
1

Not if that's the best asking you can do. And not if you insist on using floating point for a problem that should be performed purely with integer arithmetic. – David Heffernan Mar 23 '12 at 15:47
1

Integer arithmetic should not use `double` operations. What if the code is to be executed on an embedded microcontroller with no FPU and no `math.h`? – mouviciel Mar 23 '12 at 15:50
@DavidHeffernan floating point math isn't that slow these days, and not to mention the fact that the modulo operator can take quite some time to perform. – Richard J. Ross III Mar 23 '12 at 15:52
2

@RichardJ.RossIII I don't care about performance, it's just pointless to use FP math for the most trivial integer arithmetic imaginable. If I would never allow this code past code review. – David Heffernan Mar 23 '12 at 15:56
@DavidHeffernan alright, I updated my answer with a completely bitwise version of the operation. – Richard J. Ross III Mar 23 '12 at 16:02
3

Bit twiddling is even worse! Just use proper arithmetic operators for the love of god! This is the most trivial programming problem imaginable. – David Heffernan Mar 23 '12 at 16:06
@DavidHeffernan but I like bit twiddling, its fun! (and generally faster vs. the standard operators). – Richard J. Ross III Mar 23 '12 at 16:09
1

No, it is not faster. Not unless your compiler is rubbish. – David Heffernan Mar 23 '12 at 16:12

score 3 · Answer 4 · edited May 23 '17 at 12:00

For the folks who use microcontrollers, where / and % are fearsome-cost operations :-)

This shows an alternative method, using shift >> and & which are sometimes cheaper:

#include <stdio.h>

int main (int argc, const char * argv[]) {
    const int iplus = 9;
    const int iminus = -9;

    printf("iplus=%d iminus=%d\n", iplus, iminus);

    printf("(iplus >> 1)=%d ((iplus >> 1) + (iplus & 1))=%d\n", iplus >> 1, (iplus >> 1) + (iplus & 1));
    printf("(iminus >> 1)=%d ((iminus >> 1) + (iminus & 1))=%d\n", iminus >> 1, (iminus >> 1) + (iminus & 1));

    return 0;
}

Output:

iplus=9 iminus=-9
(iplus >> 1)=4 ((iplus >> 1) + (iplus & 1))=5
(iminus >> 1)=-5 ((iminus >> 1) + (iminus & 1))=-4

According to this Does either ANSI C or ISO C specify what -5 % 10 should be?

There is a difference of behaviour for / between C89 and C99, and specifically C89 '/ with one negative number may return a positive or negative result, but C99 is negative.

DeadlyChambers · Answer 5 · 2019-02-02T09:30:57.847

1

I thought the accepted answer was in the ballpark but unclear. If you want some copy and paste code this would be the best solution in my eyes

var number = 11;
var halfRoundedUp = (number % 2) ? number/2 + .5 : number/2;
var halfRoundedDown = (number % 2) ? number/2 - .5 : number/2;
alert(halfRoundedUp +" "+ halfRoundedDown);

edited Feb 02 '19 at 09:30

answered Aug 02 '14 at 19:19

DeadlyChambers

5,217
4
44
61

How to divide an odd number to leave two integers?

5 Answers5