Get this book > Problems on Array: For Interviews and Competitive Programming
In this article, we have explained two approaches to find the Absolute value of Integer using Bitwise Operations namely Right shift, OR and XOR operations.
Contents
 Introduction
 Integers in binary
 Shifting bits
 XOR in binary
 Result
 A second approach
Introduction
If we define what's Absolute value, then it says that "The distance of some number from the zero is an Absolute Value".
Which means if there is some given number +/ N then the Absolute Value of this number should be N.
One way to find out the Absolute value of a number will be to check if the given value is negative
or positive
and if it's positive
, then return n
and if it's negative
, then return n  2*n
.
Code for the above Example:
fn abs(n: i8) > i8 {
if n > 0 {
n
} else {
(n  n)  n // Using this because,
// Above mentioned can overflow.
}
}
But, you see, this requires an ifelse
statement, and if we used binary operations
to find Absolute Value, then one can avoid using ifelse
statements.
Note: we will be considering only 8bit numbers here, but you can apply this method to others as well.
Just usesize_of(n) * 8
to find out the number of bits for the data type you're using.
Integers in binary
I think if you're scrolling through this page, then you should already be familiar with how we represent integers in binary and how we know if a number is positive
or negative
but, to make sure that we're on the same page, we'll look at it once again.
There are two kinds of numbers one is signed
and unsigned
.
unsigned
 The range for
unsigned
numbers goes simply from0 to 255
and in binary0000_0000
to1111_1111
.
signed

But the range for
signed
numbers goesfrom 128 to 127
, and in binary, there are two ranges to make note of0 to 127
>0000_0000
to0111_1111
1 to 128
>1111_1111
to1000_0000
Yep!! It counts backward.
And Of course, we will be using only signed
integers here.
Shifting Bits
The rule is to have a 1 bit (the most left one) in signed integers as a sign bit, when it's 0
then, consider the number to be positive
and negative
if the sign bit is 1
.
Now, shifting bits to the left will do the same things for both positive
and negative
integers.
But when we right shift the bits then, a positive
integer will have no issue and, there will be a 0
in the sign bit before and even after the shift.
But, when we right shift a negative
integer then, it is necessary that we make sure to preserve the sign bit. So, there will be 1
present in the sign bit.
For Example:
Positive Number
Let's consider a number n = 10
and, now if we right shift it, then it should look something like the given diagram:
Negative Number
And for n = 10
, it will look something like this:
And if we think about this, then this thing gives us a really good trick to use, which will let us know if the given value of a number is negative
or positive
. How?
Well, if we right shift
a positive
integer then the bit that gets added to the left is 0
, and for negative
integer 1
.
And if we keep doing the right shift then every bit in any negative
number should become 1
and every bit in any positive
number should become 0
.
Therefore:
negative number >> 7 should give
1 (1111_1111)
.
positive number >> 7 should give0 (0000_0000)
.
XOR in Binary
Here we are going to learn a trick regarding XOR operation
, which is a necessary part to make a decision when we will be calculating the Absolute Value.
So, doing XOR operation
is simple, only know that:
 if the given two bits are different then, the output will be
1
.  if the given two bits are same then, the output will be
0
.
Now, let's try something where we consider some bits,
a
which, will be fixed to 1
And
b
which, can be 1 or 0.
So, if we takeXOR
for both 1 and 0 ofb
with a fixed bita
:
Then,
0 ^ 1
=1
1 ^ 1
=0
So, we can conclude that for b, if
XOR
'ed with a, it should act asnegation
that is,bit ^ 1
=!bit
And if we did same thing but, now a
is fixed to 0
, we see that:
0 ^ 0
=0
1 ^ 0
=1
then this tells us that,
bit ^ 0
=bit
And now, we can conclude that, if we take any number and XOR
'ed it with a number where all bits are 1
, then the result will be inverted version of the given number.
Example:
1 ^ 0b1111_1111
equals to2
Remember, we're considering i8
Finding Absolute Value
Well, time to apply it all, to calculate Absolute Value
the solution we have here can be divided in three steps:
 Check if the number is negative or positive.
