[HN Gopher] Fast midpoint between two integers without overflow
___________________________________________________________________
Fast midpoint between two integers without overflow
Author : ibobev
Score : 200 points
Date : 2022-12-07 09:59 UTC (13 hours ago)
(HTM) web link (lemire.me)
(TXT) w3m dump (lemire.me)
| aimor wrote:
| Although (a + b)/2 rounds towards 0, while the non-overflow
| solutions round up or down.
| keepquestioning wrote:
| The Hacker's Delight guy is insane.
| zerr wrote:
| Why not just x/2 + y/2 ?
| adwn wrote:
| That doesn't work when both are odd. For example, for x=1 and
| y=3 this gives 1 instead of 2.
| someweirdperson wrote:
| 1/2 + 3/2 + 1 = 0 + 1 + 1 = 2
| rocqua wrote:
| 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.
| someweirdperson wrote:
| woops, misread the indent-depth of the posts as reply,
| not to the same parent.
| beardyw wrote:
| Because division is a slow operation. Even (x + y)/2 would be
| quicker
| secondcoming wrote:
| Dividing by two is just a right shift.
| robocat wrote:
| 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/plug
| ins/servlet/mobile?c...
| vlovich123 wrote:
| X+y can overflow which is what the post is saying.
| _ache_ wrote:
| 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).
| mredigonda wrote:
| Because the division is truncated twice, which increases the
| error. Take x=y=1, or x=y=3 for example.
| pajko wrote:
| Assuming integer division, for x=3 and y=5 that would give 3,
| whereas the midpoint is 4.
| _ache_ wrote:
| x/2 + y/2 + (x & y & 1) should work.
| notorandit wrote:
| It is nice how math plus comp.sci keep on providing new
| solutions... Niiice!
| captainmuon wrote:
| 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).
| andrewla wrote:
| 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.
| PaulHoule wrote:
| 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.
| ipsi wrote:
| 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.
| hota_mazi wrote:
| Rust has a collection of wrapping functions to cover this
| case, e.g. a = b.wrapping_add(c);
| wruza wrote:
| I find this much clearer than any implicit or sigil-denoted
| behavior.
| rep_lodsb wrote:
| 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.
| captainmuon wrote:
| 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.
| Sesse__ wrote:
| > 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.
| Chinjut wrote:
| 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.
| Someone wrote:
| 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.
| ardel95 wrote:
| 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.
| Chinjut wrote:
| Wouldn't this still overflow when one of the values is
| positive, the other is negative, and their difference is
| sufficiently large?
| ardel95 wrote:
| The tweet said unsigned ints
| Chinjut wrote:
| Tweet? But yes, sorry, I missed that your post said
| positive ints. The article was about signed ints, though.
| ardel95 wrote:
| Oh, you are right. For some reason I thought I saw
| unsigned in there.
| kevin_thibedeau wrote:
| C promotion rules can can convert unsigned to signed and
| vice versa so it still matters.
| noasaservice wrote:
| you can also do
|
| min(a,b) + (max(a,b) - min(a,b))>>1
| glxxyz wrote:
| It can be rewritten without the test:
| return a - (a - b) / 2;
| [deleted]
| ardel95 wrote:
| Tweet said unsigned ints, so don't think this would work.
| Even with signed I think this can overflow.
| glxxyz wrote:
| > Tweet said unsigned ints
|
| Which tweet?
| zimpenfish wrote:
| 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
| ardel95 wrote:
| Eh, that's what I get for writing code on a cell phone.
| Fixed.
| dahfizz wrote:
| What do you do when operating on the largest int type
| available?
| tromp wrote:
| Don't have a largest int type?!
| dahfizz wrote:
| We live in a universe where infinite computer memory is not
| (yet) possible. Your CPU registers can only be so big.
| tromp wrote:
| A smart compiler might recognize cases where a finite
| number of types suffice, and reject programs where no
| such bound can be deduced.
| captainmuon wrote:
| Maybe spit out a warning and use bignums? You are then
| supposed to explicitly narrow the type, or explicitly opt
| into using bignums.
| layer8 wrote:
| 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.
| thfuran wrote:
| 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.
| captainmuon wrote:
| 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
|
| or 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").
| ithinkso wrote:
| 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
| wongarsu wrote:
| > 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.
| layer8 wrote:
| 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.
| jefftk wrote:
| What type do I get if I'm multiply four int32s?
| captainmuon wrote:
| 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.
| dragontamer wrote:
| How many bits is x/y?
|
| Assuming x and y are 32-bit integers
| messe wrote:
| 33-bits? INT_MIN / -1 = INT_MAX + 1.
| HappySweeney wrote:
| IIRC Dart 1 did this, and it was abandoned due to binary size
| issues.
| halpmeh wrote:
| 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.
| Sesse__ wrote:
| > 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).
| usefulcat wrote:
| The boost safe_numerics library (c++) has support for this (up
| to a point), in addition to detecting overflow at compile or
| run time.
| travisgriggs wrote:
| 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.
| mkl wrote:
| 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).
| withinboredom wrote:
| 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.
| gumby wrote:
| > 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?
| fulafel wrote:
| 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
| eesmith wrote:
| Tcl. In tclsh: % expr 1 +
| 9223372036854775807 9223372036854775808 % expr
| 9223372036854775808 + 1 9223372036854775809
| ErikCorry wrote:
| 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.
| tudorpavel wrote:
| Ruby's Integer type works like BigInteger under the hood.
| arh68 wrote:
| Erlang's got them, I'm pretty sure.
| OkayPhysicist wrote:
| 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.
| TheRealPomax wrote:
| 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.
| layer8 wrote:
| You eventually need bigints for that, and thus trade off
| performance against the no-overflow guarantee.
| chewbacha wrote:
| 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.
| rep_lodsb wrote:
| 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.
| webstrand wrote:
| 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.
| andrewla wrote:
| > Since the width of the operands are known ahead of time
|
| Not so for loops and accumulator constructs.
| jcparkyn wrote:
| 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).
| Aaargh20318 wrote:
| 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.
| dekhn wrote:
| I'm pretty sure their intent was to demote the value back
| to an int16 after completing the midpoint operation.
| IncRnd wrote:
| > 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).
| tsimionescu wrote:
| But you don't know the MSB at compile time in the general
| case.
| Aaargh20318 wrote:
| > 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.
| taeric wrote:
| 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.)
| IncRnd wrote:
| > No, you'd need an Int19.
|
| No, that's completely false. You don't need an Int19 but
| an Int1.
| Aaargh20318 wrote:
| 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.
| munificent wrote:
| _> 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; } }
| zmgsabst wrote:
| 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.
| hansvm wrote:
| Python, common lisp, and perl for starters.
| webstrand wrote:
| 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.
| Sesse__ wrote:
| "use bignum;" and you can.
| pacaro wrote:
| Also scheme and prolog
|
| The problem you can then run into is that a mathematical
| operation can OOM
| PartiallyTyped wrote:
| 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.
| kazinator wrote:
| 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.
| w0mbat wrote:
| Why wouldn't you just shift them both right and add them?
| yccs27 wrote:
| Rounding error
|
| https://news.ycombinator.com/item?id=33893153
| rep_lodsb wrote:
| add x,y rcr x,1
| adwn wrote:
| 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.
| flohofwoe wrote:
| 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".
| gdprrrr wrote:
| Have a look at https://github.com/wiz-lang/wiz. I agree that
| this in an unexplored area.
| distcs wrote:
| 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.
| rep_lodsb wrote:
| 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"?
| flerchin wrote:
| 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; }
| rep_lodsb wrote:
| 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.
| jlokier wrote:
| 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
| rep_lodsb wrote:
| 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)
| [deleted]
| planede wrote:
| 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.
| rep_lodsb wrote:
| You are correct, however most binary search algorithms
| wouldn't need negative numbers.
| IncRnd wrote:
| 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."_
| roflyear wrote:
| You don't need a negative number to solve that fyi.
| anonymoushn wrote:
| If the correct number is -300 you might
| roflyear wrote:
| 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.
| IncRnd wrote:
| > 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.
| neilv wrote:
| 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.
| delta_p_delta_x wrote:
| Also related: Quake III fast inverse square root[1].
|
| [1]: https://github.com/id-Software/Quake-III-
| Arena/blob/master/c...
| mkl wrote:
| 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
| TonyTrapp wrote:
| Relevant link:
| https://graphics.stanford.edu/~seander/bithacks.html
| hgsgm wrote:
| In the old days where programmers knew that everything
| computers did was AI.
| neilv wrote:
| 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.)
| gilbetron wrote:
| A bit more detailed look at it:
| https://devblogs.microsoft.com/oldnewthing/20220207-00/?p=10...
| mredigonda wrote:
| 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.
| planede wrote:
| And wrong, since x=-1 and y=INT_MAX overflows.
| orlp wrote:
| This can overflow for signed integers.
| [deleted]
| mredigonda wrote:
| 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).
| mkl wrote:
| It's not a special right, you just have to do it within 2
| hours.
| phkahler wrote:
| The subtraction could overflow.
| jlokier wrote:
| 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.
| fyresala wrote:
| Why this could be better than (x+y)/2, since they both
| overflows?
| lpage wrote:
| 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...
| hgsgm wrote:
| mojuba wrote:
| 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.
| eloff wrote:
| 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.
| tromp wrote:
| if a > b { mid = (a-b)/2
|
| That only avoids overflow on unsigned types (where it would
| be called wraparound) ...
| eloff wrote:
| 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.
| lesuorac wrote:
| > 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.
| shkkmo wrote:
| (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.
| a1369209993 wrote:
| 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.
| naasking wrote:
| > 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.
| pksadiq wrote:
| > 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
| slymon99 wrote:
| 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)?
| pksadiq wrote:
| > 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)
| a1369209993 wrote:
| The question is midpoint, not division, so that's
| irrelevant in the first place, and even if were division,
| the standard is wrong.
| msluyter wrote:
| 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.
| feoren wrote:
| 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.
| robofanatic wrote:
| If its a known issue then why don't compilers spit a warning?
| heavenlyblue wrote:
| > 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?
| Jagerbizzle wrote:
| 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);
| nick4780167 wrote:
| Maybe a little slower, but way more readable than the ones
| in the article.
| bonzini wrote:
| It's still wrong for signed integers if a/2 rounds towards
| zero. You need a>>1 and b>>1.
| nathell wrote:
| Because, assuming / means integer division, this would return
| 6 as the midpoint between 7 and 7.
| stevoski wrote:
| 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.
| scajanus wrote:
| If a & b are both odd, you end up rounding twice vs. 0 times
| if you take the sum first.
| eloff wrote:
| 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.
| roflyear wrote:
| It's good I guess if people use languages where it matters.
| Coming up with a real solution in C seems really annoying.
| TacticalCoder wrote:
| 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?
| roflyear wrote:
| Just need to define your behavior there. It similar to why
| languages choose which rounding method to use.
| brudgers wrote:
| 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.
| feoren wrote:
| 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.
| brudgers wrote:
| _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.
| gjadi wrote:
| 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?
| mojuba wrote:
| 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.
| mostlylurks wrote:
| > 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.
| mojuba wrote:
| 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.
| a1369209993 wrote:
| > 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).
| brudgers wrote:
| 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.
| DenisM wrote:
| 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?
| mojuba wrote:
| 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.
| DenisM wrote:
| 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.
| ErikCorry wrote:
| 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.
| angrais wrote:
| 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 ...
| amelius wrote:
| Shouldn't processors have a special instruction for this
| operation?
| mananaysiempre wrote:
| 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.
| josefx wrote:
| 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.
| planede wrote:
| Very much relevant:
|
| CppCon 2019: Marshall Clow "std::midpoint? How Hard Could it Be?"
|
| https://www.youtube.com/watch?v=sBtAGxBh-XI
| Tyr42 wrote:
| 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.
| kazinator wrote:
| 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).
| vikingerik wrote:
| 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.
| gavinsyancey wrote:
| If they're expressed in two's complement, this works for
| negative numbers as well.
| gnull wrote:
| 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.
| noasaservice wrote:
| 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.
| [deleted]
| porkbrain wrote:
| Related: https://news.ycombinator.com/item?id=30252263
| marginalia_nu wrote:
| How do you derive the identities mentioned at the bottom of the
| post?
| [deleted]
| foota wrote:
| 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.
| ggrrhh_ta wrote:
| 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.
| kleiba wrote:
| 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).
| pbsd wrote:
| 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.
| [deleted]
| programmer_dude wrote:
| Why not ... x, y = minmax(x, y) return x +
| (y - x) / 2; ?
| lgeorget wrote:
| There's branching involved in the minmax operation, so it'll
| always be slower than (x|y) - ((x^y)>>1).
| scatters wrote:
| (-0x80000000, 0x7fffffff)
| harerazer wrote:
| y - x overflows on y = INT_MAX and x = -1.
| bonzini wrote:
| min = x^((y^x)&-(y<x)); return min + ((y^x^min)-min)/2;
|
| Still less efficient.
| pksadiq wrote:
| 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.
| nwellnhof wrote:
| 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.
| tiffanyh wrote:
| Using the midpoint function is the most readable.
|
| https://en.cppreference.com/w/cpp/numeric/midpoint
|
| Though it's odd this allows overflow.
| abainbridge wrote:
| std::midpoint also seems to yield less efficient code with
| g++12 targeting x86-64: https://godbolt.org/z/j695ce98Y
| abainbridge wrote:
| Possibly true, but it yields less efficient code in GCC 12 for
| x86-64. https://godbolt.org/z/oafPrb4K8
| bonzini wrote:
| Because it's also wrong! / rounds towards zero, while summing
| a&b&1 requires the division to round towards negative
| infinity.
| RenThraysk wrote:
| 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
___________________________________________________________________
(page generated 2022-12-07 23:01 UTC)