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

91–100 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#91

Post by WillSlim95 »

not2b wrote: post #27
staticassertion wrote: post #17

Earlier quoted context omitted.

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);

Sure but any HW engineer before writing HDL will always draw up a circuit before writing the description. And given that the patent was issued in 1996 it was only like 6-7 years after Verilog became an open standard.

Re: Finding the average of two unsigned integers without overflow

#92

Post by jamesfinlayson »

rrss wrote: post #47
staticassertion wrote: post #37

Earlier quoted context omitted.

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 world would be better if more companies were able or daring enough to fight bullshit patents directly (with prior art, obviousness, etc defenses). but instead every company chooses to defend themselves by deluging the patent office with more crap, and collective abuse of the patent system to patent stuff even the “inventor” thinks is obvious becomes accepted totally normal behavior.

I think Alibaba did this a little while ago - someone tried to sue them for infringing a one-click checkout patent and they did challenge them in court and won.

Re: Finding the average of two unsigned integers without overflow

#94

Post by LudwigNagasena »

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

Quite “amazing” that googleblog layout breaks on iOS. It’s literally impossible to see half of the text without the reader mode.

Re: Finding the average of two unsigned integers without overflow

#95

Post by thfuran »

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.

I think that's usually resolved in court. By which I mean, I don't think there's process beyond choosing to fight any suit brought against you and hoping you win in court.

Re: Finding the average of two unsigned integers without overflow

#97

Post by Dylan16807 »

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.

> The USPTO is a lot different now, a quarter-century later.

Please be more specific or link something that explains how they've improved.

Re: Finding the average of two unsigned integers without overflow

#98

Post by johnhenry »

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.

After reading the article, learning that

  unsigned average(unsigned a, unsigned b)
  {
    return (a / 2) + (b / 2) + (a & b & 1);
  }
was once patented actually made me a bit sad for our entire system of patents.

Re: Finding the average of two unsigned integers without overflow

#99

Post by Dylan16807 »

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)

"just"? That's 2 additions, 2 shifts, and 2-3 bitwise operations, while the other method is 1 addition, 1 shift, and 2 bitwise operations.

Re: Finding the average of two unsigned integers without overflow

#100

Post by cma »

Dylan16807 wrote: post #97
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.

> The USPTO is a lot different now, a quarter-century later. Please be more specific or link something that explains how they've improved.

Back then you couldn't early challenge a patent and prevent it from being issued, and once it was issued you couldn't challenge it without violating it and entering trial. Now you can do both.
Post reply on HN