This thread is full of people who challenged themselves to solve it and then failed to come up with the 'obvious' 1-cycle solution. It's clearly non-obvious, as this thread shows.

The actual patent system failure here is the patent is not useful -- it's not valuable. If you needed this solution, you could sit down and derive it in less than an hour. That's not because it's obvious, but because the scope is so small.

The only difference between this patent and say a media codec is how long it would take to reinvent it. It might take you 200 years to come up with something as good as h.265, but there's no magic to it. There's a problem, somebody came up with a solution, somebody else could do it again given enough time to work on it. This is true for everything that's ever been patented.

The point of patents is to compensate for value of the work needed to reinvent, and so the real problem here is that value is less than any sane minimum. The value is less than the patent examiner's time to evaluate it! But court rulings have said it doesn't matter how insignificant a patent is, as long as it does anything at all it's "useful", which leads to these kinds of worthless patents.

and then failed to come up with the 'obvious' 1-cycle solution

That's unfair, as the commenters here are providing a software solution. The patent is about a hardware solution which involves two parallel adder circuits. It implements in hardware exactly what the software solution does, but you can't express it in software because there is no operand that expresses "implement this addition twice please". You'd have to express it as:

  avg = [x>>1 + y>>1, x>>1 + y>>1 + 1][x&y&1]

Which isn't 1-cycle either without the specialized adder.

And I just realized the hardware solution is incredibly sub-optimal. If you were to design this in specialized hardware, you'd use a single (N+1)-bit adder and just discard the least significant bit in the output, not duplicate the entire adder tree in silicon.

There is no need for a specialized adder.

The patented expression is computable in an obvious way by a single ordinary adder and a single AND gate connected to the carry input of the adder, without any other devices (the shifts and the "& 1" are done by appropriate connections).

Any ordinary N-bit adder computes the sum of 3 input operands, 2 which are N-bit, and a third which is an 1-bit carry.

> This thread is full of people who challenged themselves to solve it and then failed to come up with the 'obvious' 1-cycle solution. It's clearly non-obvious, as this thread shows.

If a significant fraction of people come up with it on the spot, it's obvious. And they did.

I don't even see a single comment mentioning doing this in 1 cycle except from those who read the patent, much less reusing existing functional units to do so, so it's not clear to me any commenter came up with an equivalent to the patented solution or even identified the problem solved by it.

Keep in mind this solution was to support MPEG-1 video encoding in the olden days when state of the art processors were 100 MHz and 800 nm process. Doing this in 1 cycle while reusing already existing function units seems like a clever solution to me -- not patent-worthy, not difficult, but clever.

Are you very sure that patent would never get threatened toward a software implementation that doesn't know anything about cycles?

If so then the technique in the post isn't actually patented.

If that C code would get threatened, then the 1 cycle thing is a red herring.

Also "Doing this in 1 cycle while reusing already existing function units"? In hardware you can use a normal adder without any special technique...

I've already said twice now that it's not patent-worthy, so it seems we're in agreement on that point.

That's a response to you calling it clever.

Sorry, but this argument about the single-cycle implementation is complete BS.

Any logic designer, who is not completely incompetent, when seeing the expression

(a / 2) + (b / 2) + (a & b & 1);

will notice that this is a 1-cycle operation, because it is just an ordinary single addition.

In hardware the divisions are made just by connecting the bits of the operands in the right places. Likewise, the "& 1" is done by connecting the LSB's of the operands to a single AND gate and the resulting bit is connected to the carry of the adder, so no extra hardware devices beyond a single adder are needed. This is really absolutely trivial for any logic designer.

The questions at any hiring interview, even for beginners, would be much more complex than how to implement this expression.

It is absolutely certain that such a patent should have never been granted, because both the formula and its implementation are obvious for any professional in the field.