from Hacker News

Finding the average of two unsigned integers without overflow

by mlex on 2/7/22, 10:28 PM with 208 comments

by errcorrectcode on 2/8/22, 1:01 AM
Having done computer architecture and bit twiddling x86 in the ye olden days, I immediately, independently converged on the patented solution (code / circuit / Verilog, more or less the same thing). It goes to show how broken the USPTO is because it's obvious to anyone in the field. Patents are supposed to be nonobvious. (35 USC 103)
https://patentdefenses.klarquist.com/obviousness-sec-103/
by ridiculous_fish on 2/7/22, 11:58 PM
The "SWAR" approach `(a & b) + (a ^ b) / 2` looks bizarre but can be understood.
Adding two bits produces a sum and a carry:
```
    0 + 0 = 0, carry 0
    1 + 0 = 1, carry 0
    0 + 1 = 1, carry 0
    1 + 1 = 0, carry 1
```
So the sum is XOR, and the carry is bitwise AND. We can rewrite x + y as (x ^ y) + (x & y)*2
Distribute the divide, and you get (x ^ y)/2 + (x & y) which is the mystery expression.
(Note this distribution is safe only because (x & y)*2 is even.)
by worewood on 2/8/22, 1:38 AM
Just by reading the headline, before opening the article, I thought of the patented solution in my head. "Just halve before adding, it can be off by one but some boolean logic might do it"
Software patents are absolutely disgusting.
by justin66 on 2/7/22, 11:47 PM
See also: "Nearly All Binary Searches and Mergesorts are Broken" by Joshua Bloch. The cluefulness or otherwise with which people often react to Bloch's excellent post is not something to ponder very closely if you want to retain any hope in the future of software engineering.
https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
https://news.ycombinator.com/item?id=3530104
https://news.ycombinator.com/item?id=1130463
https://news.ycombinator.com/item?id=14906429
https://news.ycombinator.com/item?id=6799336
https://news.ycombinator.com/item?id=9857392
https://news.ycombinator.com/item?id=12147703
https://news.ycombinator.com/item?id=621557
https://news.ycombinator.com/item?id=7594625
https://news.ycombinator.com/item?id=9113001
https://news.ycombinator.com/item?id=16890739
If doomscrolling all that isn't enough to make you fear for mankind's future I'm pretty sure there's an Ulrich Drepper glibc bug report rejection related to this topic (or several) that you can google...
On topic: Raymond's post has some other great stuff. SWAR!
by johnhenry on 2/8/22, 4:58 AM
I saw the title and thought to just do "(a / 2) + (b / 2)" and a do a little bit of fudging if a or b is odd.
After reading the article, learning that
```
  unsigned average(unsigned a, unsigned b)
  {
    return (a / 2) + (b / 2) + (a & b & 1);
  }
```
was once patented actually made me a bit sad for our entire system of patents.

by nmilo on 2/8/22, 12:05 AM

    There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016:

    unsigned average(unsigned a, unsigned b)
    {
        return (a / 2) + (b / 2) + (a & b & 1);
    }

There's no way that should be patentable.

