In the Math library, add support for computing x * y >> n

[barakman]

🧐 Motivation
A function which calculates x* y >> n, allowing for the intermediate value of x * y to be larger than 256 bits.

This is of course already covered via mulDiv(x, y, 1 << n, Rounding.Floor).

But it (the method below) would consume a lot less gas, so you may consider it complementary for performance optimization.

📝 Details

function mulShr(uint256 x, uint256 y, uint8 n) internal pure returns (uint256) {
    unchecked {
        (uint256 xyh, uint256 xyl) = mul512(x, y);
        require(xyh < 1 << n);
        return (xyh << (256 - n)) | (xyl >> n);
    }
}

function mul512(uint256 x, uint256 y) private pure returns (uint256, uint256) {
    unchecked {
        uint256 p = mulmod(x, y, type(uint256).max);
        uint256 q = x * y;
        if (p >= q)
            return (p - q, q);
        return (p - q - 1, q);
    }
}

I'm pretty sure that you already have some version of mul512 (above) implemented in the Math library.
For example, at the beginning of function mulDiv:

uint256 prod0 = x * y; // Least significant 256 bits of the product
uint256 prod1; // Most significant 256 bits of the product
assembly {
    let mm := mulmod(x, y, not(0))
    prod1 := sub(sub(mm, prod0), lt(mm, prod0))
}

So you might want to reuse that piece of code in some way.

---

An alternative which won't require updating the existing API is to add this in your mulDiv function:

if (denominator & (denominator - 1) == 0) {
    return (prod1 * (type(uint256).max / denominator + 1)) | (prod0 / denominator);
}

However, there are two issues with this option:

1. Minor issue: for cases which enter the if statement, it is slightly more expensive than the original suggestion
2. Major issue: it will slightly increase the cost for all other cases, which means worsening the worst-case scenario