Does unsigned math require more CPU instructions?

Question

Take an C++ integral variable i, and suppose that you're multiplying its value by 2.

If i has signedness, I believe that the operation is somewhat equivalent, at least mathematically, to:

i = i << 1;

But if i's type is unsigned, then since unsigned values do not overflow but are performed modulo their range, presumably the operation is something like this:

i = (i << 1) & (decltype(i))-1;

Now, I figure that the actual machine instructions will probably be more concise than a sequence of shifts for multiplication. But would a modern, say x86, CPU have a specific instruction for unsigned/modulo math? Or will performing math with unsigned values tend to cost an additional instruction, when compared to math with signed values?

(Yes, it would be ridiculous to care about this whilst programming; I'm interested out of pure curiosity.)

Answer 1

As the others already wrote: It does not matter for the CPU. Signed and unsigned instructions take the same time, Some operations in unsigned arithmetic are even easier to do and may require a cycle less than the signed variant (multi precision division is one example).

However, this is only half of the story.

C++ defines signed integer overflows as undefined behavior and unsigned integers as modulo2. This offers completely different optimization opportunities which lead to different code.

One example:

int foo (int a)
{
  return a * 1000 / 500;
}

unsigned bar (unsigned a)
{
  return a * 1000 / 500;
}

Here foo can be optimied to:

int foo (int a)
{
  return a * 2;
}

And bar will stay the same it is.

Note that mathematically these two functions are the same, but they start to give different results if the argument exceeds INT_MAX/1000.

Since the effect of signed overflows is undefined the compiler has the option to just pretend there is no INT_MAX when it comes to simplify expressions. For unsigned arithmetic this is not the case and the compiler has to emit code that does the multiplication and division. This is of course slower than the optimized variant.

Note: Most compilers are conservative when it comes to such optimizations and only enable them if you ask for them because they tend to break code and overflow checks. Other compilers, especially in the embedded and DSP world otoh always do these kind of optimizations even at low optimization levels. The programmers who write for these kind of machines are aware of the subtle details, so this is rarely a problem.

OTOH we've discussed stories where C/C++ programmers fall into this trap more than once on stackoverflow.

Answer 2

No, it doesn't take more instructions, at least on x86.

For some operations (e.g. addition and subtraction), the same instruction is used for both signed and unsigned types. This is possible since they work the same when using 2's complement representation of signed values.

There is also no difference for left-shift: The leftmost bit is simply discarded by the hardware, and there is no need to perform a bitwise-and like in your example.

For other operations (e.g. right-shift), there are separate instructions: SHR (shift right) for unsigned values and SAR (shift arithmetic right) for signed values, which preserves the sign bit.

There are also separate instructions for signed/unsigned multiplication and division: MUL/IMUL and DIV/IDIV, where IMUL and IDIV are used for signed values.

Answer 3

Assuming wraparound overflow, which is what most (all?) CPU arithmetic instructions on two's complement hardware do anyway, << for unsigned types is equivalent to the multiplication. So the only problem you have is when you're doing arithmetic with a type that's smaller than the register used to contain it.

The rules about promotion to at least int (or unsigned int) in arithmetic expressions are pretty much designed to avoid this happening: when you multiply, say, an unsigned short by 2 the result is an int (or unsigned int if short and int are the same size). Whichever it is, there's no need to take any modulus when the register size matches the type. And with two's complement, you don't need different instructions for signed and unsigned C++ multiplication anyway: wraparound overflow covers both unless the hardware offers an overflow bit and you care about its value (-1 * 2 would be an unsigned overflow, but not a signed overflow, even though the resulting bit-pattern is the same).

The only time a mask might be required is if/when you convert the result back to unsigned short. Even then, I think that with care an implementation can sometimes leave additional "irrelevant" bits in the top of an int-sized register used to hold an intermediate unsigned short value. You know that those extra top bits don't affect the modulo results of addition, multiplication or subtraction, and that they would be masked off if the value is stored to memory (assuming an instruction that stores the bottom 2 bytes of an int-sized register to 2 bytes of memory, the modulus basically is free). So the implementation just has to be careful to mask before division, right-shift, comparison, and whatever else I've forgotten, or else use appropriate instructions if available.

Answer 4

I think you have it the wrong way round: On unsigned data types, bit shifting does exactly what it says on the tin, and unoccupied bits are filled with zeros. This causes the correct modular arithmetic operations on the types's values for left-shift, which is multiplication. Right-shift has no arithmetic analogue because Z/nZ is not a division ring in general and there is no notion of division; right-shift is just truncating division.

On the other hand, signed types suffer from an ambiguity, because there are different ways of interpreting a bit pattern as a signed integer. With left-shift on 2's-complement you will get the expected "wrap-around" for multiplication, but there's no canonical choice of right-shift behaviour. In the old C standard I believe that was fully implementation defined, but I think C99 made that behaviour specific.

Answer 5

As far as I know, then most CPUs possess unsigned operations in hardware, and I'm quite certain that x86 does.

Answer 6

Unsigned math does overflow and hence is implicitly modulo their respective range.

Answer 7

interjay's answer covers the basics. A couple more details:

Now, I figure that the actual machine instructions will probably be more concise than a sequence of shifts for multiplication.

That depends on the processor. In the old days, when transistors were expensive, processors like the 6500 and 6800 had instructions that only shifted one bit left or right at a time.

Later, when chips got bigger and had more bits in an opcode for parameters, "barrel shifters" were implemented which could shift an arbitrary number of bits in a single cycle. This is what modern CPUs use.

Or will performing math with unsigned values tend to cost an additional instruction, when compared to math with signed values?

Never. When an operation would differ between unsigned and signed, there will be separate instructions for each.