Avoiding forking in C for this operation

Question

Is there a way to remove the following if-statement to check if the value is below 0?

int a = 100; int b = 200; int c = a - b; if (c < 0) { c += 3600; } 

The value of c must be between 0 and 3600. Both a and b signed. The value of a should also be between 0 and 3600. (yes, this is a count value of 0.1 degrees). The value gets reset with an interrupt up to 3600, but if this interrupt arrives too late, it overflows, which is not a problem, but the software should still cope with this. What is he doing.

We do this if (c < 0) check in some places where we calculate positions. (Calculation of a new position, etc.)

I used the python modulo statement to use the divider signature, in which our compiler (C89) uses the signature.

Is there a way to do this calculation differently? Examples of results:

  a - b = c 100 - 200 = 3500 200 - 100 = 100 

Answer 1

Good question! How about this?

 c += 3600 * (c < 0); 

This is one way to save branch predictor slots.

Answer 2

How about this (assuming 32 bit ints):

 c += 3600 & (c >> 31); 

c >> 31 sets all bits to the original MSB, which is 1 for negative numbers, and 0 for others in the 2-pad.

A negative shift of the number on the right is formally determined by the implementation in accordance with standard C documents, however, it is almost always implemented with MSB copying (common processors can do this in one command).

This will undoubtedly lead to the absence of branches, unlike (c < 0) , which can be implemented using the branch in some cases.

Answer 3

Why are you worried about the affiliate? [The reason is explained in the comments on the question.]

An alternative is something like:

 ((a - b) + 3600) % 3600 

This suggests that a and b already in the range 0..3600 ; if they are not under control, a more general solution is that Drew McGowan suggests :

 ((a - b) % 3600 + 3600) % 3600 

Skipping a branch must be very expensive to make this calculation useful.

Answer 4

@skjaidev showed how to do this without branching. Here's how to automatically avoid multiplication when int are two additions:

 #if ((3600 & -0) == 0) && ((3600 & -1) == 3600) c += 3600 & -(c < 0); #else c += 3600 * (c < 0); #endif 

Answer 5

What you want to do is modular arithmetic. Your machine with two additions already does this with integer math. Thus, by comparing your values ​​in arithmetic with two additions, you can get the modolo operation for free.

The trick represents your angle as a fraction of 360 degrees between 0 and 1 epsilon. Of course, then your constant angles should be displayed the same way, but it should not be hard; it's just the math we can hide in the transform function (er, macro).

The meaning in this idea is that if you add or subtract angles, you get the value, part of which you want and whose whole part you want to throw away. If we represent a fraction as a 32-bit fixed-point number with a binary point of 2 ^ 32 (for example, to the left of what is usually considered a sign bit), any fraction overflows just drop from the top of the 32-bit value for free. So, you do all the math, and the removal of "overflow" is free.

So, I rewrote your code (keeping the idea of ​​degrees 10 times):

  typedef unsigned int32 angle; // angle*3600/(2^32) represents degrees #define angle_scale_factor 1193046.47111111 // = 2^32/3600 #define make_angle(degrees) (unsigned int32)((degrees%3600)*angle_scale_factor ) #define make_degrees(angle) (angle/(angle_scale_factor*10)) // produces float number ... angle a = make_angle(100); // compiler presumably does compile-time math to compute 119304647 angle b = make_angle(200); // = 238609294 angle c = a - b; // compiler should generate integer subtract, which computes 4175662649 #if 0 // no need for this at all; other solutions execute real code to do something here if (c < 0) // this can't happen { c += 3600; } // this is the wrong representation for our variant #endif // speed doesn't matter here, we're doing output: printf("final angle %f4.2 = \n", make_degrees(c)); // should print 350.00 

I did not compile or run this code.

Changes made to make these degrees of time 100 or 1 fairly easy; change the angle_scale_factor parameter. If you have a 16-bit machine, switching to 16 bit is likewise easier; if you have 32 bits and you still want to do only 16-bit math, you will need to mask the value to be printed to 16 bits.

This solution has another nice feature: you documented which variables are angles (and have funny ideas). The OP source code just called them ints, but that’s not what they represent; the future maintainer will be surprised by the source code, especially if he finds a subtraction extracted from the variables.