How do I detect unsigned integer multiply overflow?

c++ c integer-overflow

386,068

Solution 1

I see you're using unsigned integers. By definition, in C (I don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)

With signed integers, once there has been overflow, undefined behaviour (UB) has occurred and your program can do anything (for example: render tests inconclusive).

#include <limits.h>

int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* Unreliable test */
  /* ... */
}

To create a conforming program, you need to test for overflow before generating said overflow. The method can be used with unsigned integers too:

// For addition
#include <limits.h>

int a = <something>;
int x = <something>;
if (x > 0 && a > INT_MAX - x) // `a + x` would overflow
if (x < 0 && a < INT_MIN - x) // `a + x` would underflow

// For subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if (x < 0 && a > INT_MAX + x) // `a - x` would overflow
if (x > 0 && a < INT_MIN + x) // `a - x` would underflow

// For multiplication
#include <limits.h>

int a = <something>;
int x = <something>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if (a == -1 && x == INT_MIN) // `a * x` can overflow
if (x == -1 && a == INT_MIN) // `a * x` (or `a / x`) can overflow
// general case
if (x != 0 && a > INT_MAX / x) // `a * x` would overflow
if (x != 0 && a < INT_MIN / x) // `a * x` would underflow

For division (except for the INT_MIN and -1 special case), there isn't any possibility of going over INT_MIN or INT_MAX.

Solution 2

Starting with C23, the standard header <stdckdint.h> provides the following three function-like macros:

bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);

where type1, type2 and type3 are any integer type. These functions respectively add, subtract or multiply a and b with arbitrary precision and store the result in *result. If the result cannot be represented exactly by type1, the function returns true ("calculation has overflowed"). (Arbitrary precision is an illusion; the calculations are very fast and almost all hardware available since the early 1990s can do it in just one or two instructions.)

Rewriting OP's example:

unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

c_test contains the potentially-overflowed result of the multiplication in all cases.

Long before C23, GCC 5+ and Clang 3.8+ offer built-ins that work the same way, except that the result pointer is passed last instead of first: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than int.

unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

Clang 3.4+ introduced arithmetic-overflow builtins with fixed types, but they are much less flexible and Clang 3.8 has been available for a long time now. Look for __builtin_umull_overflow if you need to use this despite the more convenient newer alternative.

Visual Studio's cl.exe doesn't have direct equivalents. For unsigned additions and subtractions, including <intrin.h> will allow you to use addcarry_uNN and subborrow_uNN (where NN is the number of bits, like addcarry_u8 or subborrow_u64). Their signature is a bit obtuse:

unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);

c_in/b_in is the carry/borrow flag on input, and the return value is the carry/borrow on output. It does not appear to have equivalents for signed operations or multiplications.

Otherwise, Clang for Windows is now production-ready (good enough for Chrome), so that could be an option, too.

Solution 3

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

Similarly, you can estimate the maximum size of the result of a to the power of b like this:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).

Solution 4

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.

You could also test for the possibility of overflow before you perform the multiplication:

if ( b > ULONG_MAX / a ) // a * b would overflow

Solution 5

Warning: GCC can optimize away an overflow check when compiling with -O2. The option -Wall will give you a warning in some cases like

if (a + b < a) { /* Deal with overflow */ }

but not in this example:

b = abs(a);
if (b < 0) { /* Deal with overflow */ }

The only safe way is to check for overflow before it occurs, as described in the CERT paper, and this would be incredibly tedious to use systematically.

Compiling with -fwrapv solves the problem, but disables some optimizations.

We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.

View more solutions

386,068

Author by

Rickyx

Updated on February 02, 2022

Comments

Rickyx over 2 years
I was writing a program in C++ to find all solutions of a^b = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and it ran a digit-counting routine each time on a, b and a^b to check if the digits condition was satisfied.

However, spurious solutions can be generated when a^b overflows the integer limit. I ended up checking for this using code like:
```
unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow
```
Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.

