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

71–80 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#71

Post by eru »

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.

Wikipedia says: "It also refers to the use of SIMD with general-purpose registers and instructions that were not meant to do it at the time, by way of various novel software tricks."

https://en.wikipedia.org/wiki/SWAR

Maybe that's the way it's meant?

Compilers might be smart enough to pick up the idiom used in the example and compile them to something done in parallel?

Re: Finding the average of two unsigned integers without overflow

#72

Post by enneff »

teaearlgraycold wrote: post #63
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.

As if anyone would ever get prosecuted for that, though. Given its simplicity this makes me wonder if a compiler has ever transformed legal original IP code into patented code.

That’s not really how software patents are (ab)used. Just having the patent and a vaguely credible claim that someone is using the patented technology is enough to encumber them with enough legal issues that many people will settle instead of fight it.

Re: Finding the average of two unsigned integers without overflow

#73

Post by erosenbe0 »

paxys wrote: post #19
nmilo wrote: post #7

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.

It shouldn't be, but the world of software patents is truly bizarre. I have several patents in my name that are completely meaningless to the point of being satirical (stuff like "system to show a list of options and dispatch and action to a web server", "validating information submitted in a web form and returning errors"). Each is 40+ pages of filing, complete with diagrams, and all of them approved. And we need to…

Maybe if employees of big tech would whisteblow to Congress on being forced into the unethical abuse of property rights that would help?

Re: Finding the average of two unsigned integers without overflow

#74

Post by Subsentient »

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.

Re: Finding the average of two unsigned integers without overflow

#75

Post by ChrisMarshallNY »

paxys wrote: post #19
nmilo wrote: post #7

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.

It shouldn't be, but the world of software patents is truly bizarre. I have several patents in my name that are completely meaningless to the point of being satirical (stuff like "system to show a list of options and dispatch and action to a web server", "validating information submitted in a web form and returning errors"). Each is 40+ pages of filing, complete with diagrams, and all of them approved. And we need to…

I have my name on a patent for an imaging pipeline.

I have no idea why it was granted. I sent it to headquarters as a design pattern description.

That’s pretty much the definition of “prior art.”

I guess they were able to reshape it into a form that the patent office wouldn’t laugh out the door. I never really looked at it. I hate reading patents; even my own.

Re: Finding the average of two unsigned integers without overflow

#76

Post by erosenbe0 »

rrss wrote: post #60
paxys wrote: post #56

Earlier quoted context omitted.

"The world would be a lot better if independently did xyz" can be applied to pretty much anything. Except tragedy of the commons is a real thing, and this is why you need governments to step in and regulate.

yes, you are right. meaningful voluntary collective change is unlikely. however, i believe that individuals should respect the commons, and don’t believe in the tragedy of the commons as an excuse for individual actions that contribute to the problem. (insert starfish on the beach story)

Well employees could stage a walk out as they do for other causes because the abuse of property rights costs the American economy, worker, and consumer and forces employees to participate in these unethical abuses.

Re: Finding the average of two unsigned integers without overflow

#77

Post by erosenbe0 »

WalterBright wrote: post #29
lilyball wrote: post #14

Earlier quoted context omitted.

Algorithms aren't patentable. What's patented here is a specific circuit that implements this algorithm in order to calculate the average in a single instruction cycle.

The XOR cursor was patented.

Probably years after it was implemented too

Edit: but back in the 70s the USPTO didn't have the search databases they had in the 90s or 2000s. It's more the XOR patent being wielded in litigation that was extra controversial

Re: Finding the average of two unsigned integers without overflow

#78

Post by b112 »

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/

But in as it is non-obvious, as to why it is non-obvious, criteria met.

Re: Finding the average of two unsigned integers without overflow

#79

Post by thayne »

staticassertion wrote: post #37
danuker wrote: post #26

Earlier quoted context omitted.

> no defense. I am not a lawyer, but I suspect prior art is a defense.

It's more complicated than that. A patent troll will hold a patent for X and then claim you are violating that patent. You, the holder of Y, can then say "well you're violating Y so fuck right off". Or maybe there's another patent that could potentially indicate prior art, but it isn't your patent. Or you're just a really small player with a few patents in your portfolio trying to defend against a troll. Companies po…

The solution is pretty simple. Just stop allowing software patents.

Re: Finding the average of two unsigned integers without overflow

#80

Post by dheera »

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…

Why not just

   (a >> 1) + (b >> 1) + (a & 1) & (b & 1)
Post reply on HN