Data Structures and Algorithms(DSA) Concept — Bit Manipulation- Part 2

Topic : DSA interview questions on Bit Manipulation.

Q 1. Given a number ‘ N ’ and ‘ i ’, Check if the i’th bit in N is set ( 1 ) or unset ( 0 ).

N = 21  i = 2

N in bits           :  0 1 0 1 0 1
position of bit (i) :  5 4 3 2 1 0

Answer  : True // the bit at postion 2 is set

N = 34 i = 3

N in bits           :  1 0 0 0 1 0
position of bit (i) :  5 4 3 2 1 0

Answer  : False // the bit at postion 3 is unset

Lets approach this problem using bit wise operators.

first lets move the i'th position bit to position 0.
We can do this using >> operator

N>>i // will move the i'th position bit to position 0.

eg
N in bits           :  0 1 0 1 0 1
position of bit (i) :  5 4 3 2 1 0

after N>>i
21>>2

N in bits           :  0 0 0 1 0 1
position of bit (i) :  5 4 3 2 1 0

Next , We can use the & operator to find out if the bit at position 0 is 
set or unset.

(N>>i)&1

N in bits           :  0 0 0 1 0 1
& 1                 :  0 0 0 0 0 1
                     ---------------
                       0 0 0 1 0 1

so we can use the properties of & operation to find out if the bit is set or
unset.

1 & 1 = 1
0 & 1 = 0
0 & 0 = 0

lets see this in code.

boolean checkBit(int N ,int i){

  if((N>>i)&1)==1){
    return true;
  }else{
    return false;
      
  }

}

Q2 . Given a number N , Count the number of set bits(1) in it.

Eg :
 
N = 10 : 1 0 1 0 => 2
N = 26 : 1 1 0 1 0 => 3

int countBit(int N){
  int count=0;
  while(N>0){
    if((N&1)==1){
        count++;
      }

       N=N>>1;
  }

return count;

}

Q3 . Given numbers ‘ N ’ and ‘ i ’ ,Set the i’th bit.

Eg : 

if i'th bit is 0 -> 1
if i'th bit is 1 -> 1

Approach 1 : 

let say N= 45

N    :   1     0     1     1    0    1 
        2^5 +  0  + 2^3 + 2^2 + 0 + 2^0 //The way to calculate the actual number


i=2  : 1     0     1     1    0    1    => 45
      2^5 +  0  + 2^3 + 2^2 + 0 + 2^0


i=1  : 1     0     1     1     1     1.  => 47
      2^5 +  0  + 2^3 + 2^2 + 2^1 + 2^0


i=4  : 1      1     1     1     1     1  => 61
      2^5 +  2^4 + 2^3 + 2^2 + 2^1 + 2^0

We can observe that when we set the i'th bit to 1 for when it is 0.
the 2^i gets added to the number.

N + 2^i 


but 2^i is of TC : 0 (log(i))

Aprroach 2 :

Using 1<<i and OR(|) operator

Eg : 

for i =1
N= N|(i<<i) = 1     0     1     1    0    1
              0     1     0     0    0    0
           -------------------------------------
              0     1     1     1    0    1. => 47

Note: 
 1|1 =   1
 1|0  =  1
  
The time complexity for this approach is TC : O(1)

lets get this implemented in code.

int setBit(int N,int i){

   return N|(i<<i);

}

Q 4. Given N and i , Toggle the i’th bit .

ie 0 => 1 and 1=>0

int toggleBit(int N, int i){

  return N^(1<<i);
}

Hope this was helpful , please do like and follow.

Up next

Data Structures and Algorithms(DSA) Concept — Subsets and Subsequence .