For this, we canright shift
the bits for the ( total number bits  1 ). And this is ourmask
.
mask = n >> size_of(n) * 8  1
 Add
one
to the number if negative and Addzero
if positive.
Adding the mask
will do this automatically.
n = n + mask
This step balances the number by filling the gap on the positive side of anyunsigned
number.
 Now, invert the whole number using
XOR
if negative.
Here also usingmask
should do this automatically because mask can choose to invert if the number is negative.
Example Code:
fn abs(n: i8) > i8 {
// 1st: right shift (sign check)
let mask = n >> 7;
// 2nd: Add the mask, `+` and `` balance.
let n = n + mask;
// 3rd: Now, invert and return.
n ^ mask
}
Time and Space Complexity
Assume we have to find the absolute value of a Nbit number
Time Complexity: O(N)
as the bitwise operations right shift and XOR along with add operation take O(N) time.
Space Complexity: O(N)
as we have to maintain the mask which is the same size of the input value.
Another Approach
When I was looking at 'the above' algorithm, I thought I would try to find some other way of doing this, So, after some tries, I figured one out, and when I told @aditya about this, he asked me to add it here.
So, here we are.
The idea for this approach is simple.
Whenever we multiply two different numbers then we make sure the signs are right and we have some rules for that. And one of them is, if we multiply two negative
numbers then the result of this product should be a positive
number.
And our goal is to change the number to positive
if it's negative
and return the same number if it's positive
.
One thing we already learned is that if we use Right Shift we get
1
fornegative
numbers and,0
forpositive
numbers.
So, if we use n >> 7
and multiply it with n
, we can get a positive
number for a given negative
number.
Something like if n = 12
:
then,
(n >> 7) * n will produce 12 as a result.
But you see if n = 12
:
then,
(n >> 7) * n will produce 0 as a result.
Yep! A problem!
So, now we need to find a way which will change our mask to 1
, when n >> 7
is 0
and do nothing when it's 1
.
Let's look at the binary representation of 1
, 0
and 1
.
1 >
1111_1111
0 >0000_0000
1 >0000_0001
Here, we can see that we have to change the Right
most bit to 1
if it's 0
or else all bits should remain 1
.
And OR (  )
is the operator that we can use for this task.
OR operator
So, what OR operator
does is that, it returns 1
if any of the given input is 1
, and it returns 0
only if bits of both sides are 0
.
Now, if we try OR
on our mascots 1
and 0
, with 1
, we get the following result:
1  1 >
1111_1111
0  1 >0000_0001
Their we go we got it.
Sum Up
Now, if we sum up all that, then again we have 3 Steps to do this:
 Check, if the given number
n
isnegative
orpositive
.
if_neg = n >> size_of(n) * 8  1
 Create
mask
. For that take theOR
ofif_neg
and1 (0000_0001)
.
mask = if_neg  1
 Now take product of the
mask
and the Numbern
to get theAbsolute Value
.
mask * n
Code Example
fn abs(n: i8) > i8 {
let size = std::mem::size_of_val(n) * 8;
// 1st step: do the right_shift
let if_neg = n >> (size  1);
// 2nd step: change to 1 if 0 else remain 1
let mask = if_neg  1_i8;
// 3rd step: multiply and return
mask * n
}
Time and Space Complexity
Assume we have to find the absolute value of a Nbit number
 Time Complexity: O(N logN)
as the bitwise operations right shift and OR take O(N) time
but the arithmetic operation Multiplication has a theoretical limit of O(N logN). In practice, the Time Complexity of Multiplication is O(N^{2}).
In practice, the Time Complexity of this approach is O(N^{2}) while the theoretical limit is O(N logN).
 Space Complexity: O(N)
as we have to maintain the mask which is the same size of the input value.
With this article at OpenGenus, you must have the complete idea of Absolute value of Integer using Bitwise Operations.