Getting the modulus of a number without a comparison operation
We take a simple code:
void main() {
int x = abs(-1);
}
Assembling and disassembling it:
$ gcc sample.c -o sample && objdump -d ./sample
Getting a listing where there is no conditional command:
80483a1: e8 ee ff ff ff call 8048394 <some>
80483a6: 89 c2 mov %eax,%edx
80483a8: c1 fa 1f sar $0x1f,%edx
80483ab: 31 d0 xor %edx,%eax
80483ad: 29 d0 sub %edx,%eax
How can I get the absolute value of an integer in C/C++ without a comparison operation?
4 answers
The assembly sar operation is a normal right shift. Here is your code:
int myabs(int x)
{
//mov %eax,%edx
//sar $0x1f,%edx
int minus_flag = x>>0x1F;//0x1F = 31
//xor %edx,%eax
int y = minus_flag ^ x;
//sub %edx,%eax
y -=minus_flag;
return y;
}
I'm more familiar with Java, so I won't write the code in C in order not to look stupid :) But from an algorithmic point of view, it should look something like this:
(I believe that in C/C++, the representation of a signed integer is done using additional code)
- Copy the first bit somewhere.
- Create a new integer variable of the same size.
- Copy the value of the previously saved bit to all the bits of the second number.
- Apply the bitwise "exclusive or" of the first number to the second (XOR).
- Add the value of the previously stored bit to the resulting number.
Here is a table of actions for the numbers -5 and 3, which are stored in 8 bits.
Number1 add.number1 add.bit1 number2 add.number2 add.bit2
- 11111011 00000000 1 00000011 00000000 0
- 11111011 00000000 1 00000011 00000000 0
- 11111011 11111111 1 00000011 00000000 0
- 00000100 11111111 1 00000011 00000000 0
- 00000101 11111111 1 00000011 00000000 0
The algorithm is not super, but it is without comparisons :)
The first thing that came to mind immediately after reading the question is to take the square root of the square of the number:
sqrt(x*x)
Another option is, as already mentioned here, to use the knowledge of number representation and additional code and bitwise operations.
Example for 8-bit numbers
char x = -5;
char minus = (x & 0x80) >> 7; // равно 1 если x - отрицательное и 0 если положительное
char plus = (((x & 0x80) >> 7) + 1) & 1; // наоборот, равно 1, если x - положительное, и 0 если отрицательное
char abs_x = minus * (-x) + plus * x;
For int will be more difficult, because you will need to take into account a lot of features, such as bit depth (int can be 8, 16, 32, 64-bit) and byte order (Little-Endian/Big-Endian).
The algorithmic trick on which the branchless module calculation is based is the property of the additional code. The xor operation with the number -1 inverts the bits of the number, and adding 1 completes the transition to negating the number. Moreover, the number -1 itself is obtained as a sign shift to the right of the original number, if it was negative. If the number was positive, that shift would give 0, so xor and sub would not change anything. Learn more about these module calculation algorithms and their speed the works can be read here.