Get this book -> Problems on Array: For Interviews and Competitive Programming
In this article, we will see how to divide a number using the bitwise operator
>> rather than using the regular division operator
/ or the multiplication operator
* or the modulo operator
Table of content:
- Introduction to Division
- Recap of required bitwise operations
- Division using the left shift operator
- Time and Space complexity
We will explore the algorithm of bitwise algorithm now.
Introduction to Division
So the task here is to divide a given number with another number and return the floor value i.e. just the decimal quotient, but we should be using bitwise operators, not the usual operators like
* / % to divide the number.
let's see it with an example, consider
96 / 7 = 13.71 and its floor value is
So, we need to write a function to do this but by using the bitwise operators.
Recap of required bitwise operations
Before we jump into the problem let's make a quick recall about the bitwise shift operators because that's what we are going to use to solve this problem.
The Bitwise left shift operator
The left shift operator is used to shift the given number to the left by a certain number of bits as shown below.
But what happens when we left shift it? let's take a closer look.
We know that the binary number system is based on powers of 2. Taking a look at the table we can see that the positional weight of each of the following bits is twice the previous bit i.e. its power is increased by 1. As a result, when we push a number towards the left by 1 bit the whole number gets multiplied by 2 power 1. Similarly when a number is pushed to the left by n bits means the number is multiplied by 2 power n.
25 << 1 = 50 (25 * 2 power 1)
25 << 3 = 200 (25 * 2 power 3)
Thus in general if you shift a number to left by n bits, it gets multiplied n times by 2.
The Bitwise right shift operator
The right shift operator shifts the bits towards the right. This means it does the exact opposite of the left shift operator i.e. every time we shift a number towards the right by 1 bit it divides that number by 2.
96 >> 1 = 48
Now since we have got enough idea about the shift operators let's use them to divide a number with another number.
Division using the left shift operator
Let's take two numbers
a = 96 and
b = 7. When we divide
b, we are calculating how many times
b is equal to
a or how many
b's can fit inside
a. In this case, we can fit 13
a / b = 13 (Note: here we calculate only the floor value)
We know that each number can be represented as the sum of powers of 2 and also when we shift a number towards left by n bits it is multiplied by
2 power n. Thus, what we do is shift the divisor
b towards the left and check if it is less than or equal to the dividend
a. If it is less than or equal to the dividend we subtract it from the dividend and add the value of
2 power n to our answer. Doing so, we get our answer as the sum of powers of 2, which will give us the required quotient.
And we repeat this process for the powers of two from 31 to 0. Here we have chosen 31 because in general, the size of an integer data type is 32 bits i.e. it starts from 0 and goes till 31.
Initially, set the answer variable i.e. the quotient to
Check if any one of the numbers is negative and store it in a separate variable.
Make both the numbers positive.
n = 31the most significant bit and loop till
n = 0the least significant bit.
Check if shifting the divisor by
nbits is less than or equal to the dividend
- if so subtract it from the dividend and update the dividend
nto the answer
( Note: Here the dividend is reduced to the reminder each time the condition is true. )
And finally, return the quotient after checking if it should be positive or negative with the result from step 2.
def bit_div(a,b): ans = 0 # the quotient is intialized neg = a < 0 or b < 0 # Checking if one of the numbers is negative a = abs(a) # making sure both the numbers b = abs(b) # are positive for i in range(31,-1,-1): # starting our loop if b << i <= a : # checking if b multiplied by 2**i is <= a a -= b << i # subtracting b << i from a ans += 1 << i # adding 2 power i to the answer # and finally checking if the output should be negative and returning it return ans if neg == 0 else -1 * ans
Now, let's break down this code.
We get the two numbers
b as input and then we initiate a variable
ans to store our final answer i.e. the quotient. Then we check if one of the numbers is negative, but why do we do that? Because, if one of the numbers is negative the quotient is also going to be negative but, if both the numbers are positive or if both are negative the answer is going to be positive.
Then we take the absolute value of both numbers which makes them both positive. Then we begin our loop. We start from
31 the most significant bit because as said before the size of an integer is 32 bits and traverse till
0 the least significant bit. And during each iteration, we check if
b << i i.e. b multiplied by
2 to the power
i is less than or equal to
a the dividend. If it is true we subtract
b << i from the dividend
a and update it and then add
1 << i which is equal to
2 power i to the answer variable
ans. we do this till the loop reaches
And finally, we check if the answer should be negative or positive using the variable
neg's value and return it in its correct form.
Let's see it with an example to get a better understanding,
a = 96 and
b = 7
So the control flow goes like this,
ans = 0
neg = 0i.e. False ( since both 96 or 7 are positive )
- Since both the numbers are positive the absolute value is the same as the number.
- Then the loop starts from
i = 31
i = 4the if statement does not get executed since
7 << iwas greater than
i = 3the value of
7 << iis
56which is less than
96hence it goes inside the if statement.
a = 40(
a = a - b << ii.e.
a = 96 - 56)
ans = 8(
ans += 1 << ii.e.
ans = 0 + 8)
i = 2the value of
7 << iis
28which is less than
a = 12
ans = 12i.e.
8 + 4
i = 1again
7<<i(14) is greater than
12so does not execute.
- And then
a = 5
ans = 13i.e.
12 + 1
- And the loop ends and we are left out with the reminder
aand the quotient
ans. Hence we finally return the quotient
Time and Space complexity
The time complexity of this algorithm is going to be O((log a)^2), where a is the dividend.
This is because each left shift operation takes O(log a) time. In short, the division is based on a multiplication operation and the time complexity of the base multiplication algorithm is the time complexity of division operation.
The space complexity of this algorithm is O(1).
Bitwise operators are one of the important parts of any programming language. They have many applications in cryptography, hash functions, computer graphics, and so on. So having a good flow in bitwise operations is always be an asset to your programming skill.
With this article at OpenGenus, you must have the complete idea of Division using Bitwise Operations. Enjoy.