Bit Manipulation and Mathematics Questions

Focuses on algorithmic and mathematical techniques that use bit level operations and discrete mathematics. Includes bitwise operators and tricks such as masking, shifting, counting bits, parity, extracting or setting fields, fast multiplication or division by powers of two, and common bit hacks. Also covers number theory and modular arithmetic fundamentals used in algorithm design, combinatorics basics for counting and enumerations, constructive mathematical reasoning, and designing creative problem solving approaches that combine bit manipulation with mathematical insight. Performance implications and complexity analysis of bit based solutions are also included.

EasyTechnical

87 practiced

You must implement feature flags for up to 60 independent boolean flags per user. Propose an efficient storage and API design using a single 64-bit bitmask per user: show how to set/clear/query flags, serialize to API responses, migrate to add new flags, and compare trade-offs with storing flags as a dictionary of booleans in a database.

Sample Answer

Approach: use a single unsigned 64-bit integer per user where each flag is a bit position (0..59). This is compact, fast to read/write, and atomic-friendly.

Code (Python examples):

python

# Define flags (enum-like)
FLAG_A = 1 << 0
FLAG_B = 1 << 1
# ...
FLAG_60 = 1 << 59

# Set a flag
def set_flag(mask: int, flag: int) -> int:
    return mask | flag

# Clear a flag
def clear_flag(mask: int, flag: int) -> int:
    return mask & ~flag

# Query a flag
def has_flag(mask: int, flag: int) -> bool:
    return (mask & flag) != 0

# Serialize selected flags to API-friendly dict
def serialize(mask: int, flag_map: dict) -> dict:
    return {name: bool(mask & bit) for name, bit in flag_map.items()}

Storage/API:- Persist a single BIGINT/unsigned bigint column "feature_mask" per user.- Expose API boolean map using serialize() with a server-side canonical flag_map (name -> bit).- Allow clients to request only changed flags (diff against last_mask) for efficiency.

Migration (adding/removing flags):- Adding: assign next free bit; update server flag_map. No DB migration needed.- Removing/deprecating: stop reading that bit; optionally zero it via backfill job.- Renaming: update flag_map mapping without changing bits.

Trade-offs vs dict-of-booleans:- Pros of bitmask: compact (8 bytes), fast bit ops, single-column atomic updates, simpler indexes/queries.- Cons: less self-describing in DB (need server-side map), harder to query users by flag in some DBs unless using bitwise index/support; limited to 64 flags (fits your 60).- Dict booleans: more readable, flexible schema, easier per-flag indexing and migrations, but larger storage, more columns/JSON complexity, and more expensive updates.

Best practice:- Keep authoritative flag_map in code + migrations repository.- Version flag_map and support backward compatibility in API.- Provide admin tooling to map bits to names and run backfills.

EasyTechnical

92 practiced

Write a Python function to count the number of set bits in a 64-bit unsigned integer. Provide two implementations: (1) a straightforward method using the n & (n-1) loop, and (2) an optimized approach suitable for many repeated queries (e.g., byte lookup table or SWAR/Hamming weight). Discuss time, space trade-offs, and which approach you would use in a high-throughput service.

Sample Answer

Approach summary:- Method 1 (n & (n-1)): simple loop removing the lowest set bit each iteration. Good for small numbers of queries or sparse bitsets.- Method 2 (fast for many queries): use a precomputed 256-entry byte lookup table, or use a SWAR (parallel) bit trick. Lookup-table trades small memory (256 bytes) for constant-time per byte; SWAR uses arithmetic masks and few operations.

Implementation 1 — n & (n-1) loop:

python

def popcount_simple(n: int) -> int:
    """
    Count set bits using n & (n-1).
    Assumes n fits in 64-bit unsigned (0 <= n < 2**64).
    """
    n &= (1 << 64) - 1
    count = 0
    while n:
        n &= n - 1  # clear lowest set bit
        count += 1
    return count

Implementation 2a — byte lookup table (good for many repeated queries):

python

# build table once
BYTE_POPCOUNT = [bin(i).count("1") for i in range(256)]