Beware that signed int overflow is undefined behaviour in C and C++, and thus you have to detect it without actually causing it. For signed int overflow before addition, see Detecting signed overflow in C/C++.
James Curran over 15 years

Inline assembly ties you to one architecture and causes the compiler to shutdown many optimizations. It should be generally avoided.
Jonas Engström over 15 years

...or use numeric_limits<TYPE>::max()
Nils Pipenbrinck over 15 years

inline assembler is no C/C++ feature and platform independent. On x86 you can use the into instruction istead of branches btw.
Rickyx over 15 years

Heh... what I didn't say was that I'm asking this question in preparation for writing a program to solve a problem with larger numbers, in which I'm already using long long int. Since long long int is not (allegedly) in the C++ standard, I stuck with the 32-bit version to avoid confusion.
Thelema almost 15 years

Don't forget to handle a=0 -- division breaks then.
Rickyx over 14 years

Unsigned integers don't strictly overflow in C++ either (ISO/IEC 14882:2003 3.9.1.4). My use of 'overflow' in the question was the more colloquial meaning, intended to include the well-defined wrapping of unsigned types, since I was interested in unsigned ints representing mathematical positive integers, not positive integers mod 2^32 (or 2^64). The distinction between overflow as a deviation from mathematical infinite-sized integer behaviour, and overflow as an undefined behaviour in the language seems rarely to be made explicit.
Oliver Hallam over 14 years

and of course you could rename highestOneBitPosition to log :)
Head Geek over 14 years

Yes, it's the same operation as log2, but that wouldn't necessarily be as obvious to someone who didn't have a mathematical background.
clahey about 14 years

Doesn't this algorithm underestimate the safe answers? 2^31 + 0 would detect as unsafe since highestOneBitPosition(2^31) = 32. (2^32 - 1) * 1 would detect as unsafe since 32 + 1 > 32. 1 ^ 100 would detect as unsafe since 1 * 100 > 32.
Head Geek about 14 years

Not quite sure where you're coming from. Those functions are meant to determine whether a mathematical operation is safe from overflowing. Unless the code explicitly checks for a zero or one multiplicand, (2^32 - 1) * 1 can't be determined as safe without doing the entire operation.
caf about 14 years

That test doesn't need to be x >= 0 - x > 0 will suffice (if x == 0, then x + a can't overflow for obvious reasons).
Blaisorblade about 14 years

Except that you can't override operators for builtin types. You'd need to write a class for that and rewrite client code to use it.
Nate Kohl over 13 years

Maybe it varies: -ftrapv seems to work fine using GCC 4.3.4 on a Cygwin box. There's an example at stackoverflow.com/questions/5005379/…
jww about 13 years

"highestOneBitPosition" - count leading zeros? publib.boulder.ibm.com/infocenter/aix/v6r1/index.jsp?topic=/‌…
jww about 13 years

@Thelema: "Don't forget to handle a=0" - and INT_MIN / -1.
SamB over 12 years

Note that compilers may only do this with signed integer types; overflow is completely defined for the unsigned integer types. Still, yes, it's quite a dangerous trap!
Rickyx about 12 years

On POSIX systems at least, the SIGFPE signal can be be enabled for floating point under/overflows.
DX-MON almost 12 years

I disagree due to computation theory.. consider the following: y > x, value overflows, y is only bigger than x due to the sign bit being set (1 + 255, for example, for unsigned chars) testing value and x would result in overflow = false - hence the use of logical or to prevent this broken behaviour..
Gunther Piez almost 12 years

The test works for the numbers you give (x:=1, y:=255, size = uint8_t): value will be 0 (1+255) and 0<1 is true. It works indeed for every number pair.
DX-MON almost 12 years

Hmm, you make a good point. I still stick on the side of safety using the or trick though as any good compiler would optimise it out provider you are indeed correct for all inputs, including non-overflowing numbers such as "0 + 4" where the result would not be overflow.
Gunther Piez almost 12 years

