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.

Bitwise Operators

Operator Description
& Bitwise AND
| Bitwise OR
^ XOR
>> Right Shift
<< Left Shift
~ 1’s Complement

 

Basic Bitwise Operations

A B A & B A | B A ^ B ~ (A)
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 0
1 1 1 1 0 0


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.

In this example – 00010111 = 23 00101110 = 46 It implies that 23<<1 = 46

Let’s look at some more examples

    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.

In this example –
00010111 = 23
00101110 = 11
It implies that 23>>1 = 11

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
    answer=N|p
    return answer
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
    answer=N &amp; ~p
    return answer
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
This article is contributed by Md Taslim Ansari

Repeated number in array

In last post : Find missing number in array, we learned how to find a missing number in array of integers with values in a given range. Today, we will learn how find a repeated number in array of integers from 1 to N. Note that here also, numbers are not sorted but are confined to a range. So, if size of array is N, then range of numbers is from 1 to N-1 as one number is repeated. For example:

A = [1,2,3,3,4,5]. Repeated number is 3
Size of array : 6 Range : 1 to 5

Algorithm

As we have learned while solving the missing number problem earlier, the XOR principle can be applied here too. Why? Because in this case repeated numbers will be XORed with itself three times. Properties of XOR to understand the method and how we use them.

A XOR A = 0
0 XOR A = A

Now, when a number XORed with itself, the result is zero, and when zero is XORed with a number, the result is the number itself. Extending this, if we XORed the same number thrice or without losing generality, an odd number of times, the result will be the number itself.

Using an odd number of times XOR principle, algorithm to find repeating a number in an array.

1. XOR all actual numbers in the array. Call it aXOR.
2. XOR all numbers in range 1 to N-1. Call it eXOR
3. XOR aXOR with eXOR. Result will be repeated number.

This is because all numbers except the repeated number will be XORed even number of times, and cancel each other. The repeated number will be XORed thrice, the final result will be the repeated number. Let’s take the above example and see if it works

A = [1,2,2,3,4]

aXOR = 001 XOR 010 = 011 XOR 010 = 001 XOR 011 = 010 XOR 100 = 110
eXOR = 001 XOR 010 = 011 XOR 011 = 000 XOR 100 = 100

ActualXOR XOR expectedXOR = 110 XOR 100 = 010

Implementation

public int repeatedNumber(int[] nums) {
 
    int n =  nums.length;
     
    int nXOR = 0;
    for(int i=0; i<=n; i++){
        nXOR ^= i;
    }
     
    int aXOR = 0;
    for(int i=0; i<n; i++){
        aXOR ^= nums[i];
    }
     
    return aXOR ^ nXOR;
}

The time complexity of the XOR method to find a repeated number in an array is O(n).

Please share your thoughts through comments, if you see something is missing or wrong or not explained properly.

Missing number in array

Given an array of N integers, ranging from 1 to N+1, find the missing number in that array. It is easy to see that with N slots and N+1 integers, there must be a missing number in the array.
This problem is very similar to another problem: find repeated number in an array
For example,

Input:
A = [1,2,5,4,6] N = 5 range 1 to 6. 
Output: 
3.

Input:
A = [1,5,3,4,7,8,9,2] N = 8 range 1 to 9. 
Output:
6

Approaches to find absent number

Using hash
Create a hash with the size equal to N+1. Scan through elements of the array and mark as true in the hash. Go through the hash and find a number that is still set to false. That number will be the missing number in the array.
The complexity of this method is O(n) with additional O(n) space complexity.

Using mathmatics
We know that the sum of N consecutive numbers is N*(N+1)/2. If a number is missing, the sum of all numbers will not be equal to N*(N+1)/2. The missing number will be the difference between the expected sum and the actual sum.

Our missing number should be = (N+2) * (N+1) /2 – Actual sum; N+1 because the range of numbers is from 1 to N+1
Complexity is O(n). However, there is a catch: there may be an overflow risk if N is big enough.

Using XOR
There is a beautiful property of XOR, that is: if we XOR a number with itself, the result will be zero. How can this property help us to find the missing number? In the problem, there are two sets of numbers: the first one is the range 1 to N+1, and others which are actually present in the array. These two sets differ by only one number and that is our missing number. Now if we XOR first set of numbers with the second set of numbers, all except the absent number will cancel each other. The final result will be the output of our problem.

Algorithm using XOR

1. Scan through the entire array and XOR all elements. Call it aXOR
2. Now XOR all numbers for 1 to N+1. Call it eXOR
3. Now XOR aXOR and eXOR, the result is the missing number

Let’s take an example and see if this works

A = [1,3,4,5] Here N = 4, Range is 1 to 5.

XORing bit representations of actual numbers
001 XOR 011 = 010 XOR 100 = 110 XOR 101 = 011 (aXOR)

XORing bit representation of expected numbers
001 XOR 010 = 011 XOR 011 = 000 XOR 100 = 100 XOR 101 = 001 (eXOR)

Now XOR actualXOR and expectedXOR;
011 XOR 001 = 010 = 2 is our answer.

Implementation

    public int missingNumber(int[] nums) {
    
        int n =  nums.length;
        
        int nXOR = 0;
        for(int i=0; i<=n; i++){
            nXOR ^= i;
        }
        
        int aXOR = 0;
        for(int i=0; i<n; i++){
            aXOR ^= nums[i];
        }
        
        return aXOR ^ nXOR;
    }

The complexity of the XOR method is O(n) with no additional space complexity.

If you want to contribute to this blog in any way, please reach out to us: Contact. Also, please share if you find something wrong or missing. We would love to hear what you have to say.