def popcount_lookup(n: int) -> int:
    n &= (1 << 64) - 1
    total = 0
    for _ in range(8):  # process 8 bytes of 64-bit
        total += BYTE_POPCOUNT[n & 0xFF]
        n >>= 8
    return total

Implementation 2b — SWAR (Hamming weight, few ops):

python

def popcount_swar(n: int) -> int:
    n &= (1 << 64) - 1
    # 64-bit SWAR algorithm
    n = n - ((n >> 1) & 0x5555555555555555)
    n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
    n = (n + (n >> 4)) & 0x0F0F0F0F0F0F0F0F
    return (n * 0x0101010101010101) >> 56 & 0xFF

Key points and trade-offs:- Simple loop: time O(k) where k = number of set bits; best when k is small. Space O(1). Easy to read.- Lookup table: time O(1) with ~8 table lookups and shifts per 64-bit number; constant and fast for many queries. Space O(256) for table (negligible).- SWAR: time O(1) with few arithmetic/bit ops, no extra memory. Usually faster in low-level languages; in CPython the arithmetic overhead may reduce advantage versus lookup, but it's still competitive.- Python note: modern Python provides int.bit_count() (C-level) — use that in production for clarity and best performance: return (n & mask).bit_count().

Recommendation for high-throughput service:- In Python, prefer the built-in int.bit_count() (C-optimized). If unavailable, use the lookup-table approach for many repeated queries (predictable, branchless, memory cheap). Use n & (n-1) when code clarity matters or when inputs are extremely sparse and queries are infrequent.

HardTechnical

92 practiced

Solve subset sum for n <= 40 and target S up to 1e12 using meet-in-the-middle: split array into two halves, enumerate all subset sums for each half, sort one list, and use two-pointer or binary search to count combinations summing to S. Then discuss how a bitset-based DP (bitset convolution) might be used when S is small and how to combine approaches for mixed constraints.

Sample Answer

Approach (meet-in-the-middle)Split array a[0..n-1] into L and R (n<=40). Enumerate all subset sums of each half (2^(n/2) ≤ ~2^20 ≈ 1e6): produce vectors SL and SR. Sort SR. For each x in SL, count how many y in SR satisfy x+y == S using binary search (or two-pointer on sorted SL and SR). This counts combinations in O(2^(n/2) * log 2^(n/2)) time.

C++ implementation (core parts):

cpp

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

vector<int64> gen(const vector<int64>& a){
    int m=a.size();
    vector<int64> res(1<<m);
    for(int mask=0; mask<(1<<m); ++mask){
        int64 s=0;
        for(int i=0;i<m;++i) if(mask>>i &1) s+=a[i];
        res[mask]=s;
    }
    return res;
}

int64 count_sum(vector<int64>& A, vector<int64>& B, int64 S){
    sort(B.begin(), B.end());
    int64 cnt=0;
    for(auto x: A){
        auto range = equal_range(B.begin(), B.end(), S-x);
        cnt += distance(range.first, range.second);
    }
    return cnt;
}

ComplexityTime: O(2^(n/2) * n/2 + 2^(n/2) log 2^(n/2)). Space: O(2^(n/2)).

Bitset-based DP when S smallIf S ≤ ~1e7 (fits memory), use a bitset dp where dp[0]=1 and for each value v: dp |= (dp<<v). Using machine-word bitsets (std::bitset or vector<uint64_t>) this runs in O(n * S / 64). It’s fast and counts reachability; to count ways you can use integer arrays with convolution-like techniques (or use multiple bitsets for small counts).

Combining approaches (mixed constraints)- If S small and n moderate → bitset DP.- If n ≤ 40 and S large (up to 1e12) → meet-in-the-middle.- Hybrid: split items into two groups; for the group with small total-sum range use bitset to produce a frequency map of sums; for the other group (large values but few items) enumerate subsets and lookup counts in the bitset-produced map. This reduces memory vs full bitset on S while keeping enumeration small.Edge cases: negative numbers (shift sums), duplicates, empty subset vs S==0.

MediumTechnical

94 practiced