If there is an overflow, than x+y>=256 and value=x+y-256. Because y<256 always holds true, (y-256) is negative and so value < x is always true. The proof for the non overflowing case is quite similar.
DX-MON almost 12 years

+1 - you make a valid point. I accept your argument for the simplification and will create an amendment to my original posting containing the amendment.
jw013 over 11 years

I'd advise using ULONG_MAX which is easier to type and more portable than hard-coding 0x100000000.
interjay about 11 years

This doesn't work when long and long long are the same size (e.g. on many 64-bit compilers).
Michi almost 11 years

according to your multiplication_is_safe 0x8000 * 0x10000 would overflow (bit positions are 16 + 17 = 33 which is > 32), although it doesn't because 0x8000 * 0x10000 = 0x80000000 which obviously still fits into a unsigned 32 bit int. This is just one out of may examples for which this codes does not work. 0x8000 * 0x10001, ...
Head Geek almost 11 years

@GT_mh: Your point? As I said, it's not perfect; it's a rule-of-thumb that will definitively say when something is safe, but there's no way to determine whether every calculation would be okay without doing the full calculation. 0x8000 * 0x10000 isn't "safe," by this definition, even though it turns out to be okay.
Pacerier almost 11 years

@HeadGeek, as for detecting overflow for addition a + b, why not simply use if(b > max - a)?
Pacerier almost 11 years

@pmg, is there a supporting quote from the standard?
Mysticial over 10 years

Unfortunately, this is a Windows-only solution. Other platforms do not have ULARGE_INTEGER.
nonsensickle over 10 years

To find out the position of the most significant bit you can use the clz instruction in ARM (infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui049‌1c/…). I'm not sure about x86 or x64 but I suspect the most efficient way is to do some form of a binary search with shift operators.
nonsensickle over 10 years

However, for multiplication the solution he has given is already optimal. Multiplication and division are single instruction operations where finding the number of leading zeroes (the position of the highest bit) are not necessarily (excluding the ARM example I gave earlier).
Head Geek over 10 years

@Pacerier: That should work too, I believe. There's also an even more efficient way to do it (for addition only) by using bit-manipulation operators to test the high-bit. I only included the addition part to show how addition fits into the theory I was trying to explain.
ZAB over 10 years

This patch is now merged to clang codebase among other sanitizers, see my answer.
ZAB over 10 years

You both are right. -ftrapv do the job but only for signed integers
Gareth Rees over 10 years

The multiplication a_bits*b in exponentiation_is_safe might overflow, so you need to test multiplication_is_safe(a_bits, b) first.
mr5 over 10 years

How about subtraction_is_safe()? I came up with that problem but I dunno how to implement it myself, would you...Thanks :D
Head Geek over 10 years

With unsigned integers, that's extremely simple -- just make sure the first one is larger than the second. With signed integers it's a little more complex, you have to check the signs too, but not too much. If I have time, I'll edit the answer above to include that, but it won't be today.
JanKanis over 10 years

While converting to floating point and back works, it is (according to my testing on a 32bit machine) much slower than the other solutions.
the swine about 10 years

This is not correct. Carry might bring bits from lower positions that will cause overflow. Consider adding UINT_MAX + 1. After masking, a will have the high bit set, but 1 will become zero and therefore the function will return true, addition is safe - yet you are headed directly for overflow.
the swine about 10 years

What if b == ULONG_MAX / a? Then it can still fit, given that a divides ULONG_MAX without residual.
SamB over 9 years

Relying on signals to tell you about overflows would be really slow anyway.
Brett Hale over 9 years

This is pretty much useless. When it returns 'safe' - it is. Otherwise, it's still necessary to perform the full multiplication just to be sure it really is safe. Given the potentially huge range of values that report false negatives, this has no real value, when algorithms exist to return the correct answer, without a validation step.
Brett Hale over 9 years

