Topics › Bit Manipulation › Learn Bit Manipulation

Check if the i-th bit is Set or Not

Easy TUF ID 177 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer n and a position i. Return true if the i-th bit of n is 1 (set) and false if it is 0 (unset). Bits are counted from the right starting at 0, so bit 0 is the least significant bit with weight 1, bit 1 has weight 2, and bit i has weight 2^i.

Constraints: 0 ≤ i ≤ 31; n is any 32-bit signed integer, but the problem is usually asked for n ≥ 0. For a negative n the answer refers to its two’s-complement pattern, so bit 31 of any negative number is set.

Example 1

n = 13, i = 2
answer = true        // 13 = 1101, bit 2 (weight 4) is 1

Example 2

n = 13, i = 1
answer = false       // 13 = 1101, bit 1 (weight 2) is 0

Example 3

n = 0, i = 0
answer = false       // zero has no set bits at all

Approach 1: Brute force, peel off digits by division

Intuition. Dividing by 2 drops the lowest binary digit, the same way dividing by 10 drops the lowest decimal digit. Divide i times and the bit we care about is now the lowest one, where % 2 reads it. This is the method you would use with no knowledge of bitwise operators at all.

Algorithm.

1. Take n as an unsigned 32-bit value by masking it into a long (so a negative n is treated as its bit pattern rather than as a negative quotient).
2. Divide by 2, i times.
3. Return whether the remainder modulo 2 is 1.

static boolean bruteForce(int n, int i) {
    long v = n & 0xFFFFFFFFL;              // unsigned view, so a negative n behaves like its 32-bit pattern
    for (int k = 0; k < i; k++) v /= 2;
    return v % 2 == 1;
}

Complexity. Time O(i): one division per position below the one asked about. Space O(1).

The 0xFFFFFFFFL mask is only there for negative inputs. Without it, -1 / 2 in Java is 0 (division truncates toward zero), and the loop would say every high bit of -1 is unset. For n ≥ 0 it changes nothing.

Approach 2: Mask with a left shift

Intuition. 1 << i is a number whose only set bit is at position i. AND-ing n with it zeroes every other position, so the result is either 0 (bit i of n was 0) or 2^i (it was 1). We do not care which non-zero value we get, so we compare against 0.

Algorithm.

1. Build the mask 1 << i.
2. Return (n & mask) != 0.

static boolean leftShiftMask(int n, int i) {
    return (n & (1 << i)) != 0;
}

Complexity. Time O(1): one shift, one AND, one comparison. Space O(1).

The comparison must be against 0, not against 1. For i = 2 and n = 13, n & 4 is 4, so == 1 would wrongly report the bit as unset. The one case where == 1 is right is i = 0, which is why the bug often survives a quick test.

Approach 3: Optimal, bring the bit down with a right shift

Intuition. Instead of moving the mask up to the bit, move the bit down to the mask. n >> i shifts the whole number right by i, so the bit that was at position i is now at position 0, and & 1 reads it as exactly 0 or 1. This version is the one to reach for when you want the bit’s value as an integer rather than as a boolean, for example to add it to a counter.

Algorithm.

1. Compute n >> i.
2. AND with 1 and compare with 1.

static boolean rightShift(int n, int i) {
    return ((n >> i) & 1) == 1;
}

Dry run on n = 13 = 1101:

Complexity. Time O(1), space O(1).

Both constant-time versions give identical answers for every n and i, including negatives: >> is an arithmetic shift that copies the sign bit into the vacated positions, but the & 1 only looks at position 0, which holds the original bit i regardless of what was shifted in above it.

Beyond checking: set, clear, toggle

The same mask drives the three sibling operations. OR turns a bit on, AND with the inverted mask turns it off, XOR flips it.

static int setBit(int n, int i) {
    return n | (1 << i);
}

static int clearBit(int n, int i) {
    return n & ~(1 << i);
}

static int toggleBit(int n, int i) {
    return n ^ (1 << i);
}

On 13 = 1101: setBit(13, 1) = 1111 = 15, clearBit(13, 2) = 1001 = 9, toggleBit(13, 0) = 1100 = 12. Setting an already-set bit or clearing an already-clear one leaves n unchanged, which makes these safe to call without checking first.

Edge cases and pitfalls

• i = 0 and n = 0. Zero has no set bits; all three methods return false because 0 & anything is 0.
• Bits beyond the number’s length. 13 has four binary digits, but asking about bit 4 or bit 20 is legal and the answer is simply false; the leading zeros are really there in the 32-bit word.
• i = 31. The mask 1 << 31 is Integer.MIN_VALUE, a negative number, and that is fine: n & Integer.MIN_VALUE is non-zero exactly when the sign bit of n is set. Integer.MAX_VALUE has bit 31 clear and every negative number has it set.
• i ≥ 32. Java reduces the shift amount modulo 32, so 1 << 32 is 1 and the code would silently test bit 0. Validate i if the input can be out of range, or use long with 1L << i for positions up to 63.
• Comparing the mask result with 1. (n & (1 << i)) == 1 only works for i = 0. Compare with 0, or shift the bit down first as in Approach 3.
• Negative n in the brute force. Plain integer division of a negative truncates toward zero and never produces the high bits; the unsigned long view fixes it.

Related problems

• Introduction to Bits and Tricks covers the operators used here and the rest of the basic toolbox.
• Check if a Number is Odd or Not is this problem with i = 0.
• Count the Number of Set Bits applies the bit test at every position.
• Power Set Bit Manipulation uses “is bit i set in the mask” to decide whether element i belongs to a subset.