Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding the average of two unsigned integers without overflow

devblogs.microsoft.com

Post reply on HN
Print view View original

141–150 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#141

Post by wildmanx »

ziml77 wrote: post #69
justinpombrio wrote: post #23

Earlier quoted context omitted.

Alternatively, a direct explanation: a & b is the bits they have in common. If they both have a bit x, you should keep it, because the average of x and x is x. a ^ b is the bits that only one of them have. You should halve these bits, because the average of x and 0 is x/2.

This explanation makes a ton more sense!

But it has lots of assumptions/prerequisites about taking the mean baked-in. It happens to work for this particular case, but in general you don't get far with such hand-wavy reasoning since you just get confused with which assumptions hold and which don't.

The original explanation was the actual SIMD approach, which is really cool. You can extend it right away to other problems.

Re: Finding the average of two unsigned integers without overflow

#143

Post by wildmanx »

AnotherGoodName wrote: post #36
ridiculous_fish wrote: post #3

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 b…

Sorry i'm confused and i asked elsewhere. How is the above SWAR? It looks like a regular set of instructions.

SIMD is "single instruction, multiple data". In this case, the data are single bits. It's basically operations on bit-vectors of width 32 (or whatever the machine word width is). All the bits are treated independently. That's exactly how you'd do SIMD elsewhere.

Re: Finding the average of two unsigned integers without overflow

#144

Post by andi999 »

dreamcompiler wrote: post #89
dheera wrote: post #80

Earlier quoted context omitted.

Why not just (a >> 1) + (b >> 1) + (a & 1) & (b & 1)

That's the "patented solution" referred to in the article.

Which is shocking to me, since this is the solution which jumps immediately to mind (and usually patents should be above that line). I could understand if the next solution was patented, but not this one.

Re: Finding the average of two unsigned integers without overflow

#145

Post by wildmanx »

smaddox wrote: post #52
justin66 wrote: post #2

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?…

> I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. I haven't seen the mentioned proof, but if said proof is not formal and mechanized and/or does not consider all possibilities, including overflow, then should we really consider it to be a proof of correctness? It might prove some desirable properties, but I do…

It was a formal proof, but one based on a false assumption, namely that x+y for two ints x and y is an int and a well-defined operation. It's not.

The trust in the significance of a proof is limited by the trust in the statement to be proven. The statement to be proven was "If XYZ assumptions about the statements in the underlying language hold, then the result of that function is the result of a binary search". The proof is correct. Just that XYZ contained something incorrect.

There is no free lunch. Even if we prove all our software formally correct, we still need to "program" the specifications, with all that comes with it. They can contain bugs, need to be debugged, revisited, etc. The above is an excellent example of this.

Re: Finding the average of two unsigned integers without overflow

#146

Post by andi999 »

jws wrote: post #54
worewood wrote: post #49

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.

Absolutely the same thing I did. I even had the low bit logic worked out by the time I scrolled the article down and saw the patented line. Clearly we have both had miraculous enlightenment because legally this is “not obvious”.

Yes. I think though the next solution is not obvious. (a & b)+ (a^b)/2

Re: Finding the average of two unsigned integers without overflow

#147

Post by Findecanor »

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.

Re: Finding the average of two unsigned integers without overflow

#148

Post by dheera »

andi999 wrote: post #144
dreamcompiler wrote: post #89

Earlier quoted context omitted.

That's the "patented solution" referred to in the article.

Which is shocking to me, since this is the solution which jumps immediately to mind (and usually patents should be above that line). I could understand if the next solution was patented, but not this one.

Don't read the article, and you would never know it's patented.

Re: Finding the average of two unsigned integers without overflow

#149

Post by kwhitefoot »

nerdponx wrote: post #82
hackthefender wrote: post #61

Earlier quoted context omitted.

> It goes to show how broken the USPTO is... The patent issued in 1996 and wasn't revisited since then (because never asserted in litigation). The USPTO is a lot different now, a quarter-century later.

Isn't there also a recourse process by which you can get a patent invalidated? You can't expect USPTO to hire an expert in every single possible field.

Why not?

Re: Finding the average of two unsigned integers without overflow

#150

Post by undecisive »

errcorrectcode wrote: post #39

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/

This is bizarre. I wonder how many of us saw that title, thought "That's a really simple problem, surely?" came up with a solution and then were shocked when their coffee-lacking brain actually came up with the patented solution?

I mean... ignoring the bitwise arithmentic (which this only obvious to people used to doing binary operations) this is the kind of maths that an 11yo could do.

That said, the patented solution is a little more complex. But not by much.

Which makes me curious: what other patents have we violated in our day-to-day without even knowing it?

Post reply on HN