4 ms·
I suppose one downside of this approach is that you need a bigger datatype to contain the result.
by NieDzejkob 6y ago
I suppose one downside of this approach is that you need a bigger datatype to contain the result.
- beeforpork 6y agoNo, not really, because you just need the lower half bits of the multiplication result, i.e., the size you need for your numbers. You do need to care about overflow: the /2 operation must not remove an upper bit from those lower bits. But you can easily do that before *: either n or n+1 is even. Divide the even number by two, then multiply by the odd one and keep only the lower bits. These lower bits are all you need, because the missing number is representable in it: subtracting may use wrap-around, but still, the remaining bits will be the missing number.