The use of 'significant bits' is not robust either. If a has m significant bits, and b has n significant bits, the product has m + n or m + n - 1 significant bits. A basic property of bit-wise multiplication. In short, this is all a lot of work for an indeterminate result. The msb calculations are just more overhead.
Head Geek over 9 years

Knowing whether a calculation is definitely safe is often all you need.
Tyler Durden over 9 years

Agreeing with Brett Hale, the posted method for unsigned multiplication here is just wrong.
Ben Voigt over 9 years

Not all 32-bit machines are Intel x86-compatible, and not all compilers support gnu assembly syntax (I find it funny that you post code which tests _MSC_VER although MS compiles will all reject the code).
Matt over 9 years

@DX-MON: Your first method is necessary if you also have a carry bit from a previous add. uint32_t x[N], y[N], z[N], carry=0; for (int i = 0; i < N; i++) { z[i] = x[i] + y[i] + carry; carry = z[i] < (x[i] | y[i]); } If you don't or the values, you will not be able to distinguish between one operand and the carry bit being zero and one operand being 0xffffffff and the carry bit being one.
Alec Teal about 9 years

There is a lot wrong with this answer, while yes, would overflow implies these will return true, there's a lot of false positives. A poor answer.
DX-MON about 9 years

You make a fine point, @Matt, for the summation/accumulation case. well caught.
Head Geek about 9 years

It does have false positives, but it's also simple and doesn't require convoluted and expensive partial calculations. It makes a good and cheap first-pass algorithm, which in many cases is sufficient.
dvicino almost 9 years

You can obtain highestOneBitPosition just calling the C function lsf()
Richard Cook over 8 years

__builtin_sub_overflow is definitely not in Clang 3.4.
Paul Chernoch over 8 years

A reviewer detected a missing case for subtraction part 2. I agree that 0 - MINVALUE would overflow. So testing for this case should be added.
user253751 over 8 years

"I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring." - so for(int k = 0; k < 5; k++) {...} should raise a warning?
user253751 over 8 years

@SamB Only if overflows were expected to be frequent.
RichardBruce over 8 years

You perhaps want to use a CLZ (count leading zero) instruction to help find the highest 1 quickly. Most modern architectures will provide this
zneak over 8 years

@RichardCook, it took some time but Clang has the generic builtins as of version 3.9.
zneak over 8 years

@tambre, I don't think there are.
Lekensteyn about 8 years

According to the docs, __builtin_add_overflow and friends should already be available on Clang 3.8.
MikeMB about 8 years

@immibis: Why should it? The values of k can easily be determined at compile time. The compiler doesn't have to make any assumptions.
user253751 about 8 years

