Fast midpoint between two integers without overflow | Hacker News Reader

Fast midpoint between two integers without overflow

lemire.me

230 pointsibobev214 comments

Regarding the identity, XOR is a kind of addition, without carry.

    101
  ^ 011
  -----
  = 110

We added 1 + 1, to get 10. We put down a 0, but didn't carry the 1.

The carry is separately calculated using AND:

    101
  & 011
  -----
    001  <- carry out from LSB.

Of course the carry is carried so we have to shift it left: 010. We can just add the carry afterward (using regular addition which will propagate additional carries not calculated by the AND, like the one from the second digit.

Thus the identity:

  (a+b) = (a^b) + 2*(a&b).

This works only for non-negative integers, right? If there's a sign bit, that won't work right with XOR, if one operand is negative then the sign bit comes out negative.

If they're expressed in two's complement, this works for negative numbers as well.

Duh, of course that's how multiplication works. If one operand is negative, so will be the sign bit of the result. If both are negative, then the result should be and does come out positive, as the sign bit XORs to 0 and so do all adjacent bits that are 1 in both operands.

If I ever create a programming language, one thing I'd like to try is to promote integer operations to larger types, so there is never overflow. For example, if a and b are int16, then a+b is int17, and (a+b)/2 is int16 again.

In practice you'd store them in the next larger integer, so 32 bits for a 17 bit int. If you really want to cut off bits or overflow, you use a cast or modulo.

It seems really weird that the "correct" way to do this calculation is to resort to bit manipulation (which should be an implementation detail IMO).

So, this is basically what dynamic languages do because they _can_ go back an allocate more memory transparently to the developer. However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations. In fact, this would likely mean that all numbers must be heap allocated, which will likely be a performance penalty when working in high-performance systems. In these cases, using an algorithm that produces correct results without error with constant memory usage is preferred.

This should be possible for static languages? Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the stack for the result of the operation.

I'm curious which dynamic language reallocates to store larger integers? All of the dynamic languages that I'm familiar with simply store numbers as doubles, with variable width integers being handled by opt-in types.

But if you do this in a static language you’d quickly run out of space anyway.

Say you start with two Int16’s. Any addition would result in an Int17. Adding a pair of those together would result in an Int18, and so forth.

You’d blow past Int64 in no time.

I'm pretty sure their intent was to demote the value back to an int16 after completing the midpoint operation.

> You’d blow past Int64 in no time.

Not really. You only need to preserve according to the msb of each number. If you are adding 0(Int18)+1(Int18), you don't need 1(Int36) anymore than you need 1(Int18) or even 1(Int1).

But you don't know the MSB at compile time in the general case.

> If you are adding 0(Int18)+1(Int18), you don't need 1(Int36)

No, you’d need an Int19. We were talking about statically typed languages, so you need to decide the type at compile-time. If you add two UInt16’s they could both contain up to 0xFFFF, you need 17 bits to store that answer. Basically, with every addition you need 1 more bit than the largest of the two (types, not values) you are adding together to prevent a potential overflow. It’s even worse for multiplication.

Couldn't you have a constraining operation in there to assert that you have enough bits? You are right that we don't know if `a + b` would need more bits than either a or b. However, we could have an assert that allows us to ensure the static constraints are satisfied. And the type system could be used as a place to know where we haven't checked the constraint.

(Note that I'm not too clear how valuable this would be. Just asking why that isn't a valid path.)

> No, you’d need an Int19.

No, that's completely false. You don't need an Int19 but an Int1.

How do you figure that you can store the result of adding 2 Int18s in an Int1 ? Remember, we’re talking about static types and you don’t know the values at compile time.

Static languages can have types which have an unboxed value part (of fixed size) that manages a boxed heap part.

  class bignum {
  private:
    digit_t *limbs;
  public:
    bignum(int val);
    ~bignum();
    bignum operator +(const bignum &rhs);
    ...
  };

> Since the width of the operands are known ahead of time

Not so for loops and accumulator constructs.

I think it would be reasonable to also have overflowing and checked versions of the operators, for cases where the compiler can't guarantee the size (e.g. mutable variables in loops).

> Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the stack for the result of the operation.

What is the width of `i` in:

    foo(int count) {
      int i = 0;
      for (int j = 0; j < count; j++) {
        i = i + i;
      }
    }

You probably want i=1 since i=0 is an answer you can predict:

i = 0 implies that i = 0 + 0 = 0; so the loop doesn’t evolve, and the whole thing can be optimized to just i = 0.

For i=1, the loop simplifies to 2^count and a count-length type, which is the point I think you wanted.

Heh, oops, yes. :)

Python, common lisp, and perl for starters.

Also scheme and prolog

The problem you can then run into is that a mathematical operation can OOM

I've not seen this in practice.

You need some numeric accident involving a higher power operator like exponentiation.

In TXR Lisp I made exponentiation n-ary: you can do (expt x y z ...).

The associativity is right to left: it means

rather than the less useful cumulative exponentiation of the same base:

  yz...
 x

which can easily be obtained as (expt x (* y z ..)).

So, anyway, if you apply expt to small list of small operands, you can cons up a big number in rather a hurry.

If it is important to prevent a problem like this, a limit can be imposed on bignums (say, large enough for common cryptography to still work).

I didn't know python could do that, that's pretty cool.

I gotta disagree on perl, though, even though it can represent numbers outside of the range of a double, it can't manipulate them without converting them into doubles.

“use bignum;” and you can.

The result of any expression would still be assigned to a variable or function parameter that has a defined type, so it would be limited to that size. However, intermediate values could automatically use larger registers, the CPU's carry flag, or some other mechanism to expand the range.

It would be desirable that every expression either produces the mathematically correct result, or a runtime exception.

In many cases it would be easy for the compiler to limit intermediate results to some number of bits (since it knows the maximum allowed range for the final result), but it may be a problem to guarantee this.

> However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations.

That is false; a static language could have bignum integers. E.g. you can easily have a bignum class in C++, which is static.

You can't have a variable-length bignum as an unboxed value type.

"Language with unboxed value types" and "statically typed language" are separate, somewhat related concepts.

They're right that this would require additional allocations though, no?

