Lesson 47Advanced58 minAssessment-backed

Bit Manipulation

Use bits for flags, masks, subsets, compact state, permissions, and low-level performance decisions.

What you will be able to do

Explain bits as compact boolean state.

Use AND, OR, XOR, shifts, and masks safely.

Solve common bit problems such as single number and subset masks.

Connect bitmasks to permissions, feature flags, and DP state compression.

Name signedness and readability risks in production code.

Bit manipulation is not just trick code. It is compact state modeling: permissions, feature flags, subsets, and low-level representations.

Bits as State

A bitmask lets one integer carry many boolean answers. The important engineering question is whether the compactness is worth the readability and representation constraints.

Bitmask flags for permissions — Each bit can represent one permission, feature flag, or subset decision.

Scenario: Permission Flags

A game server or embedded system may store permissions as bit flags to reduce memory and serialize state cheaply. A SaaS app may prefer explicit sets for clarity unless memory, transport size, or compatibility pushes toward bitmasks.

Operation	Expression	Meaning
Set flag	mask \| flag	Turn bit on.
Clear flag	mask & ~flag	Turn bit off.
Check flag	(mask & flag) != 0	Test membership.
Toggle flag	mask ^ flag	Flip bit.

XOR cancels pairs to find single number — XOR cancels equal pairs and keeps the unpaired value.

Same Pattern in Java, Python, and JavaScript

Single Number is the canonical XOR interview problem: every number appears twice except one.

class SingleNumber {
    static int singleNumber(int[] nums) {
        int answer = 0;
        for (int value : nums) answer ^= value;
        return answer;
    }
}

Assessment trap

Bit tricks must come with invariants. Explain why XOR cancellation works, or why a mask represents the full state.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Every number appears twice except one. Return the unpaired number.
Return bit counts for every number from 0 to n.
Return all subsets of an array.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Permission flags	Store many booleans as verbose payload fields.	Use named bit flags when compact transport/storage matters.	Readability and migration need constants.
Subset search	Build all subset arrays before scoring.	Use integer masks to enumerate subset state compactly.	Only works comfortably for small n.
Duplicate-pair stream	Use a set when every value appears twice except one.	XOR accumulator finds the unpaired value in O(1) space.	Only valid under the exact pair invariant.

Solved modelInterview Question Solutions

Question 1: Single Number

Every number appears twice except one. Return the unpaired number. XOR all values. Pairs cancel because x ^ x = 0, and 0 ^ y = y.

class SingleNumber {
    static int singleNumber(int[] nums) {
        int answer = 0;
        for (int value : nums) answer ^= value;
        return answer;
    }
}

Question 2: Counting Bits

Return bit counts for every number from 0 to n. Use recurrence bits[i] = bits[i >> 1] + (i & 1), reusing the count for i without its lowest bit.

class CountingBits { static int[] countBits(int n) { int[] bits = new int[n + 1]; for (int i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1); return bits; } }

Question 3: Subsets With Bitmask

Return all subsets of an array. Each mask from 0 to 2^n - 1 represents one subset; bit i says whether nums[i] is included.

import java.util.*;
class Subsets { static List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); for (int mask = 0; mask < (1 << nums.length); mask++) { List<Integer> cur = new ArrayList<>(); for (int i = 0; i < nums.length; i++) if ((mask & (1 << i)) != 0) cur.add(nums[i]); ans.add(cur); } return ans; } }

Solved modelWorked Interview Answer

Find the number that appears once when every other number appears twice. XOR cancels equal pairs and leaves the unpaired value, so a single pass with one accumulator solves the problem.

class SingleNumber {
    static int singleNumber(int[] nums) {
        int answer = 0;
        for (int value : nums) answer ^= value;
        return answer;
    }
}

Hands-on drillTry It Yourself

Practice task

Represent read, write, deploy, and admin permissions as four bits. Show set, clear, and check operations.

Failure patternsCommon Mistakes to Avoid

Using bit tricks without explaining invariants.
Confusing XOR with OR.
Forgetting signed integer behavior.
Making production code unreadable for minor gains.
Using bitmask when the number of flags can exceed integer width.

Execution guardrailQuick-Start Checklist

Define what each bit means.
Choose operation: AND/OR/XOR/shift.
Handle signedness/width.
Add constants for readability.
Explain invariant.
State complexity.

Recall drillKnowledge Check

Question	Strong answer
Why does XOR find single number?	Equal pairs cancel to zero and zero XOR x is x.
What does mask & flag test?	Whether that flag bit is present.
When are bitmasks useful?	Compact fixed-size boolean state.

VocabularyKey Terms

Term	Meaning
Bitmask	Integer whose bits encode flags or subset membership.
XOR	Exclusive OR; equal values cancel under pairing.
Shift	Move bits left or right.
Flag	Named bit representing one boolean property.

Next practiceFurther Reading

Practice single number, counting bits, subsets, and bitwise AND of range.
Review two's complement and language-specific integer width.
Use named constants in production code.

Segment Tree and Range Queries

DSA in System Design