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:

1. What are bitwise operations?
2. Subtraction using bitwise operations
3. Subtraction Logic
4. Implementation of Logic
5. 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:

1. AND &
2. OR |
3. XOR ^
4. Left-shift <<
5. Right-shift >>
6. 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:

1. XOR
2. Bitwise NOT
3. 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.