Get this book -> Problems on Array: For Interviews and Competitive Programming

Hello readers, we are gonna take a look at how can we subtract two numbers without using arithmetic operation. We will only use **bitwise operations** to perform subtraction.

Table of content:

- What are bitwise operations?
- Subtraction using bitwise operations
- Subtraction Logic
- Implementation of Logic
- Complexity Analysis

We will dive into bitwise subtraction now.

# What are bitwise operations?

Similar to arithmetic operators like `+`

, `-`

, `*`

, `/`

in decimal number system, we have bitwise operators like `AND (&)`

, `OR (|)`

, `XOR (^)`

, etc to manipulate data stored in form of bits.

Bitwise operators are used to perform bit-manipulations on the data stored in computers memory.

**Some famous bitwise operators are:**

- AND
`&`

- OR
`|`

- XOR
`^`

- Left-shift
`<<`

- Right-shift
`>>`

- Bitwise NOT
`~`

# Subtraction using bitwise operations:

To understand this, we have to get to binary level of data representation in computer's memory.

I am gonna explain it using both, decimal and binary to make it as clear as possible.

Let's say we have two numbers `x`

and `y`

with their respective values as:

```
int x = 5, y = 3;
```

and we have to find out the difference between these two numbers without using any arithmetic operator like `-`

(minus).

The operators that we are gonna utilize to achieve this task are:

- XOR
- Bitwise NOT
- Left-shift

### XOR

A XOR is a **binary operator** which will return `1`

if bits are different bits and `0`

for the same bits:

**XOR of 5 and 3:**

```
5 3 | XOR
--- --- ---
1 1 | 0 --> Same bits results in 0
0 1 | 1 --> Different bits results in 1
1 0 | 1
0 0 | 0
```

### Bitwise NOT (~)

Bitwise NOT is an **unary operator** and very easy to understand, it simply `flips`

the bits, it changes `0`

to `1`

and `1`

to `0`

.

**~5 will be:**

```
5 | ~5
--- ---
1 | 0 --> Flips the bit
0 | 1
1 | 0
0 | 1
```

# Subtraction Logic

For subtraction of binary numbers, rule are similar to decimal. When a larger digit is to be subtracted from a smaller digit, we take a `borrow`

from the next column to the left.

Lets visualize the numbers in binary form:

```
X Y Diff Borrow
1 1 0 0
0 1 1 1
1 0 1 0
0 0 0 0
```

If we take a look at bitwise difference, one can easily deduct that result of bitwise subtraction above can is equivalent to as if we perform `xor`

operation on these number (x=5, y=3), and that will also leave us with the difference.

**x^y:**

```
x y | XOR
--- --- ---
1 1 | 0
0 1 | 1 (with a borrow)
1 0 | 1
0 0 | 0
```

Now, all that is left is the `borrow`

bit, if we perform a `bitwise-not`

on `x`

and then `AND`

it with `y`

we will be left with the `borrow`

bits:

```
int x=5, y=3;
~x y | AND
--- --- --------
0 1 | 0
1 1 | 1
0 0 | 0
1 0 | 0
```

To summarize the above operation, subtraction will be equal to:

```
use (x^y) to get the difference
use ((~x)&y) to get carry bit
```

# Implementation of Logic

When it comes to implementation, we can implement this in two ways:

- Iterative
- Recursive

We'll take a look at both of them:

### 1. Iterative Algorithm

```
for two given integers x, y:
1. get the borrow/carry bit as it contains unset bits of x and
common bits of y
int borrow = (~x)&y;
2. get the difference using XOR and assign it to x:
x = x^y
3.Asssign the borrow to y by left shifting it by 1 so when we XOR it
with x it gives the required sum.
y = borrow << 1;
4. Repeat the above steps until y becomes 0, in that case our carry will become 0.
5. In the end, you will end up having x set to the difference between x and y.
In that case, simply return x
return x;
```

### Example C++ code

```
#include <iostream>
using namespace std;
int subtractUsingBitwise(int x, int y)
{
while (y != 0) // Iterate until carry becomes 0.
{
// step 1: get the borrow bit
int borrow = (~x) & y;
// step 2: get the difference using XOR
x = x ^ y;
// step 3: left shift borrow by 1
y = borrow << 1;
}
return x;
}
int main()
{
int x = 5, y = 3;
int answer = subtractUsingBitwise(x, y);
cout << "x - y is : "<<answer<<endl;
return 0;
}
```

### 2. Recursive Algorithm

```
for two given integers x, y:
1. Check if y is equal to 0, if so then return x (The base condition of recusrrsion):
if (y==0) then
return x;
2. Else, assign x to the difference and y to the carry bit(left shifted by 1)
in each recursive call:
x = x^y;
y = ((~x) & y) << 1;
call function recursively by passing x and y
```

### Example C++ code

```
#include <iostream>
using namespace std;
int subtractUsingBitwise(int x, int y)
{
if (y == 0) // step 1: base condition
return x;
// step 2: perform bitwise manipulation and assign x and y
x = x^y;
y = ((~x) & y) << 1;
// step 3: call function recursively
return subtractUsingBitwise(x, y);
}
int main()
{
int x = 5,y = 3;
cout << "x - y is "<< subtract(x, y);
return 0;
}
```

# Complexity Analysis

**Time complexity** of bitwise subtraction would be `O(n)`

where `n`

is the number of bits in a number.

**Space complexity** will remain constant, `O(1)`

as we are not using any extra space in each step.

Bit manipulation is used in many many areas of computer science to improve the program's efficiency. Having a deep understanding of bitwise operations is gonna help you in develop more efficient solutions.

This concludes this article at OpenGenus for using bitwise operators to manipulate data in order to get perform subtraction.

Hope you find it helpful!