Bit Manipulation

Use binary representations and bitwise operators for masks, flags, and compact state.

Est. 75 min Updated Suggest a fix
💡 Note
Prerequisites: integer types, arrays, loops, and basic binary place values. Examples use C’s uint32_t from stdint.h; this makes the width explicit and avoids many surprises from signed shifts.

Objectives: represent and update compact flags

A bit is a binary digit, either zero or one. In an unsigned integer, bitwise operations act independently on corresponding bit positions. Bitmasks are useful for compact flags, small sets of options, subset enumeration, and state compression. They are not automatically faster or clearer than an array or set—use them when the finite domain and width make the representation appropriate.

🎯 Pro Tip
The Interview Problem-Solving Patterns unit already covers common interview prompts. This lesson builds the underlying operator model; use Interview Problem-Solving Patterns → for separate pattern practice.

1. Binary place values and core operators

For an unsigned value, bit position 0 is the least significant bit and has value 2⁰; position 1 has value 2¹, and so on. AND (&) keeps a bit only when both inputs have it set. OR (|) sets a bit when either input has it set. XOR (^) sets a bit when the inputs differ. NOT (~) flips every bit in the integer type’s width, so it is often best used with an explicit mask.

OperatorMeaningCommon use
a & bSet only where both bits are 1Test selected bits or keep a mask
a | bSet where either bit is 1Set one or more flags
a ^ bSet where bits differToggle a bit; parity/XOR reductions
a << kShift bits left by k positionsForm a bit mask or scale unsigned values
a >> kShift bits right by k positionsInspect lower/higher portions of unsigned values

2. Set, clear, toggle, and test one bit

Build a one-bit mask by shifting the unsigned value 1 to the desired position. OR sets that bit; AND with the complement clears it; XOR toggles it. AND with the mask tests whether it is set. The caller must guarantee that the bit index is in the valid range 0 through 31.

Small, explicit bit operations · C
#include <stdbool.h>
#include <stdint.h>

uint32_t set_bit(uint32_t value, unsigned bit) {
    return value | (UINT32_C(1) << bit);
}

uint32_t clear_bit(uint32_t value, unsigned bit) {
    return value & ~(UINT32_C(1) << bit);
}

uint32_t toggle_bit(uint32_t value, unsigned bit) {
    return value ^ (UINT32_C(1) << bit);
}

bool is_bit_set(uint32_t value, unsigned bit) {
    return (value & (UINT32_C(1) << bit)) != 0;
}

For production interfaces, validate bit < 32 before shifting. In C, shifting by a count greater than or equal to the operand width is undefined behavior. Use unsigned fixed-width values for masks; right-shifting a negative signed integer can be implementation-defined, and left-shifting signed values can overflow with undefined behavior.

3. Masks as small sets

When there are at most 32 distinct options, bit i can represent whether option i is present. A subset can be inserted or removed with the same set/clear operations. To check whether all required flags are set, compare (mask & required) == required; to check whether any are set, compare the result to zero. This representation makes union and intersection direct, but it does not preserve order or repeated items.

Subset checks and a single-occurrence XOR reduction · C
#include <stdbool.h>
#include <stdint.h>

bool contains_all(uint32_t flags, uint32_t required) {
    return (flags & required) == required;
}

bool contains_any(uint32_t flags, uint32_t choices) {
    return (flags & choices) != 0;
}

uint32_t find_unique_value(const uint32_t values[], int n) {
    uint32_t answer = 0;
    for (int i = 0; i < n; i++) answer ^= values[i];
    return answer;
}

The XOR reduction returns the unique value only under a precise contract: exactly one unsigned value appears once and every other value appears exactly twice; XOR is bitwise, so cancellation is exact. It does not solve the same task when duplicates appear arbitrary numbers of times. For sets with a larger or dynamic universe, use an appropriate set or bitset abstraction rather than overflowing this fixed-width mask.

4. Count set bits and test powers of two

Kernighan’s identity clears the lowest set bit each iteration: for nonzero unsigned x, x & (x − 1) is x with its least significant 1 removed. Therefore the loop count equals the number of set bits, also called the population count. A nonzero power of two has exactly one set bit; this identity gives a compact test.