As you indicate though there's no need for this to be something the user of the type needs to think about.

Haskell is both compiled and has arbitrarily large integers. Granted, Haskell isn't used for high performance systems, but it can be used to generate programs for high performance systems.

You might not want that unconditional promotion in a systems programming language.

The problem in C that you can avoid is not taking into account the destination type of a calculation.

If you have in16 + int16, being assigned, returned or passed to a int32 type, then the calculation can be done in int32.

If the result is going back to an int16 type, then there is no need to go to int32.

In C expressions, the types are almost purely synthesized attributes: what that term means is that the information flows up the abstract syntax tree from the children to the parents. in a = b + c, the type of (b + c) is determined without regard for the parent = node. This is very simple and has the benefit of being not only easy to understand but in some ways referentially transparent: when we move (b + c) elsewhere, it retains its meaning (except for the part of what happens to the resulting value in the new context). More sophisticated rules can reduce errors though.

> If you have in16 + int16, being assigned, returned or passed to a int32 type, then the calculation can be done in int32.

By the way, if int has 16 bits (which is rare nowadays), then the calculation will happen in 16 bits. If int has more than 16 bits, then both operands will be promoted to that size before the operation.

The correct way most people would write this for positive integers is:

if (a < b)

  return a + (b - a) / 2;

else

  return b + (a - b) / 2;

This method is just more efficient (for places where it matters) as it avoids divisions and branches. But for a vast, vast majority of use-case that tiny efficiency gain doesn’t really matter.

Is that the right way around? If `a<b` then `a-b` will be negative, surely, and adding that to `a` will be moving down from `a`, not from `a` to `b`?

cf https://go.dev/play/p/SgdWzzqDygn

Eh, that’s what I get for writing code on a cell phone. Fixed.

Wouldn't this still overflow when one of the values is positive, the other is negative, and their difference is sufficiently large?

The tweet said unsigned ints

Tweet? But yes, sorry, I missed that your post said positive ints. The article was about signed ints, though.

Oh, you are right. For some reason I thought I saw unsigned in there.

C promotion rules can can convert unsigned to signed and vice versa so it still matters.

It can be rewritten without the test:

    return a - (a - b) / 2;

Tweet said unsigned ints, so don’t think this would work. Even with signed I think this can overflow.

> Tweet said unsigned ints

Which tweet?

you can also do

min(a,b) + (max(a,b) - min(a,b))>>1

It seems like if you did this you would need special syntax for accumulators and loops; there you cannot (necessarily) use static analysis to determine the proper types.

Amongst the many other dynamic languages that did this, Smalltalk was also one of them. Smalltalk took it a bit farther though. Python/Erlang will turn integer division (unbounded or optimized) into a floating point result.

Smalltalk had first class fraction objects as part of it's transcendental number system. There's a great story about Dan Ingalls changing one line of code to make all of the original Smalltalk BitBlt transparently work with fractions. I always miss having fractions as part of the transcendental math experience in "very high level languages".

The downside of these approaches, is that you can optimize some paths so that things stay relatively quick, but other paths will really slow down all of a sudden.

For example, in Smalltalk,

    16r7FFFFFFF timesRepeat: [ self fastOp ]

would allow you to do a microbenchmark on a fast operation. But if you moved to

    16r7FFFFFFF + 1 timesRepeat: [ self fastOp ]

would suddenly cause your benchmark to take 30x+ longer, because you had tripped from immediate tagged integer format to integer-as-an-object representation.

