Check if All Bits Set

Problem Overview

A number has all its bits set in binary if it is of the form 2^k - 1 (e.g., 7 = 0b111, 15 = 0b1111, 31 = 0b11111).

Intuition

A number has all its bits set in binary if it is of the form 2^k - 1 (e.g., 7 = 0b111, 15 = 0b1111, 31 = 0b11111). The key insight is that n = 2^k - 1 if and only if n + 1 = 2^k. Since a power of 2 has exactly one bit set, we can check (n+1) & n: if n is all-bits-set, then n+1 and n have no overlapping bits, so their AND is 0.

Algorithm

1Given n, compute m = n + 1.
2Check each bit of m by repeatedly dividing by 2 and taking modulo 2.
3If m is a power of 2, all bits are 0 except the highest bit (e.g., 8 = 0b1000).
4Return true if all intermediate bits are 0; return false if any intermediate bit is 1.
5Alternatively, use the bitwise trick: (n+1) & n == 0 iff n is all-bits-set.

Example Walkthrough

Input: n = 7

1. n = 7 = 0b0111 (three bits set).
2. n + 1 = 8 = 0b1000 (one bit set, a power of 2).
3. (n+1) & n = 0b1000 & 0b0111 = 0b0000 = 0 ? ? true.

Output: true

Common Pitfalls

• Zero is not all-bits-set; the edge case n=0 should return false.
• The modulo-based loop checks if n+1 is a power of 2 by verifying all intermediate bits are 0; off-by-one errors can break this.
• Do not confuse "all bits set" with "maximum value"; all-bits-set numbers are sparse (1, 3, 7, 15, 31, ...).

Check if All Bits Set.java

Java


// Approach: Check if n+1 is a power of 2. A number has all bits set
// (e.g., 0b111 = 7, 0b1111 = 15) iff n = 2^k - 1, which means n+1 = 2^k.
// A power of 2 has exactly one bit set, so (n+1) & n == 0 when n is all-bits-set.
// Time: O(log n) Space: O(1)

class Solution {

    public boolean isBitSet(int n) {
        if (n == 0) {
            return false;
        }
        int num = (n + 1);
        while (num > 1) {
            int dig = num % 2;
            if (dig != 0) {
                return false;
            }
            num = num / 2;
        }
        
        return true;
    }
};

Was this solution helpful?