I was thinking how to get the absolute value of an integer without using if statement nor abs(). At first I was using shift bits left (<<), trying to get negative sign out of the range, then shift bits right back to where it be, but unfortunately it doesn't work for me. Please let me know why it isn't working and other alternatives ways to do it.
get absolute value without using abs function nor if statement
Asked Answered
From Bit Twiddling Hacks:
int v; // we want to find the absolute value of v
unsigned int r; // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v + mask) ^ mask;
I think this is the answer the OP was looking for. –
Glyptography
v >> sizeof(int) * CHAR_BIT - 1 could you please explain what this does? –
Asteria
@codeymodey: I didn't write the original, but this depends on 2's complement representation. It makes mask be equal to all 1s if the sign bit is set (since it is being shifted right and this is usually an arithmetic shift, so sign extension occurs). This is equivalent to setting mask to either -1 or 0 according to the sign bit. –
Liverpool
Okay, but what will this value ...sizeof(int) * CHAR_BIT - 1... be equal to..where is CHAR_BIT defined? –
Asteria
@codeymodey:
CHAR_BIT is the number of bits in a char, that's usually 8. It's defined in limits.h. For 32 bit ints this expression returns 31 –
Liverpool Maybe I'm missing something, but since this essentially boils down to
r = (v + 0) ^ 0 if v is positive and r = (v - 1) ^ -1 if v is negative, how could the answers it produces be correct? The former will always be 1 and the latter always a fraction (which would be truncated to 0). –
Equi @Powerlord: Where's the fraction? The only operations involved here are addition and XOR (the
^ operator). See Two's complement for more info, but it boils down to r = v if v is positive (because XORing something with zero does nothing), and r = ~v + 1 when negative (since the mask is all 1s, (x ^ ~0) == ~x) –
Liverpool @Liverpool sigh For whatever reason I was interpreting
^ as an exponent. Guess I was really derping at the time. –
Equi Isn't right shifting signed ints implementation defined ? Basically we are setting mask = 0x0 for positive and mask=0xffffffff for negative numbers. Isn't "-((unsigned)num>>31)" correct or is it slower ? –
Bebe
@ZxcvMnb: Yes, right shifting signed integers is implementation defined. As I mentioned in a previous comment, this is usually an arithmetic right shift (for instance, GCC defines this as such). I don't know if your variation is slower, though it probably requires more operations (i.e. logical shift, negate instead of a single arithmetic shift), in any case, both variations require a 2's complement representation. The linked page has more discussion, which you might find relevant. –
Liverpool
What advantage does this have over inverting the bits with the bitwise NOT and adding 1? Sure looks like it'd take longer. –
Nugent
@MarcusJ: This is done without any branching. It's helpful where branching may be expensive, or the compiler doesn't use specialized instructions for the purpose (e.g. conditional move/negate). As per Bit Twiddling Hacks,
On machines where branching is expensive, the above expression can be faster than the obvious approach, r = (v < 0) ? -(unsigned)v : v, even though the number of operations is the same.. See also here for what some variants compile to. –
Liverpool Ok, but inverting bits doesn't branch either... and thanks for the condescending tutorial on branching, I already know what that is... Why do you think I searched for branchless versions of abs? –
Nugent
@Liverpool My version is pretty similar to b_abs, except I use a ternary operator to minimize the code (I know that this doesn't stop it from branching), AND my version adds 1 if it needs to be inverted, not sure why yours didn't do that step? but the "branchless" bl_abs version uses 1 more operation, and all the other versions use the same number as regular ol' abs(); –
Nugent
@MarcusJ: There's no advantage over doing
~v + 1, other than this being a NOP when v >= 0. As shown by my link, the compiler might make this branchless anyway (as seen on x86-64 gcc, where the compiler clearly knows this trick, but is using (v ^ mask) - mask) instead). The hack is useful where you want to force this, but is ultimately just a hack. You usually would have no reason to use this. –
Liverpool Yeah yeah yeah, that's taken care of in the it's already positive case, it just returns the value alone. I meant for the signed version. I got a weird result tho, vs my version that I rewrote to use that algorithm, mine uses 1 less instruction than yours in both clang and GCC. pastebin.com/d7X3iaVk In fact, BOTH of my versions of the function, the original, and the rewriten-to-be-branchless version, use 1 less instruction on ARM64, MIPS64, and x86_64. –
Nugent
After fixing that issue, it's now equal for ARM64, but mine is STILL 1 instruction shorter on x86_64, and MIPS64, using clang 5 for the former and GCC 5.4 for the latter. Updated the pastebin –
Nugent
int abs(int v)
{
return v * ((v>0) - (v<0));
}
This code multiplies the value of v with -1 or 1 to get abs(v). Hence, inside the parenthesis will be one of -1 or 1.
If v is positive, the expression (v>0) is true and will have the value 1 while (v<0) is false (with a value 0 for false). Hence, when v is positive ((v>0) - (v<0)) = (1-0) = 1. And the whole expression is: v * (1) == v.
If v is negative, the expression (v>0) is false and will have the value 0 while (v<0) is true (value 1). Thus, for negative v, ((v>0) - (v<0)) = (0-1) = -1. And the whole expression is: v * (-1) == -v.
When v == 0, both (v<0) and (v>0) will evaluate to 0, leaving: v * 0 == 0.
just doing
v * ((v>0) - (v<0)) would be equivalent and easier to read, no? –
Balky Branchless:
int abs (int n) {
const int ret[2] = { n, -n };
return ret [n<0];
}
Note 4.7 Integral Conversions / 4: [...] If the source type is bool, the value false is converted to zero and the value true is converted to one.
"branch-free" in C, may not be once compiled. To be interesting, "branchfree" really is a property of the object code, not of the source. –
Clachan
@SteveJessop: But more seriously: Probably, with any half-decent compiler. However, this is also branchfree in the code structure :) –
Beaird
well, suppose I'd said "most likely not once compiled". Would I be right or wrong, would it even matter? ;-) –
Clachan
Nope, and my "may" was of the style of saying the classy laconian "If.". I think there isn't too much value in the question, and my answer was more an intentionally grunty demonstration :P –
Beaird
How does the hardware implement the conversion from boolean to integer? Is that done without a conditional branch? –
Centrifugal
@KerrekSB: I guess there won't be any conversion. The compiler recognizes that the operand is either 0 or 1 (see also 4.7. Integral Conversions), possibly the bool is already of the right indexing size, and ready. –
Beaird
I try this code in C, and it works.
int abs(int n){
return n*((2*n+1)%2);
}
Hope this answer will be helpful.
The best answer here!! –
Bearnard
Causes overflow for large n. –
Edelstein
It works very well and simple yet powerful logic. –
Coalfield
@KiranChuahan no,
2*n + 1 will overflow and it won't work for large numbers –
Coleville Why not just
n * (n % 2); ? –
Disturbing @NarekGhazaryan this will give you
0 for even numbers. –
Dire Assuming 32 bit signed integers (Java), you can write:
public static int abs(int x)
{
return (x + (x >> 31)) ^ (x >> 31);
}
No multiplication, no branch.
BTW, return (x ^ (x >> 31)) - (x >> 31); would work as well but it is patented. Yup!
Note: This code may take more then 10x longer then conditional statement (8bit Verison). This may be useful for Hardware programming System C etc
How do you even patent something like that? –
Cthrine
The question is for
c, not java. -1. –
Osteotome This code is as valid for c as it is for java. Replace int for int32_t –
Unkennel
This can not be relied on to work. Right-shifting a signed integer that's negative can either be zero-filled or sign-extended: "If E1 has a signed type and a negative value, the resulting value is implementation-defined." –
Huge
Try the following:
int abs(int n)
{
return sqrt(n*n);
}
sqrt is pretty costly, in addition it accepts double as parameter, so you have 2 conversions (int to double) and (double to int) –
Bivens
This actually almost lead me to a solution where I needed an expression where functions were not supported (calculated field in an ADO.Net DataColumn expression). It can also be written as (n*n)^(1/2). Unfortunately power (^) is also not supported... –
Ailssa
beside being slow, it'll overflow for larger values of
n, and it doesn't work correctly if the floating-point type doesn't contain twice the precision of int –
Coleville Didn't saw this one. For two's complement representation and 32 bit int
( n >> 31 | 1 ) * n
Great solution! This is a better version- ( n >> sizeof(int)*8-1 | 1 ) * n –
Punkie
@MinhasKamal No. This will fail if
n is negative and the system zero-fills when using the >> operator because n >> 31 bits will be 0....0001, causing the "absolute value" to be a negative number. Per C11 6.5.7p5: "If E1 has a signed type and a negative value, the resulting value is implementation-defined." –
Huge @AndrewHenle yeah this is assuming Arithmetic Shift implementation. –
Clarkclarke
No branches or multiplication:
int abs(int n) {
int mask = n >> 31;
return (mask & -n) | (~mask & n);
}
Here is another approach without abs(), if nor any logical/conditional expression:
assume int is 32-bit integer here. The idea is quite simple: (1 - 2 * sign_bit) will convert sign_bit = 1 / 0 to -1 / 1.
unsigned int abs_by_pure_math( int a ) {
return (1 - (((a >> 31) & 0x1) << 1)) * a;
}
Bit shifting signed integers in the way you consider is undefined behaviour and thus not an option. Instead, you can do this:
int abs(int n) { return n > 0 ? n : -n; }
No if statements, just a conditional expression.
While technically this answers the question, a ternary is really just a compact if statement, so its probably not what OP is looking for. –
Delozier
It uses a different syntax, and returns a value (unlike if), but once compiled still contains a branch, which is generally what people are talking about when they want to avoid
if statements. This will probably compile to the same machine code as the obvious if implementation. –
Delozier @AaronDufour: But the standard does not define the ternary operator to be an if-statement. Actually, unlike if-statements, the ternary operator has a value, and it can yield an lvalue (e.g.
x?y:z = 0;). What it compiles to is irrelevant. switch-statements may compile to lookup-tables, if-statements may completely dissapear, only the visible behavaiour of the program shall not change (with the exception of RVO) –
Beaird @phresnel But for such a contrived question, the only reasonable interpretation is trying to avoid conditional constructs, which includes both the ternary and
if statements. Otherwise the question is trivial, as shown in this answer. This is what I was trying to convey with my talk of compiling to branches. –
Delozier @AaronDufour: The title says
without using abs function nor if statement which to me sounds like it is if statements and the abs-family of functions which are to be avoided ... –
Beaird @phresnel “the ternary operator [...] can yield an lvalue” No. You are thinking of GCC. You cannot do this in standard C. gcc.gnu.org/onlinedocs/gcc-3.4.6/gcc/Lvalues.html –
Peoples
@Complicatedseebio: Good catch, my mistake. (Sidenote: In C++, it can) –
Beaird
@Complicatedseebio: Btw, what's with your account? Are you all the same person? –
Beaird
@phresnel You are right, I guess the admins must have fixed the issue by now and I should update my information. –
Peoples
@AaronDufour But for such a contrived question, the only reasonable interpretation... As far as I'm concerned, when it comes to contrived questions, just as in love and war, all's fair. Given that this question has 26 answers, it's perfectly reasonable for one of them to use
?:. Anyone reading can decide for themselves which answers validly conform to the perverse constraint. –
Undertake If your language allows bool to int cast (C/C++ like):
float absB(float n) {
return n - n * 2.0f * ( n < 0.0f );
}
There are multiple reasons left shifting the sign bit out and right shifting back in place (v << 1 >> 1):
- left shifting a signed type with a negative value has undefined behavior so it should not be used at all.
- casting the value to
unsignedwould have the desired effect:(unsigned)v << 1 >> 1does get rid of the sign bit, if there are no padding bits, but the resulting value is the absolute value ofvonly on systems with sign+magnitude representation, which are vanishingly rare nowadays. On the ubiquitous 2's complement architecture, the resulting value for negativevisINT_MAX+1-v
Hasturkun's solution unfortunately has implementation defined behavior.
Here is a variation that is fully defined for systems with 2's complement representation for signed values:
int v; // we want to find the absolute value of v
unsigned int r; // the result goes here
unsigned int mask = -((unsigned int)v >> (sizeof(unsigned int) * CHAR_BIT - 1));
r = ((unsigned int)v + mask) ^ mask;
Yet I is much better to let modern compilers determine the best code do generate for this:
unsigned r = v;
if (v < 0)
r = -r;
It is highly likely they generate branchless, hence efficient, code today.
What about this one:
#include <climits>
long abs (int n) { // we use long to avoid issues with INT MIN value as there is no positive equivalents.
const long ret[2] = {n, -n};
return ret[n >> (sizeof(int) * CHAR_BIT - 1)]; // we use the most significant bit to get the right index.
}
Use division (and wider math) to form an "if". Perhaps not efficient, yet branchless.
int abs_via_division(int v) {
// is_neg:0 when v >= 0
// 1 when v < 0
int is_neg = (int) ((4LL * v) / (4LL * v + 1));
return v * (1 - is_neg*2);
}
Works for all int when long long wider than int, aside from the usual trouble with |INT_MIN|.
Bit-shifting is (in principle) implementation-defined, but conversion to a wider signed-integer-type will extend the sign-bit. If you interpret the hi-bits as an integer, they will be 0 or -1, which will let you invert the 2's complement:
int32_t abs(int32_t in)
{
int64_t in64 = (int64_t)in;
int32_t* ptr = (int32_t*)&in64;
int32_t hi = *(++ptr); // assumes little-endian
int32_t out = (in ^ hi) - hi;
return out;
}
The above mechanism is the result of compiling the naive implementation with optimization turned on:
mov eax,ecx
cdq
xor eax,edx
sub eax,edx
In C++20, you can use std::bit_cast from header <bit> to cast the integer into an unsigned integer, unset the sign bit and cast back into the original type. In code it looks like this:
#include <bit>
// yes, you can use this at compile time
constexpr std::int32_t custom_abs(std::int32_t x)
{
return std::bit_cast<std::int32_t>(std::bit_cast<std::uint32_t>(x) & ~(1U << 31));
}
The compiler will optimize the casts away with optimizations enabled.
If you cannot use C++20, you can always use memcpy with the same steps, as following:
#include <cstring>
// no constexpr :(
inline std::int32_t memcpy_abs(std::int32_t x)
{
std::uint32_t u32;
std::memcpy(&u32, &x, sizeof(u32));
u32 &= ~(1U << 31);
std::memcpy(&x, &u32, sizeof(u32));
return x;
}
Finally, if you cannot use C++ and have beef with memcpy, in C you can access the non-active member of a union to make the type casting like this:
#include <stdint.h>
inline int32_t union_abs(int32_t x)
{
union { uint32_t u32; int32_t i32; } num = {.i32 = x};
return num.u32 & ~(1U << 31);
}
All these approaches codegen the same as std::fabsf with optimizations, which you can check from here.
Use the ternary operator:
y = condition ? value_if_true : value_if_false;
how about that:
value = value > 0 ? value: ~value + 1
its based on the fact that negative numbers are stored as 2's complement to there positive equivalent, and that one can build the 2's complement by first building the 1's complement and adding 1, so
5 -> 0000 0101b
-5 -> (1111 1010b) + 1 -> 1111 1011b
what I did was basically to reverse this, so
-5 -> 1111 1011b
5 -> (0000 0100b) + 1 -> 0000 0101b
I know it's a bit late but just had the same issue and landed here, hope this helps.
A simple one that avoids bitshifting:
value -= (value < 0) * value * 2;
- If
valueis positive,value < 0evaluates to0so the multiplication result is0. Nothing is subtracted fromvalue. - If
valueis0, the multiplication result is also0. - If
valueis negative,value < 0istrue, which evaluates as1, which is then multiplied byvalue * 2. Essencially you're subtracting the double of value from value, netting you its corresponding positive.
© 2022 - 2024 — McMap. All rights reserved.
((n < 0) ? (-n) : (n))or((n < 0) ? (n * -1) : (n))is wrong? – Deepsixstd::abs()? – Kordula