by rustybolt on 2/8/22, 5:55 AM
> There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016.
That's completely retarded; it's literally the first solution I think of when I hear this problem.
by dralley on 2/8/22, 5:52 PM
> I find it amusing that the PowerPC, patron saint of ridiculous instructions, has an instruction whose name almost literally proclaims its ridiculousness: rldicl. (It stands for “rotate left doubleword by immediate and clear left”.)
I suspect the POWER team has a good sense of humor. There's also the EIEIO instruction https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-...
by benlivengood on 2/8/22, 4:04 AM
Before reading the article: In x86 assembly, add ax, bx ; rcr ax, 1 works. I guess technically that is with overflow, but using overflow bits as intended.
EDIT: it's included in the collection of methods in the article as expected.
by AnotherGoodName on 2/8/22, 12:44 AM
I noticed the following is in the middle of the article with no context that no one else is mentioning:
```
    unsigned average(unsigned a, unsigned b)
    {
        return (a & b) + (a ^ b) / 2;
    }
```
A quick sanity check of this
23 & 21 = 21
23 ^ 21 = 2
21 + 2 / 2 = 22 (order of operations)
I wonder why this is there. It seems the best solution but no one else is mentioning it. It also has no context near it. Nor is it stated correctly. It's just there on it's own.
by yalogin on 2/8/22, 4:33 AM
I cannot believe that solution was allowed to be patented. How crappy is our patent process? Most engineers writing code would come up with that solution first.
by classichasclass on 2/8/22, 12:46 AM
He hinted at this obliquely, but the PowerPC family of bit rotate instructions (ridicl, rlwinm, rlwimi, etc.), although intimidating in the general case, allows shifting, rotation, insertion, masking and more. There are many alternative mnemonics to try to reduce the cognitive complexity but all of these just assemble to them with particular parameters.
by leptoniscool on 2/8/22, 1:07 AM
This seems fundamental, surprised elementary operations hasn't been made a part of every major language/framework.
by Findecanor on 2/8/22, 8:52 AM
As an asm geek, I wasn't surprised to read that taking advantage of the carry flag yielded the most efficient code for some processors. I recalled that some ISAs also have special SIMD instructions specifically for unsigned average, so I looked them up:
* x86 SSE/AVX/AVX2 have (V)PAVGB and (V)PAVGW, for 8-bit and 16-bit unsigned integers. These are "rounding" instruction though: adding 1 to the sum before the shift.
* ARM "Neon" has signed and unsigned "Halving Addition". 8,16 or 32 bit integers. Rounding or truncating.
* RISC-V's new Vector Extension has instructions for both signed and unsigned "Averaging Addition". Rounding mode and integer size are modal.
* The on-the-way-out MIPS MSA set has instruction for signed, unsigned, rounded and truncated average, all integer widths.
Some ISAs also have "halving subtraction", but the purpose is not as obvious.
by unwind on 2/8/22, 6:03 AM
Very cool.
I was surprised that the article didn't mention the need for this in binary search, and the famous problems [1] that occured due to naive attempts.
[1]: https://en.m.wikipedia.org/wiki/Binary_search_algorithm
by ncmncm on 2/8/22, 9:44 AM
> gcc doesn’t have a rotation intrinsic, so I couldn’t try it there
Gcc and Clang both recognize the pattern of shifts and OR that reproduce a rotation, and substitute the actual instruction, no intrinsic needed.
I bet MSVC does too.
by user-the-name on 2/8/22, 11:20 AM
"unsigned long long"?
It's 2022. stdint.h is old enough to drink, and is probably married with a kid on the way. Just include it already?
by MaxBarraclough on 2/8/22, 1:27 PM
Reminds me of a Stack Overflow thread, Shortest way to calculate difference between two numbers? [0] Multiple answers ignored the possibility of overflow.
[0] https://stackoverflow.com/q/10589559/
by favorited on 2/8/22, 2:07 AM
Marshall Clow gave a pretty excellent CppCon talk covering these exact problems, called "std::midpoint? How Hard Could it Be?" https://www.youtube.com/watch?v=sBtAGxBh-XI
by Subsentient on 2/8/22, 2:48 AM
Eh. I just cast both to a bigger integer type where possible, which in practice, is almost always. So if I'm averaging two uint32_ts, I just cast them to uint64_t beforehand. Or in Rust, with its lovely native support for 128-bit integers, I cast a 64-bit integer to 128-bit.
by everyone on 2/8/22, 11:47 AM
I find it mind boggling that something as simple as this can actually be patented.
```
  unsigned average(unsigned a, unsigned b)
  {
      return (a / 2) + (b / 2) + (a & b & 1);
  }
```
That makes the patent system seem broken to me.
by mark-r on 2/8/22, 5:20 AM
This was a lot more thorough and in-depth than I expected it to be. But that's Raymond Chen for you.
One of the reasons I love Python is that integers never overflow, so this becomes a trivial problem.
by Beldin on 2/8/22, 8:06 AM
Since this discussion is all about patents: my 2 cents on improving the patent system.
Consider a term project of an undergraduate CS course, where the goal is spelled out, but the method is left for discovery.
Methods developed within any such project immediately invalidate patents. They're apparently obvious to folks learning to become "skilled in the art".
Yes, in practice, reaching a legal threshold would be hard (are you sure the students didn't read the patent or any description directly resulting from it?). But I'd definitely run a "patent invalidation course" - if I had confidence that the results would actually affect patents.
by mirkodrummer on 2/8/22, 8:37 AM
Wait, what? How can a patent right be applied on a one line of code that eventually is compiled down to machine code? Sounds ridicolous to me
by bufferoverflow on 2/8/22, 1:46 AM
Isn't it better to do
```
    (a>>1) + (b>>1) + (a&b&1)
```
No division needed.
by dpacmittal on 2/8/22, 1:49 PM
You could also do (a + (b-a)/2) where a is the smaller number.
by dathinab on 2/8/22, 8:17 AM
how is turning (a+b)/2 into a/2 + b/2 + a&b&1 even patentable?
Turning (a+b)/2 into a/2 + b/2 is basic obvious math.
If you do it and to any basic testing you will realize you are getting of by one errors, locking at them can then make it obvious that when they appear and hence how to fix them.
Sure a proof is more complex, but then you can just trivially test it for all smaller-bit numbers over all possible inputs, hence making proofs unnecessary (for that numbers).
This is a solution a not yet graduated bachelor student can find in less then a day.
Having granted a patent for this should lead to disciplinary measurements against the person granting the patent tbh.
by phs318u on 2/8/22, 7:59 AM
I got a pang of nostalgia seeing the Alpha AXP instructions.
by avmich on 2/8/22, 1:17 AM
Does this all work with BCD encoding?
by blobbers on 2/8/22, 2:23 AM
This guy hacks.
by kingcharles on 2/7/22, 11:58 PM
Some unreal solutions here that show how amazing mathematics can be. Especially that Google patented method that only just recently expired.
Props for including the assembler breakdown for every major CPU architecture.