@MikeMB So for(int k = 0; k < 5; k++) {...} should raise a warning when optimizations are disabled (so the compiler hasn't gone to the effort to prove that k is bounded)?
MikeMB about 8 years

@immibis: To quote the above: "I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring."
user253751 about 8 years

@MikeMB Oh, I confused that with "the compiler should issue a warning whenever overflow could occur".
user253751 about 8 years

@MikeMB So what you mean is: the compiler should issue a warning by default when making an optimization that relies on overflow not occurring unless it can prove that overflow won't occur. Then you end up with warnings for things like 1 << n.
MikeMB about 8 years

@immibis: I'm not really in favor of those kinds of warnings in general, because a) I fear they would become quite noisy and b) would probably only produce a meaningful message in trivial cases. But I really don't see how your particular examples would produce a warning. What optimization would rely on a leftshift not overflowing? Actually, besides the classical example posted by A Fog, I know very few optimizations that are based on the assumption that integers won't overflow.
user253751 about 8 years

@MikeMB The optimization where the compiler doesn't bother to check that n is less than 32, before emitting a shift instruction that only uses the lower 5 bits of n?
MikeMB about 8 years

Let us continue this discussion in chat.
Navin about 8 years

-1, Too many false positives to be of any use. Unless this is consistently faster than the correct answer, I don't see the point.
Franz D. over 7 years

I like this approach... However, be careful: the multiplication overflow detection assumes a posiive x. For x == 0, it leads to divide by zero detection, and for negative x, it always erroneously detects overflow.
chux - Reinstate Monica over 7 years

if ((a < INT_MIN / x)) test is too late. A if (x == -1) test is needed first.
Toby Speight over 7 years

Usually, I'd say that repeating the calculation in floating point is a bad idea, but for this specific case of exponentiation a^c, it may well be more efficient. But the test should be (c * log(a) < max_log), where const double max_log = log(UINT_MAX)
dimm over 7 years

This seems slow. For unsigned generally you can do the operation and then you can check for overflow.
David Stone about 7 years

If a signed value overflows, the behavior of your program is undefined. It is not guaranteed to wrap around.
Mudit Jain over 6 years

Thanks. This works great. Any idea what's the corresponding function for visual c++? Can't seem to find them.
Tom Roggero over 6 years

why are you not using 9.876.543.210 as the upper limit?
hdante over 6 years

Because 2 digits must be used for the left hand side of the equation.
Arne Vogel about 6 years

<pedantic>Integers do not underflow (= become too close to zero to be represented with any accuracy). 1.0e-200 / 1.0e200 would be an example of an actual underflow, assuming IEEE doubles. The correct term here, instead, is negative overflow.</pedantic>
Arne Vogel about 6 years

To be precise, the reason why integers are not considered to underflow is because of defined truncation behavior, e.g. 1/INT_MAX could well be considered underflow, but the language simply mandates truncation to zero.
Pastafarianist about 6 years

highestOneBitPosition can be implemented in GCC as 32 - __builtin_clz(a) for uint32_t and 64 - __builtin_clzl(a) for uint64_t.
Paul Childs almost 6 years

Not that it makes a difference, but the upper limit can actually be taken as 98765410 as you have stated the values on the LHS are > 1
supercat over 5 years

With addition or subtraction, using a modular-arithmetic type (e.g. an unsigned type in C) and checking wraparound is usually easier than trying to predict overflow. For multiplication, overflow will always occur if both values exceeds the square root of the maximum product, and never occur if neither value does. If one value does (64-bit unsigned types used for illustration), compute (big>>32)*small and (big & 0xFFFFFFFF)*small. Neither multiplication will overflow. If the first product fits in 32 bits, shift it left 32, add the second, and check for wrap-around.
Andrey Portnoy over 5 years

Who needs these complex rearrangements, just use if (a + x > INT_MAX) instead ;)
pmg over 5 years

@AndreyPortnoy: a + x (a value of type int) cannot ever be greater than INT_MAX! Much as, in a 24-hour clock, hour1 + hour2 cannot ever be greater than 23 (eg: 18 + 10 overflows to 04)
Andrey Portnoy over 5 years

@pmg I was kidding, note the ;) ;) But someone with a math background might have that instinct to simplify and rearrange.
supercat over 5 years

I didn't see anything useful at the link, but that sounds like a model I've long advocated. It supports the vast majority of useful optimizations, while also supporting useful semantic guarantees that most implementations can provide at essentially no charge. If code knows that the inputs to a function will be valid in all cases where the output matters, but doesn't know in advance whether the output will matter, being able to let overflows happen in cases where they won't affect anything may be easier and more efficient than having to prevent them at all costs.
user1593842 about 5 years

the top voted answer is an excellent answer to something that was not asked. pmg even acknowledged that. If unsigned integer overflow is something that may offend language lawyers (even though the intent is quite clear and I bet is a term incorrectly used by many), I think the best answer would have been "unsigned int does not overflow. Please ask a new question about how to detect if an operation would wrap around".
chqrlie almost 5 years

You should use the unsigned 128-bit type __uint128 to avoid signed overflow and right shifting a negative value.
dot_Sp0T over 4 years

@pmg it seems that the general case test for overflows of multiplication doesn't work properly. E.g. take the multiplication 15 * -6734, it will result in -101010 but the test will say it'll overflow
pmg over 4 years

