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

21–30 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#21

Post by [deleted] »

version_five wrote: post #9
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.

Yeah, when I read the article title, this is how I thought I would do it. Anything that obvious is not patentable in principle, but in practice, Samsung could still destroy any small business it wanted to by taking them to court over it. The patent system is awful

[deleted]

Re: Finding the average of two unsigned integers without overflow

#22

Post by nmilo »

lilyball wrote: post #14
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.

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.

Yeah you're right, it seems like the article is misleading. Still, unless I'm reading it wrong it seems like the patent is just describing the hardware translation of this algorithm, it's not really adding anything new. It's still dubious to me.

Re: Finding the average of two unsigned integers without overflow

#23

Post by justinpombrio »

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…

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.

Re: Finding the average of two unsigned integers without overflow

#24

Post by AnotherGoodName »

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.

Re: Finding the average of two unsigned integers without overflow

#25

Post by classichasclass »

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.

Re: Finding the average of two unsigned integers without overflow

#26

Post by danuker »

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…

> no defense.

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

Re: Finding the average of two unsigned integers without overflow

#27

Post by not2b »

staticassertion wrote: post #17
ijidak wrote: post #8

Earlier quoted context omitted.

I had to lol when I saw there was a patent for that. Divide both operands by 2 was my first idea before loading the page. (I like to try that sometimes before reading the articles.) I didn't think about the carry bit, but it seems like that would be a logical solution after 5 minutes of extra thinking. I'm not sure how that's patentable. That's insane to me. But maybe there is more too it. I didn't read the patent it…

https://patents.google.com/patent/US6007232A/en The patent is for a circuit design to perform that algorithm in a single cycle. The algorithm was never patented, nor could it be.

In practice it makes no difference, because digital logic designers haven't used schematic capture in a very long time. They most commonly write Verilog (or SystemVerilog, which is a superset), and it looks a lot like C:

logic [31:0] a, b, average; assign average = (a >> 1) + (b >> 1) + (a & b & 32'd1);

Re: Finding the average of two unsigned integers without overflow

#28

Post by 829588225 »

AnotherGoodName wrote: post #24

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

23 ^ 21 = 2

Re: Finding the average of two unsigned integers without overflow

#29

Post by WalterBright »

lilyball wrote: post #14
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.

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.

Re: Finding the average of two unsigned integers without overflow

#30

Post by jlynn »

AnotherGoodName wrote: post #24

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

The average of 23 and 21 is indeed 22.
Post reply on HN