DSA Bitwise

Bit Manipulation

Why is of a machine word effectively one while looping 64 booleans is not? Feature flags, set membership for n ≤ 64, and subset DP all ride that width.

Bit tricks are contracts on width, signedness, and shifts, not magic. A is a compact set; know before shifting negatives.

Decision journey

Fix width & signedness

32/64, Java int vs Python mask.

Choose the word op

Test, set, clear, toggle, isolate lowest one.

Submasks or all 2ⁿ masks.

Check overflow/shift

Distance modulo width; no silent wrap surprises.

What actually happens

Naive idea: arrays of booleans or nested loops over bit indices. Correct, and often slower and larger than a word-parallel mask.

Better idea: pack flags into an integer; update with AND/OR/XOR/shifts. Hardware applies the op across the word. Subset DP stores visited sets as masks.

The improved design still fails on Python negatives without masks, on Java arithmetic vs logical right shift, on shift distances ≥ width, and on claiming “faster” without measuring.

Invariant

Under the declared width, each bit position has a fixed meaning (element i present, flag i set). Operations must not redefine bits via overflow, sign extension, or an unbound Python shift unless you mask back to the contract.

How to choose bit tricks

1. n ≤ 64 sets/flags? Bitmasks are natural.

2. Need popcount/trailing zeros often? Prefer builtins over hand-rolled loops.

3. Cross-language? Write fixed-width helpers; do not assume Python matches Java int.

Quantitative check

All subsets of n elements: 2ⁿ. All mask/submask pairs: Θ(3ⁿ). For n = 20, 3²⁰ ≈ 3.4×10⁹ is usually too heavy; n = 16 is often the practical ceiling for dense subset DP without extra pruning.

Basic operators

AND (&)

1 AND 1 = 1, else 0

Used to check if a bit is set.

OR (|)

0 OR 0 = 0, else 1

Used to set a bit.

XOR (^)

Different = 1, same = 0

Properties: a^a=0, a^0=a.

NOT (~)

Invert all bits

Two's complement: ~x = -(x+1)

L-Shift (<<)

x << y ≈ x * 2ʸ when no fixed-width overflow

Shifts bits to the left.

R-Shift ( >> )

Signed right shift is language/width sensitive

Shifts bits to the right.

Interactive bitmask semantics

Fixed-width bitmask lab

Bits are a set over positions

value

13 · 0b00001101

lowest set bit

subset of 0b1101

13 · 0b1101

Subset iteration uses sub = (sub − 1) & mask; stop after processing zero or the sequence repeats.

🪄 Bitwise Hacks

Python

python

WIDTH = 32
MASK = (1 << WIDTH) - 1

def unsigned32(value):
    return value & MASK

def logical_right_shift32(value, distance):
    return unsigned32(value) >> (distance & 31)

def is_power_of_two(value):
    return value > 0 and (value & (value - 1)) == 0

def count_bits32(value):
    value &= MASK  # required for Python negative integers
    count = 0
    while value:
        value &= value - 1
        count += 1
    return count

def subsets(mask):
    if mask < 0:
        raise ValueError("set masks must be non-negative")
    sub = mask
    while True:
        yield sub
        if sub == 0:
            break
        sub = (sub - 1) & mask

assert logical_right_shift32(-1, 1) == 0x7fffffff
assert count_bits32(-1) == 32
assert list(subsets(0b101)) == [0b101, 0b100, 0b001, 0]

Java

java

import java.util.ArrayList;
import java.util.List;

public final class BitOperations {
    static boolean isPowerOfTwo(int value) {
        return value > 0 && (value & (value - 1)) == 0;
    }

    static List<Integer> subsets(int mask) {
        if (mask < 0) throw new IllegalArgumentException("set masks must be non-negative");
        List<Integer> result = new ArrayList<>();
        for (int sub = mask; ; sub = (sub - 1) & mask) {
            result.add(sub);
            if (sub == 0) break;
        }
        return List.copyOf(result);
    }

    public static void main(String[] args) {
        int value = -1;
        if ((value >> 1) != -1) throw new AssertionError();
        if ((value >>> 1) != 0x7fffffff) throw new AssertionError();
        if (Integer.bitCount(value) != 32) throw new AssertionError();
        if (Integer.lowestOneBit(12) != 4) throw new AssertionError();
        if (!subsets(0b101).equals(List.of(5, 4, 1, 0))) throw new AssertionError();
    }
}

Signed representation and shift semantics

Concept	Java `int`	Python `int`
Width	Exactly 32-bit two's complement	Arbitrary precision; negative bit operations behave like infinite sign extension
Right shift	`>>` arithmetic, `>>>` logical	`>>` arithmetic only; mask first to emulate fixed-width logical shift
Shift distance	For int, only low 5 bits are used	Negative distance errors; large left shifts grow the integer
Overflow	Wraps modulo 2³² for ordinary int arithmetic/shifts	No fixed-width overflow unless explicitly masked

Core identities with contracts

test bit i

(x & (1 << i)) != 0

set bit i

x | (1 << i)

clear bit i

x & ~(1 << i)

toggle bit i

x ^ (1 << i)

clear lowest one

x & (x − 1)

isolate lowest one

x & −x

Validate 0 ≤ i < width. Power-of-two checks require x > 0. XOR-swap obscures intent, breaks when both references alias, and is not faster than a temporary variable in optimized code.

Subset enumeration and bitmask DP

All masks

for mask in [0,2ⁿ): O(2ⁿ) states.

Submasks

sub=(sub−1)&mask enumerates exactly 2^popcount(mask) subsets.

All mask/submask pairs

Total Θ(3ⁿ): each element is absent, mask-only, or in submask.

Bitmask DP uses bits as a compact state, for example visited cities in Held–Karp TSP. Its speed comes from dense state encoding, not magic: memory is often O(2ⁿ·n), and shifts must use a wide enough type (1L << n in Java when appropriate).

Production and test checklist

• State width, signedness, and overflow/wrap semantics at the API boundary.
• Prefer named masks/constants and built-ins such as bitCount/numberOfTrailingZeros.
• Parenthesize mixed bitwise/comparison expressions; precedence is easy to misread.
• Do not claim bit tricks are faster without measurement; clarity often wins.

• Test zero, one, −1, MIN/MAX, highest bit, and shift distances 0, width−1, width, and negative.
• Compare fixed-width Python helpers against Java/unsigned reference behavior.
• Verify submask enumeration includes zero once and never loops afterward.
• Property-test identities under the intended width mask.

Exercises

In Java, compare (-1) >> 1 and (-1) >>> 1. What width contract does each assume?
Enumerate submasks of 0b1011 by hand. How many steps, and why does the loop include 0 once?
For n = 20, estimate 2ⁿ vs 3ⁿ mask/submask work. When would you still use bitmask DP?

Primary sources

Warren, H. S.: Hacker's Delight (bit twiddling identities and word-parallel methods).
Java Language Specification: integer shift distance and two's-complement width.
Python docs: bitwise operations on unlimited integers (masking for fixed width).

Takeaway

Bit manipulation is word-size algebra under an explicit width contract. Masks compress sets; shifts and signs are where proofs die.