Bit Manipulations – Part 1

When it comes to problem-solving during interview preparations or competitive programming there are many instances where we encounter errors like Time Limit Exceeds (TLE). These errors are mostly due to the fact that our solution does not run in stipulated time limit and it crosses the allotted time limit.

To counter this problem, there are many algorithms available and Bit Manipulation is one of them. Bit manipulations are fast and can be used in optimizing time complexity. You would be thinking what is the use of Bit manipulation if we have other algorithms/ways to solve the problems.

Consider a problem- XOR of Sum of all possible pairs of an array

A naive approach is to run two loops consider each pair and then find the sum of each pair and then calculate XOR of all the sums.

In this case, time complexity- O(n2)

An optimized approach is based on the XOR operation. We know that the XOR of the two same numbers is Zero. So pairs like (a,b), (b, a), (a, c), (c, a) will have the same sum and hence their XOR will be Zero. so we need to consider pairs like (a, a), (b, b), (c, c) and hence XOR of the sum of pairs will be XOR of all elements of the array multiplied by 2.

In this case, time complexity is O(n)

We will discuss the above problem in detail in upcoming article.

Bit manipulation in detail

Now let us understand bit manipulations in detail.

Bit Manipulations is nothing but an act of applying logical operations on bits to achieve the desired result.

Since implementing bit manipulation involves logical operations, so let’s start our discussion with logical operators and their respective operations.

Logical Operations

Logical operations are any set of operations which involves manipulating bits using some operators and such operator are known as Logical Bitwise Operators.

So far we have basic understanding of bit-wise operators and respective operations. Now we will be diving deep into bit manipulation concepts.

Important bit manipulation tricks for problem solving

1. Left Shift

In left shift each bit is being shifted by k bit(s) towards left and consequently most significant bit (MSB) is discarded.

1. 2 << 1 = 4
2. 2 << 2 = 8
3. 2 << 3 = 16

Did you observed some pattern in above examples?

Yes, here’s a trick. Observe carefully and you will get that 2 << 1 = 2 * power(2, 1) , 2 << 2 = 2 * power(2, 2) and so on.

If there is a number N and we have to perform left shift by i bits, then N = N * power(2, i)

2. Right Shift

In right shift each bit is being shifted by k bit(s) towards right and consequently least significant bit (LSB) is discarded.

Let’s have a look at some more examples

1. 8>> 1 = 4
2. 8 >> 2 = 2
3. 8 >> 3 = 1

Did you observed some pattern in above examples?

Yes, here’s a trick. Observe carefully and you will get that 8 >> 1 = 2 / (power(2, 1)) , 8 >> 2 = 8 / (power(2, 2)) and so on.

