Bit manipulation

When to reach for it

• Permissions, feature flags and capability sets stored compactly and combined quickly.
• Finding the value that appears an odd number of times, or the one missing from a range.
• Counting set bits, checking for a power of two, isolating the lowest set bit.
• Enumerating every subset of a small set (up to about 20 items) as a number from 0 to 2 to the n minus 1.

The core idea

Give each flag its own bit, 1 << k. Then mask | flag sets it, mask & ~flag clears it, and mask & flag tests it. Combining two sets is OR, their overlap is AND, and their difference is AND with the complement. Precedence rules, such as an explicit deny overriding an allow, become a fixed sequence of these operations.

A few identities do most of the work: x ^ x == 0 and x ^ 0 == x, so XOR-ing a list cancels every pair; x & (x - 1) clears the lowest set bit, so a power of two is a positive x where that gives 0; and x & -x isolates the lowest set bit.

A Python template

READ, WRITE, SHARE, ADMIN = (1 << k for k in range(4))

def grant(mask, flag):
    return mask | flag

def revoke(mask, flag):
    return mask & ~flag

def allows(mask, flag):
    return (mask & flag) == flag          # parentheses: see the mistakes below

def effective(role_masks, denied, allowed):
    """Union of the roles, minus explicit denies, plus explicit allows."""
    mask = 0
    for m in role_masks:
        mask |= m
    return (mask & ~denied) | allowed

def count_set_bits(x):
    count = 0
    while x:
        x &= x - 1                        # clears the lowest set bit
        count += 1
    return count

def all_subsets(items):
    n = len(items)
    return [[items[i] for i in range(n) if (mask >> i) & 1] for mask in range(1 << n)]

Time and space

Flag operations are O(1). Counting set bits by clearing the lowest one is O(number of set bits), at most the word size. Enumerating subsets is O(2 to the n times n) time, so it only suits small n, and it uses no recursion.

Common mistakes

• Precedence: in Java and C++, == binds tighter than &, so mask & flag == flag does not mean what it says. Python happens to parse it as intended, but parentheses make it unambiguous everywhere.
• Negative numbers: Python integers have no fixed width, so ~x and right shifts of negatives behave differently from 32-bit languages; mask to the width you need.
• Reusing a bit for two flags when adding a new capability.
• Applying deny and allow overrides in the wrong order.
• Using bit tricks where a set would be clearer and fast enough; say why the compact form matters.

How to explain it out loud

Say the representation first: "Each permission is one bit, so a role's permissions are one integer, and combining roles is a bitwise OR." Then spell out the order of overrides as plain steps before writing them as operators. The interviewer can check your logic in words far more easily than in symbols.

When you use an identity such as clearing the lowest set bit, say what it does and why, in one sentence, rather than presenting it as a trick. Mention negative numbers and precedence before you are asked; those are the follow-ups, and handling them is what Devana scores as code defense and edge cases.