DSA Day-18

Hey Guys!!! Hope you’re doing great….

In this segment of 20 Days DSA series, we’ll be learning few concepts of bit manipulation.

Bit manipulation can come very handy while solving questions like finding the unique elements. Now why is it important? It’s not like we cannot solve the same problem with different approach but bit manipulation reduces the complexities and provide very easy and effective solutions and you’re expected to know these approaches in interviews.

The Bitwise Algorithms are used to perform operations at bit-level or to manipulate bits in different ways.

For example: To check if a number is even or odd. This can be easily done by using Bitwise-AND(&) operator. If the last bit of the operator is set than it is ODD otherwise it is EVEN. Therefore, if num & 1 not equals to zero than num is ODD otherwise it is EVEN.

Bitwise Operators

The operators that works at Bit level are called bitwise operators. In general there are six types of Bitwise Operators as described below:

  • & (bitwise AND) Takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1. Suppose A = 5 and B = 3, therefore A & B = 1.
  • | (bitwise OR) Takes two numbers as operands and does OR on every bit of two numbers. The result of OR is 1 if any of the two bits is 1. Suppose A = 5 and B = 3, therefore A | B = 7.
  • ^ (bitwise XOR) Takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different. Suppose A = 5 and B = 3, therefore A ^ B = 6.
  • << (left shift) Takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift.
  • >> (right shift) Takes two numbers, right shifts the bits of the first operand, the second operand decides the number of places to shift.
  • ~ (bitwise NOT) Takes one number and inverts all bits of it. Suppose A = 5, therefore ~A = 2.

Important Facts about Bitwise Operators:

  • The left shift and right shift operators cannot be used with negative numbers.
  • The bitwise XOR operator is the most useful operator from technical interview perspective. We will see some very useful applications of the XOR operator later in the course.
  • The bitwise operators should not be used in place of logical operators.
  • The left-shift and right-shift operators are equivalent to multiplication and division by 2 respectively.
  • The & operator can be used to quickly check if a number is odd or even. The value of expression (x & 1) would be non-zero only if x is odd, otherwise the value would be zero.

Below are some problems which can be solved very easily using some of the basic concepts of Bit Manipulation. Let’s look at each of these problems and the Bitwise approach of solving them:

Problem 1: Given a number N, the task is to check whether the given number is a power of 2 or not.

Example:

  • Input : N = 4
    Output : Yes
    22 = 4
  • Input : N = 7
    Output : No
  • Input : N = 32
    Output : Yes
    25 = 32
  • Bitwise Solution: If we subtract a number which is a power of 2 1 then all of it’s unset bits after the only set bit become set; and the set bit become unset.
  • For example, consider 4 ( Binary representation: 100) and 16(Binary representation: 10000), we get following after subtracting 1 from them:
  • 3 –> 011
    15 –> 01111
  • You can clearly see that bitwise-AND(&) of 4 and 3 gives zero, similarly 16 and 15 also gives zero.
  • So, if a number N is a power of 2 then bitwise-AND(&) of N and N-1 will be zero. We can say that N is a power of 2 or not based on the value of N&(N-1).

Problem 2: Given a number N, find the most significant set bit in the given number.

Examples:

  • Input : N = 10
    Output : 8
    Binary representation of 10 is 1010
    The most significant bit corresponds
    to decimal number 8.
  • Input : N = 18
    Output : 16
  • Bitwise Solution: The most-significant bit in binary representation of a number is the highest ordered bit, that is it is the bit-position with highest value.
  • One of the solution is first find the bit-position corresponding to the MSB in the given number, this can be done by calculating logarithm base 2 of the given number, i.e., log2(N) gives the position of the MSB in N.
  • Once, we know the position of the MSB, calculate the value corresponding to it by raising 2 by the power of calculated position. That is, value = 2log2(N).

Problem 3: Given a number N, the task is to find the XOR of all numbers from 1 to N.

Examples :

  • Input : N = 6
    Output : 7
    // 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7
  • Input : N = 7
    Output : 0
    // 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0

Solution:

  1. Find the remainder of N by moduling it with 4.
  2. If rem = 0, then xor will be same as N.
  3. If rem = 1, then xor will be 1.
  4. If rem = 2, then xor will be N+1.
  5. If rem = 3 ,then xor will be 0.

How does this work?

  • When we do XOR of numbers, we get 0 as XOR value just before a multiple of 4. This keeps repeating before every multiple of 4.
  • Number Binary-Repr XOR-from-1-to-n
    1 1 [0001]
    2 10 [0011]
    3 11 [0000] ← — — We get a 0
    4 100 [0100] ← — — Equals to n
    5 101 [0001]
    6 110 [0111]
    7 111 [0000] ← — — We get 0
    8 1000 [1000] ← — — Equals to n
    9 1001 [0001]
    10 1010 [1011]
    11 1011 [0000] ← — — We get 0
    12 1100 [1100] ← — — Equals to n

Practice Bit manipulation questions here:

  1. https://www.geeksforgeeks.org/bits-manipulation-important-tactics/
  2. https://www.techiedelight.com/bit-manipulation-interview-questions/
  3. https://www.hackerearth.com/practice/basic-programming/bit-manipulation/basics-of-bit-manipulation/practice-problems/

Upcoming Posts: ECE Placement Insights(Stats, Tips, Off-campus preparation), DSA Day-19

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Arya Goswami

Arya Goswami

177 Followers

Incoming SDE intern at Amazon || Ex- mentee at Amazon ACMS