21 ms·
Fast midpoint between two integers without overflow
- notorandit 4y agoIt is nice how math plus comp.sci keep on providing new solutions... Niiice!
- porkbrain 4y agoRelated: https://news.ycombinator.com/item?id=30252263 https://news.ycombinator.com/item?id=30252263
- marginalia_nu 4y agoHow do you derive the identities mentioned at the bottom of the post?
- deleted 4y ago[deleted]
- foota 4y agoI 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 4y agoThe 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 4y agoThat'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 4y agoThe 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 4y ago[deleted]
- zerr 4y agoWhy not just x/2 + y/2 ?
- adwn 4y agoThat doesn't work when both are odd. For example, for x=1 and y=3 this gives 1 instead of 2.
- someweirdperson 4y ago1/2 + 3/2 + 1 = 0 + 1 + 1 = 2
- rocqua 4y agoYour 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 4y agowoops, misread the indent-depth of the posts as reply, not to the same parent.
- beardyw 4y agoBecause division is a slow operation. Even (x + y)/2 would be quicker
- secondcoming 4y agoDividing by two is just a right shift.
- robocat 4y agoOnly 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?contentId=87152374 https://wiki.sei.cmu.edu/confluence/plugins/servlet/mobile?c...
- rep_lodsb 4y agoadd x,y rcr x,1
- adwn 4y agoTo 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 4y agoIt'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 4y agoHave a look at https://github.com/wiz-lang/wiz https://github.com/wiz-lang/wiz. I agree that this in an unexplored area.
- distcs 4y agoI 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 4y agoFor 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 4y agoChatGPT 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; }
- planede 4y agoVery much relevant: CppCon 2019: Marshall Clow “std::midpoint? How Hard Could it Be?” https://www.youtube.com/watch?v=sBtAGxBh-XI https://www.youtube.com/watch?v=sBtAGxBh-XI
- mredigonda 4y agoYou 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.
- fyresala 4y agoWhy this could be better than (x+y)/2, since they both overflows?
- planede 4y agoAnd wrong, since x=-1 and y=INT_MAX overflows.
- orlp 4y agoThis can overflow for signed integers.
- phkahler 4y agoThe subtraction could overflow.
- deleted 4y ago[deleted]
- mredigonda 4y agoIndeed 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 4y agoIt's not a special right, you just have to do it within 2 hours.
- jlokier 4y agoOther 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.
- neilv 4y agoThere'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.
- hgsgm 4y agoIn the old days where programmers knew that everything computers did was AI.
- neilv 4y agoIIUC, 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.)
- TonyTrapp 4y agoRelevant link: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
- delta_p_delta_x 4y agoAlso related: Quake III fast inverse square root[1]. [1]: https://github.com/id-Software/Quake-III-Arena/blob/master/code/game/q_math.c#L552 https://github.com/id-Software/Quake-III-Arena/blob/master/c...
- mkl 4y agoIt's way older than Quake III: https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root Many past discussions on HN: https://hn.algolia.com/?q=inverse+square+root https://hn.algolia.com/?q=inverse+square+root
- hgsgm 4y ago
- amelius 4y agoShouldn't processors have a special instruction for this operation?
- josefx 4y agoThose 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.
- mananaysiempre 4y agoRotate 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.
- rep_lodsb 4y ago>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.
- captainmuon 4y agoIf 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).
- dahfizz 4y agoWhat do you do when operating on the largest int type available?
- tromp 4y agoDon't have a largest int type?!
- captainmuon 4y agoMaybe spit out a warning and use bignums? You are then supposed to explicitly narrow the type, or explicitly opt into using bignums.
- layer8 4y agoWhat 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.
- gilbetron 4y agoA bit more detailed look at it: https://devblogs.microsoft.com/oldnewthing/20220207-00/?p=106223 https://devblogs.microsoft.com/oldnewthing/20220207-00/?p=10...
- mojuba 4y agoThis 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.
- heavenlyblue 4y ago> 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?
- stevoski 4y agoIf 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 4y agoIf a & b are both odd, you end up rounding twice vs. 0 times if you take the sum first.
- eloff 4y agoIt'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.
- Jagerbizzle 4y agoThe 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);
- lpage 4y agoJoshua 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-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- deleted 4y ago[deleted]
- programmer_dude 4y agoWhy not ... x, y = minmax(x, y) return x + (y - x) / 2; ?
- lgeorget 4y agoThere's branching involved in the minmax operation, so it'll always be slower than (x|y) - ((x^y)>>1).
- scatters 4y ago(-0x80000000, 0x7fffffff)
- bonzini 4y agomin = x^((y^x)&-(y<x)); return min + ((y^x^min)-min)/2; Still less efficient.
- harerazer 4y agoy - x overflows on y = INT_MAX and x = -1.
- pksadiq 4y agoint 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.
- tiffanyh 4y agoUsing the midpoint function is the most readable. https://en.cppreference.com/w/cpp/numeric/midpoint https://en.cppreference.com/w/cpp/numeric/midpoint Though it's odd this allows overflow.
- abainbridge 4y agostd::midpoint also seems to yield less efficient code with g++12 targeting x86-64: https://godbolt.org/z/j695ce98Y https://godbolt.org/z/j695ce98Y
- Lockal 4y agostd::midpoint does different thing in terms of rounding, therefore comparison is not fair.
- abainbridge 4y agoPossibly true, but it yields less efficient code in GCC 12 for x86-64. https://godbolt.org/z/oafPrb4K8 https://godbolt.org/z/oafPrb4K8
- bonzini 4y agoBecause it's also wrong! / rounds towards zero, while summing a&b&1 requires the division to round towards negative infinity.
- nwellnhof 4y ago
- RenThraysk 4y agox64 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
- gnull 4y agoThe 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.
- aimor 4y agoAlthough (a + b)/2 rounds towards 0, while the non-overflow solutions round up or down.
- w0mbat 4y agoWhy wouldn’t you just shift them both right and add them?
- yccs27 4y agoRounding error https://news.ycombinator.com/item?id=33893153 https://news.ycombinator.com/item?id=33893153
- kazinator 4y agoRegarding 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 4y agoThis 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 4y agoIf they're expressed in two's complement, this works for negative numbers as well.
- vikingerik 4y agoDuh, 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.
- noasaservice 4y agoI'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.
- MaxBarraclough 4y agoUnfortunately 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 https://stackoverflow.com/q/10589559
- Tyr42 4y agoIf 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.
- keepquestioning 4y agoThe Hacker's Delight guy is insane.
- MaxBarraclough 4y ago10 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 https://news.ycombinator.com/item?id=30252263