Population count and power-of-two check · C
#include <stdbool.h>
#include <stdint.h>

unsigned count_set_bits(uint32_t value) {
    unsigned count = 0;
    while (value != 0) {
        value &= value - 1;
        count++;
    }
    return count;
}

bool is_power_of_two(uint32_t value) {
    return value != 0 && (value & (value - 1)) == 0;
}

The count runs in O(number of set bits), at most 32 iterations for a 32-bit value. Some platforms provide hardware-backed population-count instructions or compiler/library helpers; use a portable interface appropriate for the project instead of assuming a non-standard builtin exists.

5. Enumerate subsets with a bitmask

For n options, each integer mask from zero through 2ⁿ−1 represents one subset. If bit i is set, item i is included. This technique is useful for exhaustive search when n is deliberately small; the number of subsets doubles each time n increases by one, so it does not make an exponential problem scalable by itself. Keep the number of bits within the mask width.

Iterate subsets for at most 20 options · C
#include <stdint.h>
#include <stdio.h>

void print_subsets(const int items[], unsigned n) {
    if (n > 20) return; /* keep exhaustive work bounded */
    uint32_t limit = UINT32_C(1) << n;
    for (uint32_t mask = 0; mask < limit; mask++) {
        printf("{");
        for (unsigned i = 0; i < n; i++)
            if ((mask & (UINT32_C(1) << i)) != 0) printf(" %d", items[i]);
        printf(" }
");
    }
}

The guard makes both the shift and the amount of work explicit. This example uses a smaller limit than the full type width because generating millions of subsets quickly becomes impractical. Empty mask zero represents the empty subset; the final mask has every option present.

6. Precedence and signedness deserve attention

Parenthesize bitwise expressions even when operator precedence is known. In C, equality operators bind more tightly than bitwise AND, so value & mask == mask is parsed differently from the intended all-bits test. Write (value & mask) == mask. Also prefer explicit unsigned constants and types; integer promotions can make small integer operands behave as int.

For a collection of named flags, declare the position and construct masks once instead of scattering numeric literals. Keep unrelated flag groups separate, define which bits may be set, and mask off reserved bits when importing a value from a file or network packet. This makes changes easier to review and prevents an unknown flag from silently changing behavior.

📌 Real World Example
For feature flags in a compact configuration, define a named mask for each feature and use helper functions that validate indices. That is clearer and safer than scattering raw shifts such as 1 << 17 throughout application code.

7. Common mistakes

  • Shifting a signed 1: high-bit shifts can overflow or be undefined. Use a fixed-width unsigned value and a valid shift count.
  • Forgetting to parenthesize a test: equality binds tighter than bitwise AND in C; write (x & mask) != 0.
  • Assuming NOT flips only meaningful flags: ~mask flips every bit in the type. AND with an explicit allowed-bits mask when needed.
  • Using a bitmask for an unbounded set: a fixed-width integer has a strict limit and no duplicate/order semantics.

8. Practice

  1. Implement a helper that toggles a validated flag and returns an error for an index outside 0…31.
  2. Given two permission masks, determine whether the user has every required permission and whether any optional permission is granted.
  3. Count set bits using the simple shift-and-test loop; compare its iteration count to Kernighan’s method for sparse and dense inputs.
  4. Enumerate all subsets of a collection of n ≤ 20 items using a mask. Explain the time and memory growth.
  5. Prove why XOR cancels paired values, then construct a counterexample when one duplicate occurs three times.

🎯 Key Takeaways

  • ✓Bitwise operators work on individual positions of integer representations.
  • ✓A mask lets an unsigned integer represent a fixed set of flags.
  • ✓Set, clear, toggle, and test use OR, AND, XOR, and AND respectively.
  • ✓Validate shift width and use explicit unsigned types to avoid undefined behavior.
  • ✓Parenthesize expressions because C operator precedence can change their meaning.
  • ✓Bitmasks are effective only when the domain fits and their semantics stay clear.

Next

Move from compact state to range queries with dedicated tree structures.

Lesson 27 · Advanced Topics →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...