Python integer division (//) will always return an integer. Proper division of two integers with / will return a float, not an exact rational (except when the float can represent it).

In addition to what everyone else has said, that would presumably prevent you from writing statements like "a++" or "a += 1" - instead you'd have to write "a = (a + 1) as u8", which seems like it would get very tedious, even if it is much clearer that it could overflow.

In the proposed language (which isn't C!), that should produce an exception on overflow.

If you wanted it to wrap around, you could use an expression like "a = (a+1) % 256", or maybe something like Ada's modular types.

It wouldn't produce an exception, it would not compile. The nice thing is that you can avoid range checking at runtime.

Exactly, Ada's modular types would be a good option in this case, if that is what you want (my feeling is, most likely not unless you are doing some low level stuff). An alternative would be to rewrite the for loop in a functional or range based style.

In algorithmic code, you almost never want overflow. If you have a little function to calculate something, you want the intermediate variables to be big enough to perform the calculation, and in the end you cast it down to the size needed (maybe the compiler can do it, but maybe you know from some mathematical principles that the number is in a certain range and do it manually). In any case, I would want to be warned by the compiler if I am:

1. loosing precision

2. performing a wrong calculation (overflowing)

3. accidentially loosing performance (using bignums when avoidable)

1 and 2 can happen in C if you are not careful. 3 could theoretically happen in Python I guess, but it handles the transition int <-> bignum transparently good enough so it was never an issue for me.

> It wouldn't produce an exception, it would not compile. The nice thing is that you can avoid range checking at runtime.

You're proposing a language where you cannot increment integers? I don't think that would be a very popular language.

You could increment integers so long as you make it clear what you will do in the overflow case. Either use bigints with no overflow, specify that you do in fact want modular behavior, or specify what you want to do when your fixed width int overflows upon increment. That seems eminently sensible, instead of having overflow just sit around as a silent gotcha enabled by default everywhere.

Swift (https://docs.swift.org/swift-book/LanguageGuide/AdvancedOper...) uses

  a = a &+ 1

or the shorthand

  a &+= 1

IMO, that looks ugly, but that probably is a matter of getting used to it.

Compared to the %256 option, it has the advantage that, if you change the type of a, you won’t have to remember to change the modulus.

They also chose to not make modular integers separate types. That makes mixing ‘normal’ and modular arithmetic on integers easier (with modular types, you’d have to convert between regular and modular integers all the time) (edit: that also is consistent with the fact that the bitwise operators work with regular ints, and ook not require a special “set of 8/16/32/…” type that’s implemented as an integer)

I wouldn’t know how common such mixing is and, hence, whether that is a good choice.

Rust has a collection of wrapping functions to cover this case, e.g.

    a = b.wrapping_add(c);

I find this much clearer than any implicit or sigil-denoted behavior.

The amount of cryptography that relies on overflows is amazing and annoying when trying to implement it in a language/framework that doesn’t overflow.

The boost safe_numerics library (c++) has support for this (up to a point), in addition to detecting overflow at compile or run time.

> If I ever create a programming language, one thing I'd like to try is to promote integer operations to larger types, so there is never overflow.

Are there any languages other than Lisp and Python that have automatic bignum support?

Pike, Haskell.

Clojure makes a gesture toward it, literals are automatically promoted but the normal operators don't do it:

  user=> (+ 1 9223372036854775807) ;; max signed int64
  Execution error (ArithmeticException) at user/eval5 (REPL:1).
  integer overflow
  user=> (+ 1 9223372036854775808) ;; one higher

9223372036854775809N

Tcl. In tclsh:

  % expr 1 + 9223372036854775807
  9223372036854775808
  % expr 9223372036854775808 + 1
  9223372036854775809

Dart initially had it, but JS compatibility was more important.

However they don't have JS compatibility either (Dart does not round off large integers like JS does), so I forget what the point was.

Dart also (very early) had infinite precision fractions. So if you divided 355 by 113 you didn't get 3 or 3.1415... you got the fraction 355/133 which was an instance of a first class numeric type.

Unfortunately this means your numbers can grow to need arbitrary amounts of storage in loops.

Commonlisp has rationals as well (355/133) though division doesn't generate them by default.

Erlang's got them, I'm pretty sure.

Yep, integers on the BEAM are unbounded, since the language was built with "This program will run forever" as a design concern. Indices capping out and causing crashes was not an acceptable state of affairs.

Ruby's Integer type works like BigInteger under the hood.

The issue with this type of promotion is that you usually want to preserve the type. Like if I add two int32s, I probably want an int32 as a result.

A cooler feature would be requiring the compiler to prove the addition wouldn’t overflow.

> A cooler feature would be requiring the compiler to prove the addition wouldn’t overflow.

Wuffs is specialized enough to do exactly that (https://github.com/google/wuffs).

Many dynamic languages (e.g. Python, Clojure) do some variation of promoting numbers to larger types, usually not in small increments (keeping track of how many bits the number is probably adds an unreasonable overhead) but in large increments and ultimately promoting to an arbitrary precision int, a rational, or a BigDecimal. The people I know who are messing around with 5-bit ints and other irregular types are doing it with FPGAs where it unambiguously saves resources as opposed to costing them.

You eventually need bigints for that, and thus trade off performance against the no-overflow guarantee.

What do you do when operating on the largest int type available?

Maybe spit out a warning and use bignums? You are then supposed to explicitly narrow the type, or explicitly opt into using bignums.

What do you do when incrementing (or adding to) an integer in a loop? You’d need sophisticated analysis to determine that the overall sum will always fit into a specific type, or otherwise you’d end up with bigints all the time.

You wouldn't modify an integer in place. At least it wouldn't be idiomatic. Quite a few languages, especially functional, have that constraint. You can always do range-based-for:

    for i in [0, 100]:
        // i is known to be in [0, 100]
        // the argument is known to be in [0, 200]
        do_something(i*2)

If you really want unbounded growth, you need a bignum. If you want to be bounded in size but not in time, you have to specify overflow behavior. Something like (ugly pseudocode):

    integer[modulo 256] a = 0;
    while some_condition:
        a += 1

    integer[0, 1000] b = 0;
    while some_condition:
        guard if b < 999:
            // b is now in [0, 999]
            b += 1

The whole point is, forcing you to make your mind up about overflow behavior (and not just using int32 or int all the time and hoping i is going to be "small").

Isn't uint8 exactly what your 'integer[modulo 256]' is? And for unbounded you do need bignum and dynamic allocation so I'm not sure I see any benefits to explicitely fine-graining the range instead of using machine word at all times and bignums when needed

> Isn't uint8 exactly what your 'integer[modulo 256]' is

In c/c++ it is. Obviously some other languages would disagree.

I think a better example of what GP is thinking about is Rust's approach, where overflowing an u8 panics (in debug builds), but you can do x.wrapping_add(y), x.saturating_add(y), x.checked_add(y) etc., depending on what you want to happen when the operation overflows.

Yes. My point is, you’d need that ranged-based static analysis, and probably (judging from how interval arithmetic usually turns out) you’d need bigints much more frequently than they are currently used.

If you're expecting arithmetic to work not modularly, you do need to either verify that there can never be an overflow or use bignums. Otherwise you have a bug.

Don't have a largest int type?!

We live in a universe where infinite computer memory is not (yet) possible. Your CPU registers can only be so big.

A smart compiler might recognize cases where a finite number of types suffice, and reject programs where no such bound can be deduced.

if you're going that far, why bother with a "next largest" that's more than 1 byte larger? If you're just using it for intermediate values, just uplift that int16 to an int24, or that int64 to an int72, they're only there for as long as the LHS/RHS needs to evaluate: they're not getting stored, no need to use double the memory allocation.

What type do I get if I'm multiply four int32s?

It should fit in 128 bits or in the range of [-2^128,2^128] (tiny bit narrower since max and min int32 are asymmetric). The question is what type do you want? Do you want the full result? Or do you want it to be modulo something? Or are you sure that the numbers are small, but just kept in int32 storage for some other reason?

The compiler could use static analysis to keep the size to a minimum, for example in this case:

    int32 a
    int32 b = 2
    var c = a * b

it would know that c just needs 33 bits.

How many bits is x/y?

Assuming x and y are 32-bit integers

33-bits? INT_MIN / -1 = INT_MAX + 1.

and what is 3int16? nint16? you want to have an own calculation system about sizes in your calculations? Either go straight just unbounded ints like some languages (e.g. Python) already do, or nothing.. and it comes with a cost.

Pascal does something like that.

But it only goes up to 64-bit, then you get overflow again

IIRC Dart 1 did this, and it was abandoned due to binary size issues.

Very much relevant:

CppCon 2019: Marshall Clow “std::midpoint? How Hard Could it Be?”

https://www.youtube.com/watch?v=sBtAGxBh-XI

This is an excellent interview question (I used it a lot). Reveals what the candidate knows about how the computers work. 90-95% of engineers don't even see a problem with (a + b) / 2 until you tell them about the overflow, let alone find a solution for it.

The majority of programmers have no idea what an int is in their favorite language and what its range is (roughly).

Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong.

And so on and so forth, with this question you can uncover layers upon layers of trivial (non-)knowledge.

I wonder.

IMHE this is the kind of edge that you know only because you've been bitten by a bug once.

It's the same with floating point numbers. You may know that the representation is not absolute, that you can end up with NaN. But I found that I only knew it viscerally after I banged my head on bugs related to these.

Of course, that could be provided by Comp Sci ou Comp Eng curriculum, but time is finite...

In the 5-10% of engineers who saw the problem, how many had experienced it once themselves before?

It's not just about seeing the problem but also knowing what you are dealing with. The majority of engineers or whoever call themselves engineers, don't know what an int is. Some Java programmers I interviewed years ago think the range of an the int type is, I quote "256", or "65 thousand-something", these were literal answers. Let alone it's not even a range!

So you are an Android engineer and you deal with ints a lot. Screen coordinates are ints on Android, so if you think the range of an int is "256" how do you think your app works at all?

This question reveals to me one of the most important things I'm usually looking for when hiring: natural curiosity. A software engineer should be curious about things he or she is dealing with. And that starts with the most trivial things like "what is an int really?" and then moves on to other concepts like: under the hood, what is a function?, what is a virtual method? what does `await` really do? And so on.

A good engineer should know how the computers work, and I don't know why this should be even questioned.

> think the range of an the int type is, I quote [...] "65 thousand-something"

Whether or not this is a completely ludicrous answer depends entirely on how you presented the question (i.e. whether or not it was clear that you're talking about java instead of asking a more general question).

For example, in C, the int type can be as low as 16 bits in size, yielding "65 thousand-something" possible values in the worst case. So that could be a reasonable answer as the guaranteed range of values for an int. And even in an android interview, C(++) can conceivably be the assumed context if the previous questions have been NDK-related.

> Let alone it's not even a range!

I feel like it's not a particularly uncommon shorthand to refer to the extent of a range of values that something can take as "the range" of that something.

> in C, the int type can be as low as 16 bits in size, yielding "65 thousand-something"

Wrong both for worst-case C and for "16 bits in size": the actual maximum is "32 thousand-something" (specifically 32767 in 2s-complement and also in most of the stupid representations (like 1s-complement or sign-magnitude), although there might be some that have, eg, 32768). They also have a minimum of -32768 (or -32767 or otherwise for some of the stupid representations).

You could intepret it as "65 thousand-something" values between the minimum and maximum, but that strongly implies that the minimum doesn't need to be specified, which only works for unsigned integers (which C int is very much not).

The question was: what is the range of possible values of the int type in Java? (In the context of finding the middle problem)

"256" is a ridiculously bad answer on multiple levels. Believe me, I heard it from more than one Java developer with a CS degree and at least 5 years of experience at the time.

> A good engineer should know how the computers work, and I don't know why this should be even questioned.

I am not disputing this point, I agree with it.

I am saying there is a difference between knowing int can overflow or knowing that floating point numbers are imprecise, and being attentive when you read `a + b` or `a == b` with float. I believe only experience can teach that (such experience may or should be provided by school).

It's the kind of edge case I know because I just read the article...and it's probably bad if you've been bitten and that bite is still driving how you handle this case.

Because while it is easy to be bitten by this on at 16 or 32 bits, if it happens at 64 bits (1.8446744e+19) it's almost certainly an abstraction error like arithmetic on identifiers rather than values.

Back around 2010, I wrote some code for the first time in a very long time and that code initialized a 10,000 integer array and my first thought was "that's too big to work." Kilobyte thinking in a gigabyte future.

To a first approximation, as an interview question it fights the last war...again embedded systems excepted.

So what sort of answer do you find satisfactory? It seems like the "right" solution is non-trivial bit twiddling, do you expect people to come up with that, or stop sooner than that?

People rarely come up with a working solution within 30 minutes. Any solution is good as long as it doesn't overflow (there are a few suboptimal ones). But the point of this question is, again, to understand what they know about how the computers work.

Can you provide an example of a solution that someone without prior exposure could come up under 30 minutes? I'm having a hard time coming up with something that is not a monstrocity full of if s.

Perhaps the bar is not as high as you think. Coming up with a solution that has lots of ifs in will still put you at the high end of the interview distribution. Discussing intelligently with the interviewer why it's not great and how it can be improved is a lot better than not coming up with an answer at all.

One of the solutions I came up with back in the day, without googling was this:

    int avg(int a, int b) {
        if ((a < 0) != (b < 0)) // not the same sign?
            return (a + b) / 2;
        else
            return a + (b - a) / 2;
    }

It’s tricky.

This will round (-2,-1) to -2, i.e. away from zero. For comparison, if we perform the canonical (a+b)/2 instead it will round to -1, i.e. towards zero.

Now, the problem statement does not tell us how to round, so you’re technically correct, but the inconsistency bothers me.

min + (max - min) / 2

Edit: never mind, this can overflow too

Fortunately the cases where this might overflow (a and b have opposite sign) are precisely the cases where the naive (a+b)/2 is guaranteed to work. So put them together to get a suboptimal but perfectly fine solution.

What sort of role is it for?

I'm asking as I doubt "know about how computers work" is necessary for most tech roles.

I get it, having technical expertise is important, but still ...

> This is an excellent interview question (I used it a lot).

Is it though? It just tells you if they know the trick or not. At that point you might as well have them fill out a form and use the score from that to hire/no hire.

It doesn't tell you if they understand what RAM is or storage (HDD/SSD/etc) or the various buses on a motherboard or pretty much anything about how a computer works. For the example given in the article, it's pretty rare for (a+b)/2 to overflow since the default ints end up being 32 bit (article calls out 64bit tbh) and your parameters are [-1000,1000].

---

> 90-95% of engineers don't even see a problem with (a + b) / 2 until you tell them about the overflow, let alone find a solution for it.

In my experience a similar percentage can't write a working DFS which I think is much more work related than midpoint.

My first real job was for a sdet position and I was asked how to test a function that takes 3 numbers representing lengths of sides of triangle, and determines whether the the numbers can form a possible triangle. E.g. (in python),

    def is_triangle(a, b, c) -> bool:
        ...etc...

One of the things an ideal candidate would realize is that the triangle inequality needs to apply (a + b >= c (for all permutations of a,b,c)), and that if a developer naively implemented the above via:

    if a + b < c:
        return false

it'd run into this exact problem.

I'd thought this question had gotten stale / overdone, but perhaps it's still a great interview question.

This is so fraught with problems.

First of all, doesn't it also need to have the condition (c > a - b)? Maybe you just left this part out?

Secondly, you're worried that (a + b) could overflow. The triangles in your applications are just THE MOST EXTREME! That's how cool your application is! You have the MOST EXTREME TRIANGLES!

But wait! When are you dealing with integer lengths of triangles? You never specified they were integers. In 99.99% of all real-world applications dealing with triangles, their coordinates are floating-point. I think it's fair to say overflow isn't nearly your biggest arithmetic problem with floating points -- rather, once you get to extreme (and extremely different) exponent values, you have all sorts of accuracy and loss issues, long before overflow becomes an issue. Do you expect the candidate to also handle the case where one side is 1e-155 and another is 1e274? Because otherwise their code is "wrong"!

So left unspecified, your "gotcha" is completely ridiculous and just a mind-reading trap to arbitrarily filter out people who don't think exactly (and erroneously) like you do!

Or maybe you did mean that the sides of the triangle are constrained to integer lengths? That would be extremely unusual, so you absolutely need to specify that. But if you're constraining the side lengths to integers, are you also constraining the vertex coordinates to integers? It would be extremely strange to require integer lengths but allow floating-point coordinates; but it would also be extremely strange to only allow integer coordinates, as most triangles with integer coordinates have a least one non-integer side length! And it doesn't sound like a trivial problem at all to find whether a given set of integer lengths could form a triangle on an integer lattice, but that seems to be what you maybe think you're asking? Do you even know what you're asking?

If integers are involved at all, it's far more likely that the coordinates are integers, but the side lengths are floating point.

What a tremendously awful interview question. I really hope your description is just extremely limited and flawed and mis-remembered, because if that's the actual question, you are perpetuating the "arbitrary leetcode interviews" problem that competent software engineers always complain about when they look for jobs.

> Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong.

Seems like you can cover the corner case easily enough:

    x/2 + y/2 + (x & y & 0x01)

A few more operations than the article though so not the most efficient solution.

> x/2 + y/2 + (x & y & 0x01)

This returns -1 for x = INT_MIN and y = INT_MAX were the answer should be 0 (for an example). so not a correct solution

Isn't (32 bit) INT_MAX 2^31-1 and INT_MIN -2^31, so this is an acceptable solution (since the decimal average is -0.5)?

> since the decimal average is -0.5

The C standard says: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded (This is often called ‘‘truncation toward zero’’).

So it should be 0 (as per C standard, not sure what C++ standard says)

The question is midpoint, not division, so that's irrelevant in the first place, and even if were division, the standard is wrong.

Per Google (suddenly I feel a need to make it clear I didn't use chat GPT)

  2^64 is 1.8446744e+19

To a first approximation, if your application is overflowing 64 bit integers, the problem is in the abstractions not sloppiness in low level details...something like doing arithmetic on IPv6 addresses.

What I mean is that it's one think if you specify a 32-bit or 16-bit architecture because the job entails low level programming with that constraint.

But entirely another think if it is used as a general test of software engineering skill because on the one hand, now I know the trick of the trick question and you wouldn't hire me based on my software engineering chops.

And on the other hand, in the vast majority of cases, the solution that might overflow is not just the simplest thing that might work, but it will also work well enough for the business purpose and be easier to support and maintain in the code base.

Finally, handling problems like this culturally during development and after-action debriefing is better healthier than how-many-golfballs at the interview stage...like I said, I know the answer.

Completely agreed. The statement "that function is wrong because it could overflow" is putting one potential edge case on a pedestal while ignoring all other considerations for why you might prefer one alternative over another. The vast majority of the code in most business applications can perform straight arithmetic on 64-bit ints without worrying too much about overflow -- you just never encounter numbers like 2^63, and only rarely encounter numbers that wouldn't fit in a 32-bit signed integer.

When you write a bit of code, you naturally have in mind the realistic range of values you'll be working with. Even if it's just within 4 orders of magnitude. You know whether you're dealing with thousands or quadrillions. In the extremely rare case it's the latter, then you start worrying about this. You just can't worry about being 10 orders of magnitude off in your assumptions all the time -- that's what Exceptions are for. Holy crap, this software is dealing with values ten orders of magnitude different than you programmed for!? Absolutely throw an exception in that case, because it requires a complete rewrite of that area of the code.

Yes, if you're writing midpoint in a language-standard math library, it should work for all possible inputs. But the point of looking at toy problems in software engineering blogs is to inform us how to write our much more complicated, much more domain-specific code, and these lessons just don't cleanly transfer into that world.

quadrillions

Just to pretend to be an engineer a bit longer, 64 bits still provides a few orders of magnitude of overflow headroom for integer subtraction, addition, and division.

Multiplication is another story and might come up if you’re rolling your own cryptography. But then you have two problems since 64bits isn’t big enough.

Or rather three since you are rolling your own cryptography.

I have a question for the interviewer, maybe a bit metaphysical: what should your function return when one parameter is zero and the other is 1?

Just need to define your behavior there. It similar to why languages choose which rounding method to use.

> Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong.

Why is that wrong?

It's mathematically correct, but integers use truncating (floor) division. So you can lose a fractional 0.5 from both a/2 and b/2, which would have added up to 1, and now your result is off by one from (a+b)/2.

In general, even with floating point numbers you can get different results by rounding implicitly or intentionally the intermediate values versus the end result.

If a=1 and b=1, the midpoint should be 1.

But in computing, assuming we are only dealing with integers, 1/2 == 0. So 1/2 + 1/2 returns 0.

The dev blog from Microsoft in a different comment covers this:

"This will be too low if the original addition contained a carry from bit 0 to bit 1, which happens if bit 0 is set in both of the terms, so we detect that case and make the necessary adjustment."

return (a / 2) + (b / 2) + (a & b & 1);

It's still wrong for signed integers if a/2 rounds towards zero. You need a>>1 and b>>1.

Maybe a little slower, but way more readable than the ones in the article.

If a & b are both odd, you end up rounding twice vs. 0 times if you take the sum first.

Because, assuming / means integer division, this would return 6 as the midpoint between 7 and 7.

If its a known issue then why don't compilers spit a warning?

You don't necessarily need that actually, there are carry flags that are set on overflow that you can check to get that extra bit of precision.

In Rust you can actually do this using the checked add/sub/etc methods. It's one of the things I really appreciate about the language. By default, it panics on overflow in debug builds. You have to use the wrapping variants to declare that's intentional.

How about:

  if a > b { 
    mid = (a-b)/2 
  } else { 
    mid = (b-a)/2 
  }

There must be a way to do it without the branch? edit: Yes, in the article, I'm an idiot.

    if a > b { 
      mid = (a-b)/2

That only avoids overflow on unsigned types (where it would be called wraparound) ...

The point of the midpoint calculation is to find the mid-index usually (e.g. binary search, quicksort). So a and b would be unsigned. You're right about signed integers though.

(a / 2) + (b / 2) + ((a % 2) + ((b % 2)) / 2) works and can be extended from 2 to n to find the average of a set of integers.

Note that this can equivalently[0] (and more readably) be written as `(a/2) + (b/2) + (a&b&1)`.

0: Assuming your language rounds integer division and modulo correctly, ie that `i%array_len` is reliably a valid array index. C has problems here when i (respectively: a or b) is signed, but that doesn't matter in the sensible case, where you always index everything with size_t.

It's good I guess if people use languages where it matters. Coming up with a real solution in C seems really annoying.

A bit more detailed look at it: https://devblogs.microsoft.com/oldnewthing/20220207-00/?p=10...

Joshua Bloch did a great post [1] on how nearly all standard library binary searches and mergesorts were broken (as of 2006) due to this exact issue. The punchline is that the bugs started cropping up when the need and capability to sort O(2^32) element arrays arose.

[1]: https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

  int mid(int x, int y) {
    return (x/2 + y/2) + (1 & x & y);
  }

would be a more readable solution

edit: Actually, this fails on mid(INT_MIN, INT_MAX) and possibly other mixed sign values (returns: -1, expected: 0 (or -1 is okay?), where the precise answer is -0.5)

more edit: The C standard says: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded (This is often called ‘‘truncation toward zero’’).

So -1/2 should be 0.

For signed ints, try

    (x >> 1) + (y >> 1) + (x & y & 1)

This rounds toward negative infinity. Also

    (x >> 1) + (y >> 1) + ((x | y) & 1)  // Rounds toward +Inf
    (x >> 1) + (y >> 1) + (x & 1)        // Rounds up if x is odd
    (x >> 1) + (y >> 1) + (y & 1)        // Rounds up if y is odd

I'd be curious if there's a bit-twiddling trick for rounding toward x or y.

Using the midpoint function is the most readable.

https://en.cppreference.com/w/cpp/numeric/midpoint

Though it's odd this allows overflow.

std::midpoint also seems to yield less efficient code with g++12 targeting x86-64: https://godbolt.org/z/j695ce98Y

std::midpoint does different thing in terms of rounding, therefore comparison is not fair.

Possibly true, but it yields less efficient code in GCC 12 for x86-64. https://godbolt.org/z/oafPrb4K8

Because it's also wrong! / rounds towards zero, while summing a&b&1 requires the division to round towards negative infinity.

There's an entire category of bit-twiddling methods for different operations.

They were developed by programmers at places like the AI labs at MIT and Stanford, in much earlier days of computing, when size and time constraints sounded much more in everyone's faces than today.

Relevant link: https://graphics.stanford.edu/~seander/bithacks.html

Also related: Quake III fast inverse square root[1].

[1]: https://github.com/id-Software/Quake-III-Arena/blob/master/c...

It's way older than Quake III: https://en.wikipedia.org/wiki/Fast_inverse_square_root

Many past discussions on HN: https://hn.algolia.com/?q=inverse+square+root

In the old days where programmers knew that everything computers did was AI.

IIUC, Marvin Minsky, at some early point in "AI", wanted to build it with computers as a method for understanding how the human mind works. I think Computer Science came a little later.

When I got into "AI", much later, coming from CS and software engineering thinking, "AI" seemed to be "things we currently think are hard for computers to do (and useful computational methods that we've already figured out)".

Now "AI" is getting different, and generalized AI is looking more plausibly attainable than it was shortly before DL. (Minsky thought it would happen quicker, and also speculated explosive growth of capability once the AI could teach and evolve itself.)

I've used

min(x, y)+( ((unsigned int)abs(x-y))>>1);

with no issue.

abs(x-y)is the distance between points x and y. We don't care about order here because of the absolute value. And by its nature, it will always be positive - hence unsigned.

We divide the distance between the points by 2. This always provides a solution that fits in the signed bounds of X and Y once you add to min(x,y).

And it costs an ABS, a subtract, a non-negative bitshift, and a min().

To make it more complete, a switch statement depending on type of input function would be needed to handle the various sizes of numbers. And then it'd be doing the same but for long int->unsigned long int etc.

Unfortunately abs(x-y) can overflow in two different ways.

The subtraction can overflow, e.g. INT_MIN - 1, or 0 - INT_MIN. The abs call can also overflow, with abs(INT_MIN). In both cases, the overflow causes undefined behaviour.

To calculate the difference between 2 signed integers we must bear in mind that the result may exceed INT_MAX, and must use unsigned int for the result. I wrote about this on StackOverflow: https://stackoverflow.com/q/10589559

How do you derive the identities mentioned at the bottom of the post?

The first one is already explained, a^b + 2*(a&b) is computing the sum and carry in parallel, and then adding them up.

The second formula is more elaborate, and makes heavy use of the above identity:

      2*(a|b)-(a^b)
    = 2*((a&b)^a^b)-(a^b) (express boolean or in terms of and and xor)
    = 2*(a&b) ^ 2*(a^b) - (a^b)
    = 2*(a&b) + 2*(a^b) - (a^b) (there can't be carries, so xor equals addition in this case)
    = 2*(a^b) + 4*(a&b) - 2*(a&b) - (a^b)
    = 2*((a^b) + 2*(a&b)) - 2*(a&b) - (a^b)
    = 2*(a+b) - (a+b)
    = a+b.

The first one is just the binary sum without carry (x xor y) and then adding the carries of that sum (x&y) shifted by 1 bit (2*(x&y)), still the addition of the carries can in turn produce carries, but that is taken care of by the normal "+" which is addition with carry.

That's correct, and here's a further illustration.

Consider adding two single bits, X and Y - you'll get the following sums, denoted in binary (column CM):

    X Y | CM
    ----+---
    0 0 | 00
    0 1 | 01
    1 0 | 01
    1 1 | 10

As you'll note, the M-bit is just XOR and the C-bit is AND (google "half-adder" if you're into hardware).

And as we remember from school, the carry (C-bit) always has to be added to the next column to the left, that's why we shift it by one bit (aka multiplication by 2).

I believe these follow from the definition of twos complement addition. Times 2 is just a left shift. So it's like a carry bit.

You can also do x + (y - x) / 2 (starting point + distance halved), that doesn't overflow, is easy to remember, and the compiler would probably optimize it further.

And wrong, since x=-1 and y=INT_MAX overflows.

Other comments point out that can overflow for some values.

However if you're doing mid-point in something like binary search where you already know y >= x AND x >= 0, then x + (y - x) / 2 is indeed a fine choice. It's a good one to remember.

This can overflow for signed integers.

Indeed this overflows too! Still don't have the rights here to edit or delete the comment, sorry for the confusion! It needs a couple of extra conditions: x and y need to be uint, and y needs to be >= x (you can swap them if they are not).

It's not a special right, you just have to do it within 2 hours.

The subtraction could overflow.

Why this could be better than (x+y)/2, since they both overflows?

x64 has a 9/17/33/65 bit rotate using the carry as the extra bit. So for unsigned ints should be 2 instructions IIRC. Something like

ADD a, b

RCR $1, a

10 months ago there was a long thread on a very similar topic, Finding the average of two unsigned integers without overflow.

https://news.ycombinator.com/item?id=30252263

The main problem with the naive solution is not the overflow, but the undefined behavior caused by it in C.

If overflows are allowed, like in Rust, you could implement this by representing X and y with two ints each and doing mini big integer arithmetic on them.

It is nice how math plus comp.sci keep on providing new solutions... Niiice!

Why not ...

  x, y = minmax(x, y)
  return x + (y - x) / 2;

?

There's branching involved in the minmax operation, so it'll always be slower than (x|y) - ((x^y)>>1).

    min = x^((y^x)&-(y<x));
    return min + ((y^x^min)-min)/2;

Still less efficient.

(-0x80000000, 0x7fffffff)

y - x overflows on y = INT_MAX and x = -1.

Shouldn't processors have a special instruction for this operation?

Rotate through carry works for that. (Maybe not on RISC-V, it’s kind of picky about things you can’t easily access in high-level languages.) Unsigned floored, x86:

  add eax, ebx
  rcr eax, 1

ARM:

  adds r0, r0, r1
  rrx r0, r0

I’d need to think a bit more to come up with a signed version.

>I’d need to think a bit more to come up with a signed version.

Invert the high bits, turning two's complement into biased format (0 = lowest negative number, 0xFF...F = highest positive number). Then do the add+rotate and convert the result back.

Those four integer instructions are generally quite fast already. So unless this operation is needed extremely often there is probably no point in dedicating hardware to it.

If you are on arm, I know you can basically do

  R3 = (r1 + r2) >> 2
  R3 = R3 + 0x1000 0000 0000 0000 if carry bit is set.

So should only be 2 instructions.

Although (a + b)/2 rounds towards 0, while the non-overflow solutions round up or down.

Why not just x/2 + y/2 ?

Assuming integer division, for x=3 and y=5 that would give 3, whereas the midpoint is 4.

Because the division is truncated twice, which increases the error. Take x=y=1, or x=y=3 for example.

x/2 + y/2 + (x & y & 1) should work.

That doesn't work when both are odd. For example, for x=1 and y=3 this gives 1 instead of 2.

1/2 + 3/2 + 1 = 0 + 1 + 1 = 2

Your final +1 is not in the expression by OP. You can get it by taking the correction term (x & y & 1) as mentioned in another comment.

woops, misread the indent-depth of the posts as reply, not to the same parent.

Because division is a slow operation. Even (x + y)/2 would be quicker

Division by 2 is one of the quickest operation. The correct implies 3 additions instead of one, so you go a point.

But y>>1 + x>>1 + (x & y & 1) is easier to remember than ((x^y)>>1) + (x&y).

Dividing by two is just a right shift.

Only if you are dealing with unsigned integers.

For signed integers, you need to be careful depending on the language you are using. Most languages provide a signed right shift that doesn’t lose the sign.

Personally, I think shift should always have been a bitwise operator, without sign extension. To me signed right shift feels as sensible as right shifting a floating point number - a shift is bitwise and not an arithmetical operator. But I guess that’s what comes from being brought up on healthy machine code by robots in the steel jungle.

C recommendation: “INT13-C. Use bitwise operators only on unsigned operands” https://wiki.sei.cmu.edu/confluence/plugins/servlet/mobile?c...

X+y can overflow which is what the post is saying.

  add x,y
  rcr x,1

To explain: The rcr instruction performs a right rotation and shifts the CF (carry flag) bit into the most significant position. Together with the preceding add instruction, this effectively provides an n+1 bit operation on n-bit registers.

This is correct for unsigned integers, but incorrect for signed.

For x=INT_MIN+1 (0b1000...1) y=INT_MAX (0b01111...1) this gives INT_MIN (0b1000...0) instead of 0.

You are correct, however most binary search algorithms wouldn't need negative numbers.

It is, however, the exact case shown in the linked article. "Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number."

You don't need a negative number to solve that fyi.

If the correct number is -300 you might

No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search.

I think in the unfortunate example question the binary search is from -1000 to +1000, but the question is not about binary search, it is about finding the midpoint between two numbers.

> No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search.

That's not true. Binary search doesn't map everything to a positive integer. You are incorrectly looking at the index offset, but the issue is determining the midpoint between two signed numbers.

It is being pedantic, but the issue is in the context of binary search:

Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number. With each guess, I tell you whether your guess is correct, smaller or larger than my number. A binary search algorithm tries to find a value in an interval by repeating finding the midpoint, using smaller and smaller intervals. You might start with 0, then use either -500 or 500 and so forth.

You don't need negative numbers to do this.... you can easily do it with only positive numbers.

It's a bit of a shame that programming languages above assembly don't expose the flag bits. Would be an interesting feature to explore for a "medium level language".

I believe that the reason is that high-level programming languages are meant to run on different types of CPUs and the flag implementations are different in different CPUs.

Have a look at https://github.com/wiz-lang/wiz. I agree that this in an unexplored area.

For a higher level language, one idea would be to automatically widen the result of operations, so for example adding two 32 bit integers would have a 33 bit result.

Since the expression will be eventually assigned to some variable or passed as a function parameter, it will have a limited range (and there should be an exception if that overflows), but intermediate results could be larger.

Is this just completely unfeasible, or just not done because "that's not how C does it"?

ChatGPT came up with this solution when I asked it to handle the overflow, and then asked it to be more efficient.

  // Calculates the midpoint of two 64-bit integers
  // and returns the result as a 64-bit integer.
  int64_t midpoint(int64_t a, int64_t b) {
    // Use the __int128 type to calculate the sum
    // of the two input numbers without overflowing.
    __int128 sum = (__int128) a + (__int128) b;

    // Shift the sum to the right by 1 bit to divide it by 2
    // and get the midpoint. This operation is equivalent to
    // sum / 2, but is more efficient because it uses a bit shift
    // operation instead of a division operation.
    int64_t midpoint = (int64_t) (sum >> 1);
    return midpoint;
  }

Yes, but that converts to 128 bits before doing the actual sum (maybe the compiler can still optimize that away?)

My idea was a better language where typecasts are never needed at all, because the compiler knows how the result will be used (in this example, returned as int64_t), and can produce whatever code is most efficient and either produces the correct result or a runtime exception.

edit: Also any non-toy compiler will optimize division by powers of two into a shift operation, so ChatGPT isn't being clever at all here, just repeating a common superstition.

ChatGPT knows better!

> ChatGPT isn't being clever at all here, just repeating a common superstition

Source:

  #include <stdint.h>

  int64_t midpoint_ChatGPT(int64_t a, int64_t b) {
      __int128 sum = (__int128) a + (__int128) b;

      // Shift the sum to the right by 1 bit to divide it by 2
      // and get the midpoint. This operation is equivalent to
      // sum / 2, but is more efficient because it uses a bit shift
      // operation instead of a division operation.
      int64_t midpoint = (int64_t) (sum >> 1);
      return midpoint;
  }

  int64_t midpoint_rep_lodsb(int64_t a, int64_t b) {
      __int128 sum = (__int128) a + (__int128) b;

      // Shifts are for the superstitious.
      int64_t midpoint = (int64_t) (sum / 2);
      return midpoint;
  }

Clang -O2 output:

  _midpoint_ChatGPT:
      pushq    %rbp
      movq    %rsp, %rbp
      movq    %rdi, %rcx
      sarq    $63, %rcx
      movq    %rsi, %rax
      sarq    $63, %rax
      addq    %rdi, %rsi
      adcq    %rcx, %rax
      shldq    $63, %rsi, %rax
      popq    %rbp
      retq

  _midpoint_rep_lodsb:
      pushq    %rbp
      movq    %rsp, %rbp
      movq    %rdi, %rcx
      sarq    $63, %rcx
      movq    %rsi, %rax
      sarq    $63, %rax
      addq    %rdi, %rsi
      adcq    %rcx, %rax
      movq    %rax, %rcx
      shrq    $63, %rcx
      addq    %rsi, %rcx
      adcq    $0, %rax
      shldq    $63, %rcx, %rax
      popq    %rbp
      retq

GCC -O2 output:

  midpoint_ChatGPT:
      endbr64
      movq    %rsi, %r8
      movq    %rdi, %rax
      sarq    $63, %rdi
      sarq    $63, %rsi
      movq    %rdi, %rdx
      addq    %r8, %rax
      adcq    %rsi, %rdx
      shrdq   $1, %rdx, %rax
      ret

  midpoint_rep_lodsb:
      endbr64
      movq    %rsi, %rcx
      movq    %rdi, %rax
      sarq    $63, %rdi
      sarq    $63, %rcx
      movq    %rdi, %rdx
      addq    %rax, %rsi
      movq    %rcx, %rdi
      adcq    %rdx, %rdi
      xorl    %edx, %edx
      movq    %rdi, %rcx
      shrq    $63, %rcx
      movq    %rcx, %rax
      addq    %rsi, %rax
      adcq    %rdi, %rdx
      shrdq   $1, %rdx, %rax
      ret

But all of these use a bit shift instead of the (I)DIV instruction. I wasn't saying compilers can't be stupid, but the AI-generated comment explicitly stated that the shift operation was more efficient than division, not that it would result in fewer instructions emitted.

    midpoint_rep_lodsb_handwritten:
        endbr64
        movq   $0x8000000000000000, %rax
        xorq   %rax, %rsi    ;convert two's complement to biased
        xorq   %rax, %rdi
        addq   %rsi, %rdi
        rcrq   $1, %rdi
        xorq   %rdi, %rax    ;convert back
        ret

(sorry if I got the syntax wrong, AT&T is just horrible)

The Hacker's Delight guy is insane.

Why wouldn’t you just shift them both right and add them?

Rounding error

https://news.ycombinator.com/item?id=33893153

Reply on news.ycombinator.com