Many programmers are accustomed to seeing mathematical operations performed using arithmetic operators. However, there are other ways to perform the same operations without the use of arithmetic operators.
Bitwise operators happen to be much simpler operators, making them quite a bit faster than arithmetic operators. Bitwise operators are most often used when encoding and decoding bits.
They may not always be the best option in every program as they're not necessarily intuitive and unnecessary. However, when handling large pieces of data, the bitwise operator may just resolve your issues. If you have not learned the basics of bitwise operators, it may be helpful to take a look at Bitwise operators in Python before going further.
We will go through the following operations:
- Check if Two Numbers are the Same
- Add Two Numbers
- Multiply Two Numbers
- Swap Two Numbers
- Check Divisibility of a Number
We will go through each of the operations in detail.
Check if Two Numbers are the Same
A quick glance at the example below seems a bit odd. If you have reviewed your bitwise operators, then you may know that
^ can add two numbers together. However, if these two numbers are the same, then the result will be 0. The
checkEquality method below determines the truthiness of each statement by checking whether or not the expression evaluates to zero.
def checkIfSame(x, y): # use XOR operator to determine if the two numbers eval greater than 0 if (x ^ y): print('x and y are not the same numbers.') # move on to else statement if numbers are same and eval to 0 else: print('x and y are the same number.') checkIfSame(12, 5) # output: 'x and y are not the same numbers.' checkIfSame(100, 100) # output: 'x and y are the same number.'
We can see this in action by checking out the bitwise operations a little closer. In the first example, we check if 12 and 5 are the same. The
checkIfSame method takes in the numbers and plugs them into the
12 ^ 5.
1 1 0 0 = 12 in decimal 0 1 0 1 = 5 in decimal ----------- 1 0 0 1 = 9 in decimal
As we find, the result is not zero. Therefore, we can conclude that the numbers are not the same. Let's take a look at the next example between 10 and 10. Of course, we already know that these are the same number, but let's see what this looks like in binary.
1 0 1 1 = 10 in decimal 1 0 1 1 = 10 in decimal --------- 0 0 0 0 = 0 in decimal
Since the XOR statement only evaluates to 1 if there is a 1 and a 0, the result is 0 for each bit.
Add Two Numbers
Adding two numbers is a much easier with arithmetic operators because it involves simply placing a
+ between them. However, addition using the bitwise operators builds foundational knowledge that allows you to better understand how binary numbers work. In the example below, we demonstrate how to add two numbers using a function in python.
def add(x, y): while (y != 0): # the carryOver value will allow the while loop to continue until # we have solved for the sum carryOver = x & y # the XOR statement will accumulate until the loop is broken # then this will be the sum x = x ^ y # double the carryOver and pass it to y y = carryOver << 1 print(y) print(x) add(14, 8) # output: 22
The carryOver value is determined by using the bitwise
& operator. In the example above x = 14 and y = 8, so we must first evaluate
carryOver = 14 & 8.
1 1 1 0 = 14 in decimal 1 0 0 0 = 8 in decimal --------- 1 0 0 0 = 8 in decimal
The AND statement evaluates to 8 in decimal, so carryOver = 8. Next, we must look at the XOR statement, which will determine the sum in the function. This time, we're evaluating
x = 14 ^ 8.
1 1 1 0 = 14 in decimal 1 0 0 0 = 8 in decimal --------- 0 1 1 0 = 5 in decimal
In the XOR problem, we are looking for bits that are different. After comparing bits in 14 and 8, we can see the XOR to be 5 (in decimal), which means
x = 5.
Next, we need to resolve
y and find out if the loop will reiterate or break:
y = carryOver << 1. Recall that we found that
carryOver = 8 and we know that a left shift will double this amount. Let's see what this looks like in bits.
1 0 0 0 = 8 in decimal 1 0 0 0 0 = 16 in decimal
Now that we know
x = 5 and
y = 16, we will iterate over the function again. Starting with the first bitwise operation,
carryOver = 5 & 16, we find that carryOver = 0.
0 1 0 1 = 5 in decimal 1 0 0 0 0 = 16 in decimal ----------- 0 0 0 0 0 = 0 in decimal
Evaluating the XOR operation,
x = 5 ^ 16 reveals
x = 22.
0 1 0 1 = 5 in decimal 1 0 0 0 0 = 16 in decimal ----------- 1 0 1 0 1 = 22 in decimal
Lastly, we must evaluate
y = carryOver << 1. Since the carryOver was determined to equal 0, the result will be
y = 0. This means that the loop will break and 22 will be printed as the answer.
Multiply Two Numbers
The following program takes in two numbers and returns their product, but this doesn't involve the arithmetic multiplication operator like you may expect. Since we are using bitwise operators, we must use a while loop to increment the binary numbers until we reach the correct product of the two inputs. Let's take a look at the example and walk through it together.
def multiply(x, y): # declare variable and initialize to 0 product = 0 # if y <= 0 then the loop will break and print solution while(y > 0): # if y is an odd number, add x to total if (y & 1) # adds x to product arithmetically product = product + x # else, double x and half y x = x << 1 y = y >> 1 print(product) multiply(8, 2) # output: 16
Let's say that we are trying to multiply 8 and 2 as we saw in the example. 8 is x and 2 is y. Since
y > 0 is true, we continue to the
y & 1. To work this out in binary we must compare each bit of 8 and 1, like so:
1 0 0 0 = 8 in decimal 0 0 0 1 = 1 in decimal --------- 0 0 0 0 = 0 in decimal
When using the bitwise
& operation, we see that 8 and 1 have no bits that evaluate to 1. If y had been an odd number, then there would have been a 1 in the right most place, making the
if statement return true.Since it does not, however, we continue to the left and right shift.
We can see from the binary representation of the left and right shift exactly how the while loop will eventually break, as y is halfed each time the loop iterates. For now, let's evaluate what happens when x = 8 and y = 2. First, we come to the left shift,
x = x << 1.
1 0 0 0 = 8 in decimal 1 0 0 0 0 = 16 in decimal
Left shift is the same as doubling, in this case you are shifting the binary digit left by 1, making the new value of x, 16. Next is the right shift, y = y >> 1.
0 0 1 0 = 2 in decimal 0 0 0 1 = 1 in decimal
Right shift is the same as halfing, in this case you are shifting the binary digit right by 1, making the new value of y, 1.
The loop reiterates and this time, the
if statement returns true because y is an odd number (1). At this point, we add x to the variable
product = product + x
The loop continues to the left and right shift, which will change the value of x to 32 and y to 0. This means that the loop will now break and will print
product, which is equal to 16. As we already know, 8 times 2 equals 16, so we have correctly solved the problem using bitwise operations.
Note on the Example
You may notice in this example that the product was added arithmetically. This can be replaced with addition using the bitwise operations that we demonstrated in the previous example, 'Add Two Numbers'.
Swap Two Numbers
If you're familiar with the beginner's overview on bitwise operators and you have become comfortable with XOR, then this is a fairly simple program to swap numbers without using arithmetic operators.
x = 7 y = 4 # 7 XOR 4 evaluates to 3 x = x ^ y # 3 XOR 4 evaluates to 7, so now y has been re-assigned the value 7 y = x ^ y # 3 XOR 7 evaluates to 4, so now x has been re-assigned the value 4 x = x ^ y print(x) # output: 4 print(y) # output: 7
Let's take a closer look at how we were able to evaluate each of those expressions. The first time that we assign
x ^ y to
x, we are evaluating between 7 and 4. This is what is actually going on in binary:
0 1 1 1 = 7 in decimal 0 1 0 0 = 4 in decimal --------- 0 0 1 1 = 3 in decimal
x's new value of 3, we evaluate between 3 and 4:
0 0 1 1 = 3 in decimal 0 1 0 0 = 4 in decimal --------- 0 1 1 1 = 7 in decimal
Now, we evaluate for the last time:
0 0 1 1 = 3 in decimal 0 1 1 1 = 7 in decimal --------- 0 1 0 0 = 4 in decimal
Check Divisibility of a Number
Checking the divisibility of a number can be as simple as evaluating a single
if statement. In the example below we are testing to find whether or not 8 is divisible by 2.
def checkDivisibility (n, m): if (n & ((m << 1) - 1)) == 0: return True return False n = 8 m = 2 if checkDivisibility(n, m): print('It is divisible') else: print("It's not divisible") # output: It is divisible
If n is 2 and we are checking that 8 is divisible by 2, then we first must evaluate the statement
m << 1. This shifts m (or 2) to the left, doubling its value. Then, we must subtract 1 from m and evaluate
n & m or
8 & 2. Let's see the binary representation to find the answer:
0 0 1 0 = 2 in decimal (m) 0 1 0 0 = 4 in decimal
First, we must left shift m by 1. 4 becomes the new value for m, but then we must subtract 1, which gives us m = 3. Now, let's evaluate
n & m.
1 0 0 0 = 8 in decimal (n) 0 0 1 1 = 3 in decimal (m) --------- 0 0 0 0 = 0 in decimal
if statement in the Python code above, this leads us to conclude that 8 is divisible by 2 because
n & m evaluated to 0.
Note About Bitwise Operations
There is much more to learn about bitwise operators and the advanced operations that can be performed with them. While they may not seem very useful in every usecase, they come in handy particularly when dealing with very large data sets, encoding/decoding, as well as when efficiency is important.
Bitwise operators may not be extensively discussed in software development, but it can be incredibly helpful to understand what actually goes on beneath the hood. So, try these examples on your own. If you need more information, check out Bitwise operators in Python to learn more about the basics.