Bit Manipulation – DSA Notes

Small, fast solutions using bitwise tricks.

---

📌 Summary Table

Problem	Core Trick	Time	Space
Power of Two	n & (n-1) clears lowest set bit	O(1)	O(1)
Counting Bits (0..n)	DP: bits[i] = bits[i>>1] + (i&1)	O(n)	O(n)
Divide Two Integers	Subtract shifted divisor (bitwise long division)	O(32)	O(1)
Power Set (String)	Enumerate bitmasks 0..(1<<n)-1	O(n·2ⁿ)	O(2ⁿ)
Most Significant Set Bit	highestOneBit / bit-spread	O(1)	O(1)
Square without */pow	Recurrence on parity (n=2x / 2x+1)	O(log n)	O(log n) stack

---

Power of Two

Problem. Check if n is a power of two.

Idea. A power of two has exactly one set bit; n & (n-1) clears the lowest set bit → result is 0 iff only one bit was set.

class Solution {
    public boolean isPowerOfTwo(int n) {
        // n > 0 avoids negative/zero; (n & (n-1)) == 0 means only one bit set
        return n > 0 && (n & (n - 1)) == 0;
    }
}

Key Takeaway. One-liner: n > 0 && (n & (n-1)) == 0.

---

Counting Bits (0..n)

Problem. For each i ∈ [0..n], return the number of set bits in i.

Idea. DP by halving: i >> 1 drops the last bit; (i & 1) adds the last bit back.

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        // res[0] = 0 by default
        for (int i = 1; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1); // bits of half + last bit
        }
        return res;
    }
}

Key Takeaway. bits[i] = bits[i/2] + (i%2) but done with shifts/ands.

---

Divide Two Integers (No *, /, %)

Problem. Compute dividend / divisor truncated toward zero; handle overflow.

Idea. Use bitwise long-division: subtract the largest shifted divisor each time. Work in long to avoid intermediate overflow, then clamp final result if needed.

class Solution {
    public int divide(int dividend, int divisor) {
        // Overflow-only edge case: MIN / -1
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

        // Use long for safe shifting/abs
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        int sign = ((dividend ^ divisor) < 0) ? -1 : 1;

        long ans = 0; // accumulate with bits

        // Try to subtract b<<i from a, from high bit to low bit
        for (int i = 31; i >= 0; i--) {
            if ((a >> i) >= b) {     // means b<<i <= a without overflow
                a -= (b << i);       // subtract this chunk
                ans += (1L << i);    // set the i-th bit of the quotient
            }
        }
        ans = sign > 0 ? ans : -ans;

        // Clamp just in case (should be within int range except handled case)
        if (ans > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (ans < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        return (int) ans;
    }
}

Key Takeaway. Think binary long-division: subtract biggest divisor << i.

---

Power Set (All Subsets of String)

Problem. Return all non-empty subsets of a string in lexicographic order.

Idea. For each bitmask mask in 1..(1<<n)-1, include character j if bit j is set.

class Solution {
    public List<String> AllPossibleStrings(String s) {
        List<String> ans = new ArrayList<>();
        int n = s.length();
        // mask = 0 would be the empty subset; here we skip it by starting at 1
        for (int mask = 1; mask < (1 << n); mask++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) sb.append(s.charAt(j));
            }
            ans.add(sb.toString());
        }
        Collections.sort(ans); // optional, per many judge specs
        return ans;
    }
}

Key Takeaway. Subsets ↔ bitmasks; each bit chooses a position.

---

Most Significant Set Bit (MSB) Mask

Problem. Return a mask with only the highest set bit of n (e.g., n=10 (1010b) → 8 (1000b)).

Idea A (built-in). Integer.highestOneBit(n) does exactly this. Idea B (bit-spread). Spread highest bit to all lower bits, then isolate.

class Util {
    public static int msbMask(int n) {
        if (n <= 0) return 0;
        // Built-in: return Integer.highestOneBit(n);

        // Bit-spread approach (portable & log-free)
        n |= (n >> 1);
        n |= (n >> 2);
        n |= (n >> 4);
        n |= (n >> 8);
        n |= (n >> 16);
        return (n + 1) >>> 1; // isolate highest bit
    }
}

Why not Math.log? Floating-point rounding can fail for large powers-of-two. Bit hacks are exact.

Key Takeaway. Use highestOneBit or bit-spread + shift for precise MSB.

---

Square without * or pow

Problem. Compute n² without using multiplication or pow.

Idea. Write n = 2x or 2x+1:

• If n even: n² = 4·x².
• If n odd: n² = 4·x² + 4·x + 1. Recurse on x = n >> 1. Handle negatives via absolute.

class MathUtil {
    public static int square(int n) {
        if (n == 0) return 0;
        // Make n non-negative; squaring negs equals squaring abs value
        if (n < 0) n = -n;

        int x = n >> 1; // n / 2
        int sqx = square(x);

        if ((n & 1) == 0) {
            // n = 2x: (2x)^2 = 4 * x^2
            return sqx << 2;
        } else {
            // n = 2x + 1: (2x+1)^2 = 4x^2 + 4x + 1
            return (sqx << 2) + (x << 2) + 1;
        }
    }
}

⚠️ Note: Result may overflow 32-bit int for large |n| (e.g., |n| > 46340). If needed, switch intermediates and return type to long.

Key Takeaway. Parity recurrence reduces work to O(log n) via shifts/adds.

---