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

111–120 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#111

Post by [deleted] »

Agentlien wrote: post #105
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/

I just want to second this with my own experience just now: I looked at the title while still waking up. At first I thought of the low + (high - low) / 2 method. I then figured maybe it was better to simply predivide both numbers before adding and just correcting for the lowest bit (how was that ever patented?!). However, I didn't like having to perform two divisions so I thought there was probably something clever o…

[deleted]

Re: Finding the average of two unsigned integers without overflow

#112

Post by [deleted] »

Agentlien wrote: post #105
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/

I just want to second this with my own experience just now: I looked at the title while still waking up. At first I thought of the low + (high - low) / 2 method. I then figured maybe it was better to simply predivide both numbers before adding and just correcting for the lowest bit (how was that ever patented?!). However, I didn't like having to perform two divisions so I thought there was probably something clever o…

[deleted]

Re: Finding the average of two unsigned integers without overflow

#113

Post by xaduha »

Dylan16807 wrote: post #102
xaduha wrote: post #87

Earlier quoted context omitted.

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.

What should happen if you store "a+b" in an intermediate value?

If it is used and there's no way around it, then show a compilation warning that there might be overflow. If it can be resolved without being directly used, then it should be optimized away.

Re: Finding the average of two unsigned integers without overflow

#114

Post by erwincoumans »

mark-r wrote: post #110

This was a lot more thorough and in-depth than I expected it to be. But that's Raymond Chen for you. One of the reasons I love Python is that integers never overflow, so this becomes a trivial problem.

Rounding in Python is interesting though:

https://www.askpython.com/python/built-in-methods/python-rou...

"Also, if the number is of the form x.5, then, the values will be rounded up if the roundup value is an even number. Otherwise, it will be rounded down.

For example, 2.5 will be rounded to 2, since 2 is the nearest even number, and 3.5 will be rounded to 4."

Re: Finding the average of two unsigned integers without overflow

#116

Post by vbezhenar »

Agentlien wrote: post #105
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/

I just want to second this with my own experience just now: I looked at the title while still waking up. At first I thought of the low + (high - low) / 2 method. I then figured maybe it was better to simply predivide both numbers before adding and just correcting for the lowest bit (how was that ever patented?!). However, I didn't like having to perform two divisions so I thought there was probably something clever o…

x / 2 === x >> 1, it's fast.

Re: Finding the average of two unsigned integers without overflow

#118

Post by rustybolt »

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.

If you, for example, want to do addition of four 8-bit integers within a 32-bit register, you have to use similar techniques to stop the carry from propagating.

For example, when x and y are 32-bit integers holding 4 8-bit integers, you can do

    z = (x ^ y) + (x & y) & 0x7f7f7f7f;
Now z holds four 8-bit integers which hold the sum (modulo 256) of the integers of x and y. The bit mask is to stop the carry from propagating.

Re: Finding the average of two unsigned integers without overflow

#119

Post by wahern »

thfuran wrote: post #95
nerdponx wrote: post #82

Earlier quoted context omitted.

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.

> I don't think there's process beyond choosing to fight any suit brought against you and hoping you win in court.

Not true. See https://en.wikipedia.org/wiki/Reexamination It's even easier today than a decade ago, though the Wikipedia article doesn't explain that aspect very well. (I wouldn't be able to explain it, either. I think it has to do with reduced ability for a patent owner to drag out review, including dragging it into court.) Probably not nearly easy enough, though.

Re: Finding the average of two unsigned integers without overflow

#120

Post by Agentlien »

vbezhenar wrote: post #116
Agentlien wrote: post #105

Earlier quoted context omitted.

I just want to second this with my own experience just now: I looked at the title while still waking up. At first I thought of the low + (high - low) / 2 method. I then figured maybe it was better to simply predivide both numbers before adding and just correcting for the lowest bit (how was that ever patented?!). However, I didn't like having to perform two divisions so I thought there was probably something clever o…

x / 2 === x >> 1, it's fast.

It's fast, but I figured doing that on both sides before adding looked a bit inelegant and maybe it could be avoided by doing "something something bit operations" and then I dropped the thought and clicked the link.
Post reply on HN