Conclusion : If there is a number N and we have to perform right shift by i bits, then N = N / ( power(2, i)

3. Swapping two numbers

Suppose a=2 and b=3, then we need a=3 and b=2, so swapping will be done as-

def swapping(a,b):
a=a^b
b=a^b
a=a^b
print(a,b)
def main():
a=int(input())
b=int(input())
swapping(a,b)
if __name__=="__main__":
main()

4. To check whether number is even or ODD

Let’s observe some even and odd numbers and their respective binary representations-

2 = 0010
3 = 0011
4 = 1000
9 = 1001
10 = 1010

Upon carefully observing the binary representations of above numbers you will find that if a number is even then LSB is 0 else LSB is 1.

Now observe one more thing-

2 & 1 => 0010 & 0011 = 0000
3 & 1 => 0011 & 0001 = 0001
9 & 1 => 1001 & 0001 = 0001
4 & 1 => 0100 & 0001 = 0000
Bitwise AND of N with 1 is 0 for even numbers and is 1 for odd numbers.
def oddeven(N):
if(N&amp;1==0):
print("EVEN")
else:
print("ODD")
def main():
N=int(input())
oddeven(N)
if __name__=="__main__":
main()

5. How to set a bit in a number N

If we want to set a bit at kth position then-

• Left shift 1 k times (let p=1<<k)
• Find bitwise OR of N with p i.e. answer=N|p

Consider and example-

N=8 (1000) suppose we want to set 2nd bit means k=2 since 1 = 0001 (in binary) Therefore, p=1<<k

p=0100 (in binary)

Hence, N | p = 1000 | 0100 = 1100 (equivalent to 35 in decimal)

def setKthBit(N,k):
p=1&lt;&lt;k
def main():
N,k=map(int,input().split())
print(setKthBit(N,k))
if __name__=="__main__":
main()

6. How to unset a bit in a number N

If we want to unset a bit at kth position then-

• Left shift 1 k times (Let p=1<<k)
• Negate p => ~p
• Find bitwise AND of N with ~p , it will unset the required bit.

Suppose N=51 and k=4 N = 110011 then, p = 1 << 4 = 010000 So, ~p = 101111

Therefore N & ~p = 100011 (equivalent to 35 in decimal)

def setKthBit(N,k):
p=1&lt;&lt;k
def main():
N,k=map(int,input().split())
print(setKthBit(N,k))
if __name__=="__main__":
main()

So far we have learned some basic but useful concepts in bit manipulation.

In the Second Part of Bit Manipulation series I will be covering some important concepts with tips and tricks like-
• Check if kth bit is set.
• Count Number of set bits.
• Toggle a bit at kth position.
• Check if a number is divisible by 3
• Swap all odd and even bits
• Binary to gray code conversion

Single number in an array

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Example 1:
Input: [2,2,1,3,4,3,5,4,5,]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4

Approach 1

You will be thinking it’s a very simple problem. What we all need to do is to take count of each distinct number and that number having count 1 will be our answer. We can achieve it by using a dictionary.

Time Complexity – 0(N)
Space Complexity – 0(N)

What if your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? It means you have to solve the problem in O(N) time complexity and constant space that means space complexity must be O(1).

Think of an approach before going into the post.

Let me tell you, have you ever heard of Bit Manipulation?

‘’ As the name suggests, it is a process of performing logical operations on bits to achieve the desired result.’’

To understand the bit manipulation let’s first have a look at Logical Bitwise Operators.

1. AND (&)
2. OR ( | )
3. XOR (^)
4. Left Shift (<<)
5. Right Shift (>>)

In our particular problem, we will implement Bitwise XOR to get the desired result.

Properties of Bitwise XOR (^)–

1. 0 ^ 0 = 0
2. 0 ^ 1 = 1
3. 1 ^ 0 = 1
4. 1 ^ 1 = 0

If we observe the above operations we find that XOR of the same bits results in 0 and XOR of two different bit results into 1.

Now, Let’s have a look on some other examples –

• 1 ^ 1 ^ 1 ^ 1 = 0
• 2 ^ 2 = 0
• 1 ^ 1 ^ 2 = 2
• 2 ^ 3 ^ 4 ^ 3 ^ 2 = 4 (XOR operation is commutative and associative)

Now pause and observe the above examples very carefully.

Approach 2

So, If you observe carefully you will find that XOR of all those numbers appearing twice are being cancelled out and we are left with the number that appears only once. It clearly means if there are N numbers out of which N-1 numbers appears twice (or even number of times) and one number appear only once, then XOR of all numbers collectively results into that number which appears only once (See Examples 6, 7, 8) and as a result we will get our desired number.

As in example 8, 2 appears twice (so 2 ^ 2 = 0) and 3 appears twice (3 ^ 3 = 0) and 4 appears only once so as a consequence we will get 4 (0 ^ 0 ^ 4 = 4)

So in order to solve our particular problem we need to find XOR of all the numbers of array and and resultant XOR will be our answer.

Python Solution –

def singleNumber(Arr, n):
ans=0
for i in range(N):
ans^=Arr[i]
return ans

Steps-

1. Iterate over all elements of array
2. Find the XOR of all elements of array and store it into a variable ans.
3. Return ans.

Complexities –

1. Time Complexity – O(n)
2. Space Complexity- O(1)