Check if Kth bit is set or not

Problem Statement: Check if kth bit is set or not.

Examples:

Example 1:
Input: n=5 ,k=0
Output: Yes
Explanation: The binary representation of n is “101”.Since 0th bit is set,”Yes” will be printed.

Example 2:
Input: n=8 ,k=2
Result: No
Explanation: The binary representation of n is “1000”.Since 2nd bit is not set,”No” will be printed.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Using left shift operator.

Approach:

Left shift 1 by k bits and store it in a variable say p.
Now perform “&” operation of n and p.
If the resultant is 0 print “NO” else print “YES”

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main() {
  int n = 5, k = 3;
  int p = (1 << k);
  if ((n & p) != 0) {
    cout << "YES" << "\n";
  } else {
    cout << "NO" << "\n";
  }
}

Output: YES

Time Complexity: O(1).

Space Complexity: O(1).

Java Code

import java.util.*;

class TUF{
public static void main(String args[]) {
  int n = 5, k = 0;
  int p = (1 << k);
  if ((n & p) != 0) {
    System.out.println("YES");
  } else {
    System.out.println("NO");
  }
}
}

Output: YES

Time Complexity: O(1).

Space Complexity: O(1).

Solution 2:Using right shift operator

Approach:

Right shift n by k bits.
Now the kth bit is shifted to 0th position.
Now simply check whether 0th bit is set or not using “&” operator.
If 0th bit is set print “YES”,else print “NO”.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main() {
  int n = 5, k = 0;
  n=(n>>k);
  if ((n & 1) != 0) {
    cout << "YES" << "\n";
  } else {
    cout << "NO" << "\n";
  }
}

Output: YES

Time Complexity: O(1).

Space Complexity: O(1).

Java Code

import java.util.*;

class TUF{
public static void main(String args[]) {
  int n = 5, k = 0;
  n=(n>>k);
  if ((n & 1) != 0) {
    System.out.println("YES");
  } else {
    System.out.println("NO");
  }
}
}

Output: YES

Time Complexity: O(1).

Space Complexity: O(1).

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article