Check If The kth Bit is Set/Unset, A FAANG Interview Questions - Java
Tags: bitwise, algorithms, java, faang
Published: 2022-02-19 06:36:23

In this article, we try to find a bit in the binary representation of a number at the kth position and check if it is set/un-set.

## Introduction
In this question, input a number and check if the k​th bit is set or not.

## Problem statement
Given two positive integers `n` and `k` check whether the bit at position `k`, from the right in the binary representation of n, is set `1` or unset `0`.

**Example 01:**

```javascript
Input: n = 5, k = 1 
 
Output: true
```

**Example 02:**

```javascript
Input: n = 10, k = 2
 
Output: true
```

**Example 03:**

```javascript
Input: n = 10, k = 1 
 
Output: false
```

## Algorithm

1. If `n == 0` return;

2. Initialize `k = 1`

3. Loop
    - If `(n & (1 << (k - 1))) == 0` increment the pointer `k`
    - Else return `k` 

## Code

Here is the logic for this solution.

```java
class FirstSetBitPosition {
    private static int helper(int n) {
        if (n == 0) {
            return 0;
        }

        int k = 1;
        
        while (true) {
            if ((n & (1 << (k - 1))) == 0) {
                k++;
            } else {
                return k;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("First setbit position for number: 18 is -> " + helper(18));
        System.out.println("First setbit position for number: 5 is -> " + helper(5));
        System.out.println("First setbit position for number: 32 is -> " + helper(32));
    }
}
```

## Complexity analysis
**Time Complexity:** `O(1)` This is always constant time, as we are dealing with the bit representation of the decimals or ASCII. They are represented in either `32` or `64` bit.

**Space Complexity:** `O(1)` extra space, as we are not using any extra space in our code.

## Optimal solution (refactored)

```java
class CheckKthBitSetOrNot {
    private static boolean checkKthBitSet(int n, int k) {
        return (n & (1 << (k - 1))) != 0;
    }

    public static void main(String[] args) {
        System.out.println("n = 5, k = 3 : " + checkKthBitSet(5, 3));
        System.out.println("------------");
        System.out.println("n = 10, k = 2 : " + checkKthBitSet(10, 2));
        System.out.println("------------");
        System.out.println("n = 10, k = 1 : " + checkKthBitSet(10, 1));
    }
}
```

## Explanation
We used the left shift operation to shift the bits to `k​`th position and then use the `&` operation with number `1` and check if it is not-equals to `0`.

Let’s see these in 32-bit binary representation

### Case 01:

```javascript
Input n = 5, k = 3

   n    = 5 = 00000000 00000000 00000000 00000101
   1    = 1 = 00000000 00000000 00000000 00000001
   k    = 3 = 00000000 00000000 00000000 00000011
(k - 1) = 2 = 00000000 00000000 00000000 00000010
```

Now shift `1` with `(k - 1)` positions. We are shifting number `1` two bit positions to the left side.

```javascript
(1 << (k - 1)) = 4 = 00000000 00000000 00000000 00000100
```

Now, doing & operation of `n` and `(1 << (k - 1))` will give us a decimal number. If that is not equal to `0`, then the bit is set, and we return `true`.

```javascript
         n         = 5 = 00000000 00000000 00000000 00000101
  (1 << (k - 1))   = 4 = 00000000 00000000 00000000 00000100
-------------------------------------------------------------
n & (1 << (k - 1)) = 4 = 00000000 00000000 00000000 00000100
-------------------------------------------------------------
```

So, `n & (1 << (k - 1)) = 4`, which is not `0`, so we return `true`.

## Complexity analysis
**Time Complexity:** `O(1)` This is always constant time, as we are dealing with the bit representation of the decimals or ASCII. They are represented in either `32/64` bit.

**Space Complexity:** `O(1)` extra space, as we are not using any extra space in our code.


We can solve this problem using the right shift as well. We will see how to solve the same problem using the `>>` operator in the next chapter.

---

## Extras

If you are interested in mastering bit tricks, I've got a course that are loved by more than 100k+ programmers. 

In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. The course has simple explanation with sketches, detailed step-by-step drawings, and various ways to solve it using bitwise operators. 

These bit-tricks could help in competitive programming and coding interviews in running algorithms mostly in `O(1)` time.

This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG(Facebook, Amazon, Apple, Netflix, and Google) companies.

To kick things off, you’ll start by learning about the number system and how it’s represented. Then you’ll move on to learn about the six different bitwise operators: AND, OR, NOT, XOR, and bit shifting. Throughout, you will get tons of hands-on experience working through practice problems to help sharpen your understanding.

By the time you’ve completed this course, you will be able to solve problems faster with greater efficiency!! 🤩

Link to my course: [Master Bit Manipulation for Coding Interviews](https://www.educative.io/courses/bit-manipulation?aff=xjzd).