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)<p><a href="https://patentdefenses.klarquist.com/obviousness-sec-103/" rel="nofollow">https://patentdefenses.klarquist.com/obviousness-sec-103/</a>
The "SWAR" approach `(a & b) + (a ^ b) / 2` looks bizarre but can be understood.<p>Adding two bits produces a sum and a carry:<p><pre><code> 0 + 0 = 0, carry 0
1 + 0 = 1, carry 0
0 + 1 = 1, carry 0
1 + 1 = 0, carry 1
</code></pre>
So the sum is XOR, and the carry is bitwise AND. We can rewrite x + y as (x ^ y) + (x & y)*2<p>Distribute the divide, and you get (x ^ y)/2 + (x & y) which is the mystery expression.<p>(Note this distribution is safe only because (x & y)*2 is even.)
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"<p>Software patents are absolutely disgusting.
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.<p><a href="https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html" rel="nofollow">https://ai.googleblog.com/2006/06/extra-extra-read-all-about...</a><p><a href="https://news.ycombinator.com/item?id=3530104" rel="nofollow">https://news.ycombinator.com/item?id=3530104</a><p><a href="https://news.ycombinator.com/item?id=1130463" rel="nofollow">https://news.ycombinator.com/item?id=1130463</a><p><a href="https://news.ycombinator.com/item?id=14906429" rel="nofollow">https://news.ycombinator.com/item?id=14906429</a><p><a href="https://news.ycombinator.com/item?id=6799336" rel="nofollow">https://news.ycombinator.com/item?id=6799336</a><p><a href="https://news.ycombinator.com/item?id=9857392" rel="nofollow">https://news.ycombinator.com/item?id=9857392</a><p><a href="https://news.ycombinator.com/item?id=12147703" rel="nofollow">https://news.ycombinator.com/item?id=12147703</a><p><a href="https://news.ycombinator.com/item?id=621557" rel="nofollow">https://news.ycombinator.com/item?id=621557</a><p><a href="https://news.ycombinator.com/item?id=7594625" rel="nofollow">https://news.ycombinator.com/item?id=7594625</a><p><a href="https://news.ycombinator.com/item?id=9113001" rel="nofollow">https://news.ycombinator.com/item?id=9113001</a><p><a href="https://news.ycombinator.com/item?id=16890739" rel="nofollow">https://news.ycombinator.com/item?id=16890739</a><p>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...<p>On topic: Raymond's post has some other great stuff. SWAR!
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.<p>After reading the article, learning that<p><pre><code> unsigned average(unsigned a, unsigned b)
{
return (a / 2) + (b / 2) + (a & b & 1);
}
</code></pre>
was once patented actually made me a bit sad for our entire system of patents.
<p><pre><code> 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);
}
</code></pre>
There's no way that should be patentable.
> There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016.<p>That's completely retarded; it's literally the first solution I think of when I hear this problem.
> 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”.)<p>I suspect the POWER team has a good sense of humor. There's also the EIEIO instruction <a href="https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-in-order-execution-io-instruction" rel="nofollow">https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-...</a>
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.<p>EDIT: it's included in the collection of methods in the article as expected.
I noticed the following is in the middle of the article with no context that no one else is mentioning:<p><pre><code> unsigned average(unsigned a, unsigned b)
{
return (a & b) + (a ^ b) / 2;
}
</code></pre>
A quick sanity check of this<p>23 & 21 = 21<p>23 ^ 21 = 2<p>21 + 2 / 2 = 22 (order of operations)<p>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.
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.
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.
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:<p>* 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.<p>* ARM "Neon" has signed and unsigned "Halving Addition". 8,16 or 32 bit integers. Rounding or truncating.<p>* RISC-V's new Vector Extension has instructions for both signed and unsigned "Averaging Addition". Rounding mode and integer size are modal.<p>* The on-the-way-out MIPS MSA set has instruction for signed, unsigned, rounded and truncated average, all integer widths.<p>Some ISAs also have "halving subtraction", but the purpose is not as obvious.
Very cool.<p>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.<p>[1]: <a href="https://en.m.wikipedia.org/wiki/Binary_search_algorithm" rel="nofollow">https://en.m.wikipedia.org/wiki/Binary_search_algorithm</a>
> <i>gcc doesn’t have a rotation intrinsic, so I couldn’t try it there</i><p>Gcc and Clang both recognize the pattern of shifts and OR that reproduce a rotation, and substitute the actual instruction, no intrinsic needed.<p>I bet MSVC does too.
"unsigned long long"?<p>It's 2022. stdint.h is old enough to drink, and is probably married with a kid on the way. Just include it already?
Reminds me of a Stack Overflow thread, <i>Shortest way to calculate difference between two numbers?</i> [0] Multiple answers ignored the possibility of overflow.<p>[0] <a href="https://stackoverflow.com/q/10589559/" rel="nofollow">https://stackoverflow.com/q/10589559/</a>
Marshall Clow gave a pretty excellent CppCon talk covering these exact problems, called "std::midpoint? How Hard Could it Be?" <a href="https://www.youtube.com/watch?v=sBtAGxBh-XI" rel="nofollow">https://www.youtube.com/watch?v=sBtAGxBh-XI</a>
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.
I find it mind boggling that something as simple as this can actually be patented.<p><pre><code> unsigned average(unsigned a, unsigned b)
{
return (a / 2) + (b / 2) + (a & b & 1);
}
</code></pre>
That makes the patent system seem broken to me.
This was a lot more thorough and in-depth than I expected it to be. But that's Raymond Chen for you.<p>One of the reasons I love Python is that integers never overflow, so this becomes a trivial problem.
Since this discussion is all about patents: my 2 cents on improving the patent system.<p>Consider a term project of an undergraduate CS course, where the goal is spelled out, but the method is left for discovery.<p>Methods developed within any such project immediately invalidate patents. They're apparently obvious to folks learning to become "skilled in the art".<p>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.
how is turning (a+b)/2 into a/2 + b/2 + a&b&1 even patentable?<p>Turning (a+b)/2 into a/2 + b/2 is basic obvious math.<p>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.<p>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).<p>This is a solution a not yet graduated bachelor student can find
in less then a day.<p>Having granted a patent for this should lead to disciplinary
measurements against the person granting the patent tbh.
Some unreal solutions here that show how amazing mathematics can be. Especially that Google patented method that only just recently expired.<p>Props for including the assembler breakdown for every major CPU architecture.