CODEWITHSUNDEEP
ccastingintegerabsolute-valuebranchless
bozeng
bozeng

Reputation: 265

What does (unsigned) do in this abs() function?

There are many ways to implement abs() with or without branching. I came across this one:

r = (v < 0) ? -(unsigned)v : v;

Does this use branching or is it branchless?

And why can it not just use -v, instead of -(unsigned)v? What does the (unsigned) do here? Why does it give more correct results than -v?

Upvotes: 1

Views: 319

Answers (5)

rcgldr
rcgldr

Reputation: 28826

For a twos complement signed integer a , assuming that sizeof(int)*8 is the number of bits in a signed integer, and that a right shift on a signed integer copies the sign bit so that a >> (sizeof(int)*8-1)) is 0 or -1, and you can use:

int a;
/* ... */
    a = (a + (a >> (sizeof(int)*8-1))) ^ (a >> (sizeof(int)*8-1));

Upvotes: 0

Jobs
Jobs

Reputation: 3377

The C ternary operator works as follows:

condition ? value_if_true : value_if_false

The ternary operator is therefore saying:

If V<0, then the value of r becomes -V, thus effectively converting the negative number to a positive number. Else, (when v is a positive number at the beginning), set r equal to v.

The unsigned keyword is generally not necessary and is simply there to indicate that you are storing -V as an unsigned number. You can do this because you know for sure that -V is going to be a positive number.

However, it is good practice to declare -v unsigned. When v is specifically –2,147,483,648, marking -v as unsigned becomes necessary, because there is no positive 2,147,783,648 signed int. The largest signed int is 2,147,783,647.

The range of values for signed int is –2,147,483,648 to 2,147,483,647, while the range of values for unsigned int is 0 to 4,294,967,295.

As you can see, the range for unsigned int is large enough to hold that one particular number, 2,147,783,648, while the range for signed int isn't.

Upvotes: 1

Arlie Stephens
Arlie Stephens

Reputation: 1176

Negative numbers are generally represented in two's complement form. One effect of this is that the largest possible negative integer which can be represented in some number of bits is 1 farther from zero than the largest possible positive value.

Let's use a 3 bit integer as an example

000 is 0
001 is 1 111 is -1
010 is 2 110 is -2 011 is 3 101 is -3

What is 100 ? It's the next value in both series.

IIRC, it's -4, and there's no signed 3 bit representation of +4.

If we negate 100 while staying within our 3 bit integral type, there's no valid value. We need to use a wider integral type to represent it. An unsigned 3 bit type has a range of values from 0 to 7 - 4 is legal.

If you convert signed to unsigned, you keep the same bit value.

This plus type promotion rules seem to be what's happening

I don't know the specifics of the type promotion rules, that cause signed 111 (-1) --> unsigned 111 (7) then - unsigned 111 -> 001 (1) and signed 100 (-4) --> unsigned 100 (4) then - unsigned 100 -> 100 (4)

But that's got to be the gist of it.

Upvotes: 0

ouah
ouah

Reputation: 145839

 r=(v<0)?-(unsigned)v : v

There are some ways to compute abs without branching but this one is not one of them as < and ?: operators are usually translated to branching instructions.

Assuming r is of type unsigned int, the cast to unsigned is here to get a specified behavior when v value is INT_MIN. Without the cast, -v would be undefined behavior when v is INT_MIN (as -INT_MIN is undefined behavior in C).

Upvotes: 3

Arlie Stephens
Arlie Stephens

Reputation: 1176

The ? : construct in C is effectively a branch.

r = (v<0) ? - (unsigned)v : v;

is just another way of writing

if (v < 0) {
  r = - (unsigned)v;
} else {
  r = v;
}

More correctly, the resulting compiled code for each of these could reasonably be identical.

Upvotes: -1

Related Questions