18. Bit Manipulation

18.1 Binary Representation

Integers are stored internally as sequences of bits (0 or 1). Each bit position i corresponds to the power 2^i. Understanding this positional system is the foundation for all bit‑level operations.

Conversion Between Decimal and Binary

• Decimal → Binary: Repeatedly divide the number by 2 and record the remainders. The binary string is the remainders read in reverse order.
• Binary → Decimal: Compute the sum Σ (bit_i × 2^i) where bit_i is the i‑th bit (starting from 0 on the right).

Example: 13₁₀ = 1101₂ because 1·8 + 1·4 + 0·2 + 1·1 = 13.

Two’s Complement for Signed Numbers

To represent a negative value -x in an n-bit word:

1. Invert all bits of x (bitwise NOT).
2. Add 1 to the result.

This yields a representation where addition works identically for signed and unsigned numbers.

Value Ranges

18.2 Bitwise Operators

These operators work on each bit independently.

Truth Tables

Shift Operations

• Left Shift (x << k): Equivalent to x × 2^k. Zeros are shifted in from the right.
• Right Shift (x >> k):
  • Arithmetic shift (signed): preserves the sign bit, filling left with the original sign.
  • Logical shift (unsigned): fills left with zeros.

Examples (8‑bit view)

5  = 00000101
3  = 00000011
5 & 3 = 00000001 = 1
5 | 3 = 00000111 = 7
5 ^ 3 = 00000110 = 6
~5  = 11111010 = -6   (two’s complement)
5 << 2 = 00010100 = 20
5 >> 1 = 00000010 = 2   (arithmetic shift preserves sign)

18.3 Bit Masking

A mask is a bit pattern used to isolate, set, clear, or toggle specific bits.

Common Mask Patterns

• Isolate i‑th bit: mask = 1 << i; extracted value = x & mask.
• Set i‑th bit: x | (1 << i).
• Clear i‑th bit: x & ~(1 << i).
• Toggle i‑th bit: x ^ (1 << i).

Power‑of‑Two Test

For x > 0, x is a power of two iff (x & (x‑1)) == 0.

Population Count (Popcount)

Number of set bits can be computed with Kernighan’s algorithm:

count = 0;
while (x) {
    x &= x - 1;   // clear the lowest set bit
    count++;
}

Many compilers provide intrinsics: __builtin_popcount (GCC/Clang) or Integer.bitCount (Java).

Example: Extract Lower 4 Bits

Given 0b11010110, mask 0b1111 yields 0b0110 = 6.

18.4 XOR Tricks

The XOR operation has several algebraic properties that enable clever tricks.

Properties

• a ^ a = 0
• a ^ 0 = a
• a ^ b = b ^ a (commutative)
• (a ^ b) ^ a = b (self‑inverse)

Applications

1. Find the element occurring odd number of times:

   result = 0;
   for v in arr:
       result ^= v;
   // result is the odd‑occurrence element
   

2. Swap two variables without a temporary:

   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
   

3. Find missing number in range [0, n] given n numbers:

   xor_all = 0;
   for i in 0..n: xor_all ^= i;
   xor_arr = 0;
   for v in arr: xor_arr ^= v;
   missing = xor_all ^ xor_arr;
   

4. Gray code generation: g(i) = i ^ (i >> 1) produces a sequence where successive values differ by exactly one bit.

Example

Array [2,3,2,3,4] → XOR all = 2 ^ 3 ^ 2 ^ 3 ^ 4 = (2^2) ^ (3^3) ^ 4 = 0 ^ 0 ^ 4 = 4. The odd‑occurrence element is 4.

18.5 Applications

Bitwise techniques permeate many domains.

Cryptography

Stream ciphers (e.g., one‑time pad) encrypt by XORing the plaintext with a pseudo‑random key stream. Block cipher modes such as CFB and OFB also rely on XOR for diffusion.

Data Compression

Bit‑level writers/readers (used in Huffman coding, arithmetic coding) pack symbols into a bit stream using shifts and masks to avoid byte alignment waste.

Graphics

RGBA channels are often packed into a 32‑bit integer. Masking extracts R = (pixel >> 16) & 0xFF, G = (pixel >> 8) & 0xFF, B = pixel & 0xFF, A = (pixel >> 24) & 0xFF. Alpha blending and color transformations use bitwise ops for fast per‑pixel manipulation.

Networking

• IP address subnetting: network address = IP & subnet_mask.
• Checksum algorithms (e.g., Internet checksum) accumulate 16‑bit words using one’s complement addition, which can be expressed with bitwise operations.

Competitive Programming

• Submask enumeration: Iterate all submasks of a mask m:

  sub = m;
  while (sub) {
      // process(sub)
      sub = (sub - 1) & m;
  }
  process(0); // include empty submask
  

• DP on bitsets: Represent subsets as bits; transition via dp[mask | (1<<i)].
• Fast subset convolution: Uses SOS DP (Sum Over Subsets) with bitwise loops.

Summary

Mastering binary representation and bitwise operators equips you with a versatile toolkit for low‑level optimization, algorithmic tricks, and system‑level programming. The techniques discussed—masking, XOR‑based solutions, and efficient bit traversal—are indispensable in fields ranging from embedded systems to high‑performance competitive coding.