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

31–40 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#31

Post by AnotherGoodName »

jlynn wrote: post #30
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.

Oh right, sorry i'll edit this. It works straight up then. Weird it's there with no context.

Re: Finding the average of two unsigned integers without overflow

#32

Post by AnotherGoodName »

829588225 wrote: post #28
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

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.

Re: Finding the average of two unsigned integers without overflow

#33

Post by [deleted] »

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

[deleted]

Re: Finding the average of two unsigned integers without overflow

#34

Post by staticassertion »

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

Sorry, I don't understand what you mean. It makes no difference to whom? It definitely makes a difference to someone writing that code, since that code is not patented.

Re: Finding the average of two unsigned integers without overflow

#35

Post by tialaramex »

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.

Several of these patent claims are for "an apparatus" because you're not allowed to patent ideas - but any realisation of the algorithm will necessarily be "an apparatus" so the effect is that in fact you can claim algorithms and that's exactly what this is doing.

Re: Finding the average of two unsigned integers without overflow

#36

Post by AnotherGoodName »

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.

Re: Finding the average of two unsigned integers without overflow

#37

Post by staticassertion »

danuker wrote: post #26
paxys wrote: post #19

Earlier quoted context omitted.

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.

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 pool their patents together, promising not to sue each other over patents, in order to collectively defend themselves against trolls.

Re: Finding the average of two unsigned integers without overflow

#38

Post by staticassertion »

tialaramex wrote: post #35
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.

Several of these patent claims are for "an apparatus" because you're not allowed to patent ideas - but any realisation of the algorithm will necessarily be "an apparatus" so the effect is that in fact you can claim algorithms and that's exactly what this is doing.

I'm not a lawyer, so I'm confused. If you patent a hardware implementation of a software algorithm, on the basis that the implementation is novel, how would you stop me from writing that algorithm irrespective of how it executes?

Re: Finding the average of two unsigned integers without overflow

#39

Post by errcorrectcode »

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/

Post reply on HN