CODEWITHSUNDEEP
c++ccasting
ILove Anime
ILove Anime

Reputation: 59

Computational complexity for casting int to unsigned vs complexity for comparing values

I just wanted to know which operation is faster in C/C++, as well as what the computational complexity for a type cast is.

Typecasting x to an unsigned integer like so:

(unsigned int) x

or

Performing a comparison between x and a constant:

x<0

edit: computational complexity as in which process requires the least amount of bit operations on a low level aspect of the hardware in order to successfully carry out the instruction.

edit #2: So to give some context what I'm specifically trying to do is seeing if reducing 

if( x < 0)

into 

if((((unsigned int)x)>>(((sizeof(int))<<3)-1)))

would be more efficient or not if done over 100,000,000 times, with large quantities for x, above/below (+/-)50,000,000

Upvotes: 1

Views: 1305

Answers (3)

Yuushi
Yuushi

Reputation: 26040

To answer your actual edited question, it is unlikely to be faster. In the best case, if x is known at compile time, the compiler will be able to optimize out the branch completely in both cases.

If x is a run-time value, then the first will produce a single test instruction. The second will likely produce a shift-right immediate followed by a test instruction.

Upvotes: 0

cmaster - reinstate monica
cmaster - reinstate monica

Reputation: 40625

The monster if((((unsigned int)x)>>(((sizeof(int))<<3)-1))) will be slower than the straight forward if(x < 0): Both versions need to compare a value against zero, but your monster adds a shift before the comparison can take place.

Upvotes: 0

Tony Delroy
Tony Delroy

Reputation: 106096

(unsigned int) x is - for the near-universal 2's complement notation - a compile time operation: you're telling the compiler to treat the content of x as an unsigned value, which doesn't require any runtime machine-code instructions in and of itself, but may change the machine code instructions it emits to support the usage made of the unsigned value, or even cause dead-code elimination optimisations, for example the following could be eliminated completely after the cast:

if ((unsigned int)my_unsigned_int >= 0)

The relevant C++ Standard quote (my boldfacing):

If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source integer (modulo 2n where n is the number of bits used to represent the unsigned type). [ Note: In a two’s complement representation, this conversion is conceptual and there is no change in the bit pattern (if there is no truncation). —end note ]

There could be an actual bitwise change requiring an operation on some bizarre hardware using 1's complement or sign/magnitude representations. (Thanks Yuushi for highlighting this in comments).

That contrasts with x < 0, which - for a signed x about which the compiler has no special knowledge, does require a CPU/machine-code instruction to evaluate (if the result is used) and corresponding runtime. That comparison instruction tends to take 1 "cycle" on even older CPUs, but do keep in mind that modern CPU pipelines can execute many such instruction in parallel during a single cycle.

if( x < 0) vs if((((unsigned int)x)>>(((sizeof(int))<<3)-1))) - faster?

The first will always be at least as fast as the second. A comparison to zero is a bread-and-butter operation for the CPU, and the C++ compiler's certain to use an efficient opcode (machine code instruction) for it: you're wasting your time trying to improve on that.

Upvotes: 6

Related Questions