Bit Manipulation: Logic, Complements, and High-Performance Tricks

Binary Representation: Two's Complement

In Java (and most modern languages), signed integers are represented using 32-bit Two's Complement:

Key Identities:

• Negative representation: -n = ~n + 1.
• Lowbit: n & (-n) = n & (~n + 1). This isolates the lowest 1 bit.

The Sign Bit and Arithmetic Shifts

int n = -8;        // Binary: 1111...1000
int a = n >> 1;    // Arithmetic shift: 1111...1100 = -4 (Preserves sign)
int b = n >>> 1;   // Logical shift: 0111...1100 = LARGE POSITIVE (Pads with 0)

Real-world Application: Safe binary search midpoint.

// Prevents overflow in int calculations (left + right)
int mid1 = (left + right) >>> 1; // Correct even if (left + right) exceeds MAX_INT

No-Branch Selection (Bitwise instead of if)

In performance-sensitive code (SIMD/Game Engines), you can replace branching with bit-logic to avoid pipeline stalls.

// Select a or b based on condition 'cond' (0 or 1)
// If cond=1, mask=-1 (all 1s). If cond=0, mask=0.
int select(int cond, int a, int b) {
    int mask = -cond;
    return (a & mask) | (b & ~mask);
}

// Absolute value without Math.abs or if
int abs(int n) {
    int mask = n >> 31;      // 0 for positives, -1 for negatives
    return (n + mask) ^ mask; // Inverts negatives and adds 1
}

Lowbit and Binary Indexed Trees (Fenwick Trees)

The lowbit operation is the backbone of the BIT (Binary Indexed Tree), allowing $O(\log N)$ prefix sum queries and point updates.

public int lowbit(int x) {
    return x & (-x);
}

// update(i, delta): i += lowbit(i) moves up the tree
// query(i): i -= lowbit(i) moves down the tree to aggregate sums

Common Bitwise Pitfalls

1. Operator Precedence

The & | ^ operators have lower priority than equality == and relational operators. Always use parentheses.

if ((n & 1) == 0) { ... } // Correct
if (n & 1 == 0) { ... }   // BUG: equivalent to n & (1 == 0)

2. Shift Overflow

In Java, shifting an int by 32 results in no shift at all because the shift amount is computed modulo 32.

int x = 1 << 32; // Equivalent to 1 << 0 = 1

3. Signed Bytes

A signed byte 0xFF in Java is -1. To get the unsigned value $255$:

int value = b & 0xFF; // Promotes to int then masks to lower 8 bits

Engineering Proficiency Checklist

Conclusion: The First Principles of Bits

1. Two's Complement unifies addition across positive and negative domains.
2. XOR is addition without carrying; AND identifies carries.
3. n & (n-1) is the standard tool for counting bits $O(K)$.
4. n & (-n) is the entry point for BIT/Fenwick trees.
5. Masks turn an integer into an efficient, indexed boolean set.
6. State Compression is the bridge between combinatorial problems and efficient DP. 筋