good catch @dot_Sp0t, I wrote those conditions erroneously assuming a and x have the same sign.
Peter Mortensen over 4 years

The link is broken: HTTP 403: Forbidden
Peter Mortensen over 4 years

What are "compiler-dependent instincts" and "overflow instincts"? Do you mean "intrinsic functions"? Do you have a reference? (Please respond by editing your answer, not here in comments (as appropriate).)
supercat over 4 years

@MikeMB: Most of the optimizations I'd regard as useful would effectively involve allowing integer operations to behave as though the upper bits were indeterminate, but gcc will sometimes generate nonsensical code when overflows occur even in cases where the upper bits would be totally ignored.
jaques-sam about 4 years

I think this answer should be selected as best answer and the C++ standard should introduce a generic way of doing this. @chris-johnson
jaques-sam about 4 years

Funny that, performance wise, a multiplication is rather fast compared to a division and you're adding a division for every multiplication. This doesn't sound like the solution.
jmrk almost 4 years

The multiplication "solution" is wrong. For example, x = 0x80000000 and y = 2 would overflow, but since (y >> 16) == 0 in this case, the code does not detect that. I see no easy fix; I suggest to delete that part of the answer.
DX-MON almost 4 years

Thank you for providing a counter-example for the multiplication case. The simple way to fix this is to perform more of the Karatsuba decomposition (en.wikipedia.org/wiki/Karatsuba_algorithm) for the multiplication and if any of those sub-parts results in bits in this high 32-bit section, the result is overflow.
Ankit Roy about 3 years

Great info! Note that dividing a signed integer can also overflow (specifically INT_MIN / -1, since abs(INT_MIN) == INT_MAX + 1 with the usual two's complement representation), but there don't seem to be corresponding builtin functions.
yuri kilochek about 3 years

@Matt, that fails when x[i] and y[i] are both 0xFFFFFFFF and carry is 1. You have to test for overflow before adding carry, and at that point you might as well ditch the |.
PersonWithName almost 3 years

Doesn't this invoke undefined behavior? Signed overflow is undefined behavior. Correct me if I'm wrong, but even if you don't use the result, you get UB. stackoverflow.com/questions/16188263/…
PersonWithName almost 3 years

You might have to do the multiplication in assembly too if you want to avoid UB.
Fayeure almost 3 years

Unsigned integers does overflow and underflow, when you do (unsigned int)-1 you get UINT_MAX, same for UINT_MAX + 1, you get 0
Matt almost 3 years

@yurikilochek, you make a good point. It's been forever since I've thought about this, but I'm not sure how I missed that.
mtraceur over 2 years

Use binary search instead of top-down loop in the pure C implementation: something like size_t highestOneBitPosition(T a) { size_t shift = (sizeof(T) * CHAR_BIT) / 2, position = 0; while (a) { if(a >> shift) { a >>= shift; position += shift; } shift /= 2; } return position; }, sorry for the format, untested, I just improvised this in the comment box. Instead of O(n) it's O(log(n)) which is great. Small downside: you pay one more branch and a couple more instructions per loop, and for a random input value those branches are less consistent and so is maybe less branch-predictor friendly.
mtraceur over 2 years

A lot of the critique of this answer is needlessly condemning, as if we can't just trivially refine this answer's solution's concept. If highest_bit_position(a) + highest_bit_position(b) < n then multiplication doesn't overfull, if > n it ddefinitely does overflow, and if == n then we gotta do further checking. Since the majority of inputs won't hit the == n case, it would be decently performant in the typical case.
Vega4 over 2 years

if (a > INT_MAX / x) is true say for x=3 and a=2 .... no overflow here though;]
vitiral about 2 years

This is by far the best answer and should be the accepted one IMO.
Medinoc about 2 years

@MuditJain With basic pattern recognition of Microsoft's adoption of updated C standards, we can expect C23 features to be in Visual Studio by 2037.