Basics Of Bit Manipulation

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number n.
2. Print the number produced on setting its i-th bit.
3. Print the number produced on unsetting its j-th bit.
4. Print the number produced on toggling its k-th bit.
5. Also, Check if its m-th bit is on or off. Print 'true' if it is on, otherwise print 'false'.
Input Format
A number
Four numbers i,j,k,m.
Output Format
Check the sample ouput and question video.
Question Video
Constraints
1 <= n <= 10^9
1 <= i <= 9
1 <= j <= 9
1 <= k <= 9
1 <= m <= 9
Sample Input
57
3
3
3
3
Sample Output
57
49
49
true


  • Editorial

    The problem can be divided into four parts:

    Part 1: Setting ith Bit (For n = 57 and i = 2)

    Here we have created a mask [ 0 0 0 1 0 0 ] = 4 in which the ith bit here 2nd index bit is set and rest the whole mask has been set to value 0. Now we are performing OR operation to get our result. As we know that that in an OR operation, if either of the operands has a value of 1 then the result is always 1, henceforth we have designed a mask in such a way that the mask can only affect the input number at index i and can set it irrespective of its last value. Thus we get our result.

    Part 2: Unsetting jth Bit (For n = 57 and j = 3)

    Here we have created a mask [ 1 1 0 1 1 1] = 55 by performing two steps. Firstly we created a mask [0 0 1 0 0 0] = 8 by performing j left shift operations on 1. But having this mask can only help us to set a bit but as we want to reset a bit, therefore, we flip the bits to obtain our final mask [ 1 1 0 1 1 1 ] = 55 with which we performed an AND operation with the given input value and get our result. As we know that in AND operation 1 is insignificant and 0 is dominant which means that having 0 on either of the operands ensures the result to be 0. That is why we have a mask wherein we have 0 only at the position where we have to reset the bit and performing the AND operation ensures that the rest bits have the same nature as that of input bits while the jth bit resets.

    Part 3: Toggling jth Bit (For n = 57 and k = 4)

    Here we have created a mask [ 0 1 0 0 0 0 ] = 16 in which the kth bit here 4th index bit is set and the rest of the whole mask has been set to value 0. Now we are performing an XOR operation to get our result. As we know that that in an XOR operation 1 dominates that is that if either of the operands have the value 1 then it is decided that the result will be toggled. Keeping this in mind we have designed a mask in such a way that we have 1 at the index where we wish to toggle the bit hence ensures our result.

    Part 4: Check for set bit (For n = 57 and m = 3)

    Here we have created a mask [ 0 0 1 0 0 0 ] = 8 in which the mth bit here 3rd index bit is set and the rest of the whole mask has been set to value 0. Now we are performing an AND operation to get our result. As we know that that in an AND operation 0 dominates that is that if either of the operands have the value 0 then it is decided that the result will be 0. Keeping this in mind we have designed a mask in such a way that we have 1 at the index where we wish to check whether the bit is set or not. This mask ensures that apart from that bit every other resultant bit will have a 0 value. Now for that particular bit, the result will be the same as the input bit. Thus, if the result is zero then the bit was unset and if the result is non-zero then the bit was set.

    Below is the implementation in Java:

     public static void main(String[] args) {
                                        Scanner scn = new Scanner(System.in);
                                        int n = scn.nextInt();
                                        int i = scn.nextInt();
                                        int j = scn.nextInt();
                                        int k = scn.nextInt();
                                        int m = scn.nextInt();
                                        int mask1 = 1 << i;
                                        int mask2 = 1 << j;
                                        int mask3 = 1 << k;
                                        int mask4 = 1 << m;
                                        System.out.println(n | mask1);
                                        System.out.println(n & (~mask2));
                                        System.out.println(n ^ mask3);
                                        System.out.println((n & mask4) == 0 ? false : true);
                                    }

    java false

    Time Complexity: O(1)

    The time complexity for the function is constant as basic bit operations are involved.

    Space Complexity: O(1)

    The space complexity for the function is constant.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name