All elements in an integer array appear exactly twice except for two elements that appear only once. Implement an O(n) time and O(1) extra space C++ function to find those two unique numbers. Explain the XOR partitioning trick you use and why it separates the two singletons.

Sample Answer

Approach: Use XOR partitioning. XORing all numbers yields x = a ^ b (because pairs cancel). Find a bit where a and b differ (rightmost set bit of x). Partition numbers into two groups based on that bit and XOR within each group to isolate the two unique numbers. This is O(n) time and O(1) extra space.

cpp

#include <vector>
#include <utility>

std::pair<int,int> findTwoSingles(const std::vector<int>& nums) {
    // XOR of all elements = a ^ b
    int x = 0;
    for (int v : nums) x ^= v;
    // mask = rightmost set bit of x (a and b differ here)
    int mask = x & -x;
    int a = 0, b = 0;
    // Partition by mask and xor within each partition
    for (int v : nums) {
        if (v & mask) a ^= v;
        else b ^= v;
    }
    return {a, b};
}

Key points:- mask = x & -x isolates a bit that is 1 in exactly one of a or b, so partitioning separates them.- Each partition contains one singleton and many paired duplicates that cancel under XOR, leaving that singleton.Time Complexity: O(n). Space Complexity: O(1) extra space (ignoring input). Edge cases: handle small arrays (size >=2), negative numbers work due to two's complement. Alternative: hash map O(n) time, O(n) space.

HardSystem Design

86 practiced

Design a compact bitfield encoding for network packet headers that packs variable-length fields into minimal bits, supports optional fields via presence flags, aligns for 64-bit processing efficiency, and allows backward-compatible extensions. Specify encoding rules, parsing algorithm in C (low-branch approach), endian handling, versioning strategy, and how to handle future additions of fields.

Sample Answer

Requirements & approach:- Pack variable-length fields tightly with a 64-bit-aligned wire format for CPU efficiency.- Use a small fixed primary header that contains: magic(8), version(4), presence_bitmap_len(4), presence_bitmap (variable, up to 56 bits in first 64-bit word), then consecutive 64-bit words containing field payloads packed bitwise. Optional fields indicated by bitmap. Backwards-compatible extension via version + TLV extension area after core fields.- Endian on-wire: network byte order (big-endian). Processors use ntoh64 helper to convert.

Encoding rules:1. Primary 64-bit word layout (big-endian): - bytes[0]: magic (8) - bits 8-11: version (4) - bits 12-15: bitmap_len_words (4) — how many 64-bit words follow that contain presence bitmap (0..7) - bits 16-63: first presence bitmap bits (48)2. Presence bitmap bit i => field i present. Field definitions have fixed bit-lengths or variable-length encoded with a small length prefix (e.g., 6-bit length) stored adjacent.3. Following bitmap words (if any) complete presence map up to N fields.4. After bitmap, fields are packed sequentially bitwise into 64-bit words (MSB-first). For variable-length fields, store length (6 bits) + payload bits.5. After core fields, an optional TLV extension area: repeated {type(8), length(16), value(variable, byte-aligned)}. Parsers that don't understand a type skip by length.

Parsing algorithm (C, low-branch, uses masks & shifts; minimal conditionals — use population counts and pointer arithmetic). Assumes buf points to network-order bytes and buf_len >= 8.

#include <stdint.h>
#include <string.h>
#include <arpa/inet.h> // for ntohl, ntohs

static inline uint64_t ntoh64(const void *p){
    uint32_t hi = ntohl(*(uint32_t*)p);
    uint32_t lo = ntohl(*((uint32_t*)p + 1));
    return ((uint64_t)hi << 32) | lo;
}

/* Read next n bits (n<=64) from stream (big-endian bit stream) */
typedef struct { const uint8_t *b; size_t len; size_t bit; } bitstream;

