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

81–90 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#81

Post by doctor_eval »

hackthefender wrote: post #67
jws wrote: post #54

Earlier quoted context omitted.

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

> Clearly we have both had miraculous enlightenment because legally this is “not obvious”. To be precise, legally it is "not obvious back in 1996." There is a lot of stuff that is obvious today that wasn't 25 years ago. That said, this one in particular probably would have been invalidated as obvious if it was ever litigated (and it was not). Also, the USPTO has reined in software patents a lot in recent years (but a…

Seriously, I could have done this in 1996 and so could anyone. I reckon I could probably have worked this out in 1986. It’s not like binary arithmetic has changed significantly in the last 20 years.

Re: Finding the average of two unsigned integers without overflow

#82

Post by nerdponx »

hackthefender wrote: post #61
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/

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

Re: Finding the average of two unsigned integers without overflow

#83

Post by zanethomas »

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/

100% correct

the patented solution immediately came to mind

Re: Finding the average of two unsigned integers without overflow

#84

Post by shannongreen »

AnotherGoodName wrote: post #32
829588225 wrote: post #28

Earlier quoted context omitted.

23 ^ 21 = 2

Sorry, edited the above. This is straight up right then which is weird. It's just there in the middle of the article with no context. In the middle of the SWAR method.

It is the SWAR method. Another comment explains it well, it basically treats each bit position as a 2-bit adder.

Re: Finding the average of two unsigned integers without overflow

#85

Post by jagger27 »

umeshunni wrote: post #65
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.

It's not the solution that's patented, but it's the implementation in a single CPU cycle in hardware.

That’s a pretty important distinction. If someone in the 1800s invented a mechanical calculator that could do this operation in a single crank, I don’t think anyone would upset about that patent.

Re: Finding the average of two unsigned integers without overflow

#86

Post by ______-_-______ »

hackthefender wrote: post #67
jws wrote: post #54

Earlier quoted context omitted.

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

> Clearly we have both had miraculous enlightenment because legally this is “not obvious”. To be precise, legally it is "not obvious back in 1996." There is a lot of stuff that is obvious today that wasn't 25 years ago. That said, this one in particular probably would have been invalidated as obvious if it was ever litigated (and it was not). Also, the USPTO has reined in software patents a lot in recent years (but a…

It's not even computer science, it's literally just math. (a+b)/2 = a/2 + b/2. They were teaching that in pre-algebra in middle schools well before 1996.

Re: Finding the average of two unsigned integers without overflow

#87

Post by xaduha »

jws wrote: post #55
bufferoverflow wrote: post #53

Isn't it better to do (a>>1) + (b>>1) + (a&b&1) No division needed.

Your compiler will take care of that. Leave the division for the humans to read.

I'm in a camp that thinks compilers should also take care of the original

    unsigned average(unsigned a, unsigned b) {
        return (a + b) / 2;
    }
At the end of the day it's all just text. There are plenty of steps before any of it does anything at all.

Re: Finding the average of two unsigned integers without overflow

#89

Post by dreamcompiler »

dheera wrote: post #80
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)

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

Re: Finding the average of two unsigned integers without overflow

#90

Post by jandrewrogers »

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.

Any algorithm directly expressible as an electronic circuit is considered patentable in most countries due to this equivalence relationship. Technically, this includes all computing algorithms in practice, since there is no meaningful distinction between software and hardware.

However, this is also why business method algorithms like the Amazon "One-Click" are not patentable in most countries. There is no trivial theoretical equivalence between one-click shopping and an electronic circuit.

Post reply on HN