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

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 `if`

statement: `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 `if`

statement `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 = 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
```

Taking `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
```

Following the `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.