The Ultimate Fast Absolute Value

9e2949c18eec6140c7290e4ad2276d3b
0
blueone 101 Jun 10, 2006 at 08:38

Bitwise operation


From Wikipedia, the free encyclopedia

In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. On many computers, bitwise operations are slightly faster than addition and subtraction operations and significantly faster than multiplication and division operations.

I dont know if there was already existing fast absolute value in this forum but Id like to share my own :lol: .

This is absolute value for short int. It will return a new value as unsigned short.

unsigned short abss(ushort g)
{
if (g&32768u)
return 32768u-(g&32767u);
return (g);
}

This is absolute value for int.

unsigned int absi(int g)
{
if (g&2147483648u)
return 2147483648u-(g&2147483647u);
return (g);
}

This is absolute value for long int.

unsigned long int absl(long int g)
{
if (g&9223372036854775808llu)
return 9223372036854775808llu-(g&9223372036854775807llu);
return (g);
}

Is this what you are looking for? :lol:

float absf(float g)
{
unsigned int *gg;
gg=(unsigned int*)&g;
*(gg)&=2147483647u;
return g;
}

Another one :yes:

double absd(double g)
{
unsigned long int *gg;
gg=(unsigned long int*)&g;
*(gg)&=9223372036854775807llu;
return g;
}

Hope you like its performance :worthy: :sneaky: :lol:

12 Replies

Please log in or register to post a reply.

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Jun 10, 2006 at 09:12

I hate to be the one to tell you but these things are well known. It’s cool though that you found them on your own! :yes:

A typically faster and more importantly cleaner way to compute absolute value is:

inline int abs(int x)
{
    return (x > 0) ? x : -x;
}

On most platforms this compiles into code without branches (no jumps) and computing -x takes just one clock cycle.

For floating point we can also use the slightly nicer hexadecimal notation:

inline float abs(float x)
{
    int y = (int&)x & 0x7FFFFFFF;
    return (float&)y;
}
340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 10, 2006 at 10:54

Nick: unfortunately, your abs float code performs terrible on the xbox360 for example, as it requires the variable to be stored to memory. This has massive stalls.

And why is fabs slow anyway? The cpu only has to set a single bit to 1. Is it the long path to the FPU? Or is it that fabs itself isn’t slow, but the C runtime function around it that is?

Also, here is an abs(int) without conditional code:

int abs(int value)
{
    static const int INT_BITS = sizeof(int) * CHAR_BIT;
    int topbitreplicated = value >> (INT_BITS - 1);
    return (value ^ topbitreplicated) - topbitreplicated;
}

a shift, a xor and an add.

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Jun 10, 2006 at 18:24

@.oisyn

Nick: unfortunately, your abs float code performs terrible on the xbox360 for example, as it requires the variable to be stored to memory. This has massive stalls.

It’s functionally the same as blueone’s version. Most processors have an instruction for floating-point absolute value though. x87 has fabs, and for SSE the andps instruction can be used. On processors without such instructions I believe changing the sign in memory is the fastest method.

And why is fabs slow anyway? The cpu only has to set a single bit to 1. Is it the long path to the FPU? Or is it that fabs itself isn’t slow, but the C runtime function around it that is?

I guess it depends on the compiler and the runtime. With Visual C++ 2005 in Release mode on an x86 processor the function translates into a single fabs instruction.

Also, here is an abs(int) without conditional code:

int abs(int value)
{
    static const int INT_BITS = sizeof(int) * CHAR_BIT;
    int topbitreplicated = value >> (INT_BITS - 1);
    return (value ^ topbitreplicated) - topbitreplicated;
}

a shift, a xor and an add.

On x86 processors the fastest approach is to use this sequence:

cdq              
xor eax, edx 
sub eax, edx 

cdq is equivalent to ‘mov edx, eax; sar edx, 31’. This is also what Visual C++ 2005 uses when using the math.h abs() function.

D2448cb88a2f57130566eaa633ee7f5c
0
WatsonLadd 101 Jun 28, 2006 at 11:48

@Nick

For floating point we can also use the slightly nicer hexadecimal notation:

inline float abs(float x)
{
    int y = (int&)x & 0x7FFFFFFF;
    return (float&)y;
}

No we cannot. IEEE floating point does not set the internal representation in any way, shape or form. And you rounded.

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Jun 28, 2006 at 13:49

@WatsonLadd

No we cannot. IEEE floating point does not set the internal representation in any way, shape or form. And you rounded.

Yes we can. Yes it does. I made the value positive.

But feel free to elaborate… :huh:

6b7e1a4b42e4b47d92fdef8bf2bd8e2c
0
Jare 101 Jun 29, 2006 at 00:12

@WatsonLadd

IEEE floating point does not set the internal representation in any way, shape or form.

Obligatory Wikipedia link: http://en.wikipedia.org/wiki/IEEE_floating-point_standard

Aa49fb4fa33227edb37971712c18481c
0
jmgk 101 Jun 29, 2006 at 04:05

hi,

in x86 asm, for a int, you can do

btr eax,31

but dunno if its fast enought

jmgk

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 29, 2006 at 04:12

Unfortunately, that doesn’t work. You can’t just reset the sign bit as numbers are stored in two’s complement format.

2fcd95b0b62d18275c6b5a6f23f29791
0
tbp 101 Jun 29, 2006 at 11:16

Aliasing = bad.

Use unions.

6b7e1a4b42e4b47d92fdef8bf2bd8e2c
0
Jare 101 Jun 29, 2006 at 18:25

@Reedbeta

You can’t just reset the sign bit as numbers are stored in two’s complement format.

IEEE floating point numbers do not use two’s complement for either the mantissa or the exponent. The mantissa M is always positive, and the exponent E is stored with a bias. The sign bit is exactly what it says: a bit indicating whether the number has a negative sign in front of it or not. The link explains everything in quite clear terms.

Or did I misunderstand you?

8fd4a055522ce713cde7dd1cb4083cb2
0
martinsm 101 Jun 29, 2006 at 18:39

Reedbeta was answering to jmgk post, not yours.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 29, 2006 at 22:00

Yes. He claimed you could do it by just resetting bit 31 for integers. That would certainly work for an IEEE float stored in an integer register though. Which is exactly what Nick’s code sample does.