static inline uint64_t bs_read(bitstream *s, unsigned n){
    uint64_t out = 0;
    unsigned need = n;
    while(need){
        size_t byte_idx = s->bit >> 3;
        unsigned bit_off = s->bit & 7;
        uint8_t cur = (byte_idx < s->len) ? s->b[byte_idx] : 0;
        unsigned take = (unsigned) ( (8 - bit_off) < need ? (8 - bit_off) : need);
        uint8_t chunk = (cur << bit_off) >> (8 - take);
        out = (out << take) | chunk;
        s->bit += take;
        need -= take;
    }
    return out;
}

int parse_packet(const uint8_t *buf, size_t buf_len){
    if(buf_len < 8) return -1;
    uint64_t w0 = ntoh64(buf);
    bitstream s = { buf, buf_len, 0 };
    uint8_t magic = (uint8_t)bs_read(&s,8);
    uint8_t version = (uint8_t)bs_read(&s,4);
    uint8_t bitmap_words = (uint8_t)bs_read(&s,4);
    /* read remaining 48 bits of first bitmap word */
    uint64_t bitmap = bs_read(&s,48);
    for(unsigned i=0;i<bitmap_words;i++){
        uint64_t extra = bs_read(&s,64);
        bitmap = (bitmap << 64) | extra; /* for up to wide bitmaps; careful with sizes */
    }
    /* iterate fields: for each set bit, read according to schema; use popcount / scanning */
    for(unsigned fid=0; fid < 128; ++fid){
        int present = (bitmap >> (127 - fid)) & 1; /* MSB-first mapping */
        /* low-branch: multiply mask to zero-out absent reads */
        uint64_t len_prefix = 0;
        uint64_t value = 0;
        /* Example: fields 0..31 fixed 12 bits, fields 32..63 variable with 6-bit len */
        if(fid < 32){
            /* attempt to read 12 bits; if absent, shift bitstream by 0 (no-op) */
            uint64_t v = bs_read(&s, present ? 12 : 0);
            value = v;
        } else if (fid < 64){
            uint64_t l = present ? bs_read(&s,6) : 0;
            uint64_t v = present ? bs_read(&s,(unsigned)l) : 0;
            (void)l; value = v;
        } else break;
        /* handle value... */
    }
    /* After core fields, align to next 64-bit boundary: advance s->bit to ((s->bit+63)/64)*64 */
    s.bit = ((s.bit + 63) / 64) * 64;
    /* parse TLV extension area byte-aligned */
    size_t byte_pos = s.bit >> 3;
    while(byte_pos + 3 < buf_len){
        uint8_t t = buf[byte_pos];
        uint16_t l = (buf[byte_pos+1] << 8) | buf[byte_pos+2];
        /* safe skip if beyond buf */
        if(byte_pos + 3 + l > buf_len) break;
        const uint8_t *v = buf + byte_pos + 3;
        /* If unknown type, skip. If known, process. */
        byte_pos += 3 + l;
    }
    return 0;
}

Endian handling:- Wire big-endian. Use ntoh helpers for word-level conversion. Bitstream reads interpret MSB-first within bytes.

Versioning & backward compatibility:- version field (4 bits) allows schema changes. Parsers: if version > supported, they parse known subset (presence bitmap): unknown fields are skipped using length rules or TLV skip. Additions should prefer: - New optional fields assigned new bitmap indices. - If new parsing semantics needed, increment version; keep prior format unchanged. - Use TLV extension area for arbitrary future data; older parsers skip unknown TLVs cleanly.

Extensions & evolution:- Reserve a range of bitmap indices for experimental fields; if semantics change, deprecate bits and introduce new version.- Keep core mandatory fields stable. Prefer adding optional fields or TLVs rather than changing existing field sizes/positions.- If needing more fields than bitmap size, set bitmap_words >0 to extend presence map without breaking older parsers that interpret extra bitmap bits as zeros.

Trade-offs:- Very compact, fast 64-bit-aligned processing at cost of complex bit packing and a slightly larger parser. Low-branch bitstream reduces branching but requires careful bounds checking and testing.

Testing & safety:- Provide exhaustive fuzz tests, property tests for endian/bit-order, and backward-compat test vectors for each version.

Unlock Full Question Bank

Get access to hundreds of Bit Manipulation and Mathematics interview questions and detailed answers.

Join thousands of developers preparing for their dream job.