The post is in fact the second part of this. I reproduce from the book test for overflow in multiplication two unsigned 32 bit integers, and extended it to unsigned longs (64 bit unsigned). The basic idea is to check sum of leading zeroes (for 64 bits reasoning is the same) in 64 bit factors (when checking 32 bits). When the number is greater or equal than 32 (nlz(x) + nlz(y)) the multipliction does not overflow, when is less than 31 overflows; when equal to 31 is uncertain - additional checks are to be made.
Function is fast, there was no time difference when check run in a loop, precedding multiplication.
Code here (I'm moving from bitbucket, seems these days, everybody has github account from birthday-:)).
No comments:
Post a Comment