Java Program to Check if K-th Bit is Set or Not

In computer programming, numbers are usually represented in binary, where each bit (digit) can be either 0 or 1. The k-th bit of a number corresponds to the bit at position k, with the rightmost bit (least significant bit) being counted as position 0.

To determine whether the k-th bit is set (1) or not set (0), we use bitwise operations. These operations allow us to efficiently inspect and manipulate individual bits of a number.

Problem Statement

We have given a number (n)and a bit number (k). We have to check if the k^th index bit of number n is set or not. The position of bit should be indexed starting with 0 from the LSB side in the binary representation of the number.

Set: if bit is 1

Not set: if it is 0

Let's understand it through an example.

Example of K-th Bit is Set or Not

Example 1:

Input: n=7, k=2

Output: SET

Explanation: 7 is represented as 111 in binary. The bit at position 2 (counting from 0) is 1 which is SET.

Example 2:

Input>: n=4, k=0

Output>: NOT SET

Explanation>: 4 is represented as 100 in binary. The bit at position 0 (counting from LSB) is 0, so it is NOT SET.

Approach: Using Left Shift Operation

This method utilizes the left shift operator (<<) to generate a mask with the k-th bit set. A bitwise AND operation (&) is then applied between the number and the mask to determine whether the k-th bit is set or not.

Algorithm

Step 1: Shift 1 left by k positions to create a mask for the k-th bit.

Step 2: Perform bitwise AND operation between the number n and the mask created.

Step 3: If the outcome is not zero, it signifies that the k-th bit is activated to 1.

Step 4: If the outcome is zero, it indicates that the k-th bit is not configured to 1.

Step 5: Print "SET" if the k-th bit is active; otherwise, print "NOT SET".

Let's implement the above algorithm in a Java program.

Output:

 The 3-th bit is SET. 

Time Complexity: The time complexity of the above code is O(1).

Auxiliary Space Complexity: The auxiliary space complexity of the above code is O(1).

Approach: Using Right Shift Operator

This method employs the right shift operator (>>) to shift the k-th bit to the least significant position. Then, the least significant bit is checked to see whether the k-th bit is set or not.

Algorithm

Step 1: Right shift the number n by k positions using n >> k.

Step 2: The least significant bit (LSB) of the result will be the k-th bit of n.

Step 3: If the result of n >> k is odd, the k-th bit is set; otherwise, it's not.

Step 4: Print "SET" if the least significant bit is 1, otherwise print "NOT SET".

Let's implement the above algorithm in a Java program.

File Name: CheckKthBit.java

Output:

 The 3-th bit is SET. 

Time Complexity: The time complexity of the above code is O(1).

Auxiliary Space Complexity: The auxiliary space complexity of the above code is O(1).