Bit Manipulation, Binary Arithmetic, and Low-Level Bit Tricks

Bit manipulation performs direct operations on individual binary digits (bits) at the register level. It operates in single CPU clock cycles with zero memory overhead, providing essential performance optimizations in cryptography, compression, networking protocols, graphics rendering, and dynamic programming state compression (bitmask DP).

⚡ Quick Dive

Bitwise Operators Reference

Operator Name Logic / Behavior Example (Binary)
& AND $1$ if both bits are $1$, else $0$ 1100 & 1010 = 1000
| OR $1$ if at least one bit is $1$ 1100 | 1010 = 1110
^ XOR $1$ if bits are different ($x \oplus x = 0, x \oplus 0 = x$) 1100 ^ 1010 = 0110
~ / ^ NOT Invert all bits ($0 \to 1, 1 \to 0$) ~00001010 = 11110101
<< Left Shift Shift bits left; multiply by $2^k$ 00000101 << 2 = 00010100 ($5 \cdot 4 = 20$)
>> Right Shift Shift bits right; integer divide by $2^k$ 00010100 >> 2 = 00000101 ($20 / 4 = 5$)

Essential Bit Tricks Cheat Sheet

Task Expression Why It Works
Check if Odd / Even (n & 1) == 1 Least Significant Bit is $1$ for odd numbers
Clear lowest set bit n & (n - 1) Flips the lowest $1$-bit and all trailing $0$s
Isolate lowest set bit n & (-n) In Two's complement, $-n = \sim n + 1$
Check Power of Two n > 0 && (n & (n - 1)) == 0 Powers of two have exactly one set bit
Set $k$-th bit n | (1 << k) Creates a mask with $1$ at position $k$
Clear $k$-th bit n & ~(1 << k) Creates a mask with $0$ at position $k$
Toggle $k$-th bit n ^ (1 << k) Inverts bit at position $k$
Test $k$-th bit (n & (1 << k)) != 0 Isolates bit at position $k$

📖 Extended Guide

1. Two's Complement Representation

Modern computers represent signed integers using Two's Complement:

  • Most Significant Bit (MSB) acts as the sign bit ($0$ = positive, $1$ = negative).
  • To negate a number: Invert all bits and add 1 ($-x = \sim x + 1$).
Example (8-bit integer):
   +5 = 00000101
~(+5) = 11111010 (Invert bits)
   -5 = 11111011 (Add 1)

This mathematical property allows the CPU ALU (Arithmetic Logic Unit) to perform subtraction using standard addition hardware circuitry without separate subtraction paths.

2. Brian Kernighan’s Algorithm (Counting Set Bits)

The naive bit counter loops 32 or 64 times. Brian Kernighan's algorithm runs in time proportional strictly to the number of set bits ($O(\text{count of 1s})$) by clearing the lowest set bit in each step:

package main

import "fmt"

func CountSetBits(n int) int {
	count := 0
	for n > 0 {
		n = n & (n - 1) // Clears the lowest set bit
		count++
	}
	return count
}

func main() {
	num := 29 // Binary: 11101 (four 1-bits)
	fmt.Printf("Number of set bits in %d: %d\n", num, CountSetBits(num)) // 4
}

3. The Power of XOR: Finding the Single Number

Problem: Given an array where every element appears twice except for one unique element, find the unique element in $O(n)$ time and $O(1)$ auxiliary memory.

Properties of XOR:

  1. $x \oplus x = 0$ (Self-inverse)
  2. $x \oplus 0 = x$ (Identity)
  3. $x \oplus y = y \oplus x$ (Commutative & Associative)
func SingleNumber(nums []int) int {
	result := 0
	for _, num := range nums {
		result ^= num // Duplicate pairs cancel out to 0
	}
	return result
}

4. Bitmasks for State Compression (Bitmask DP)

An integer can represent a boolean set of up to 64 items using its binary representation ($1$ = element present, $0$ = absent):

// Generate all 2^N subsets of a set
func Subsets(elements []string) [][]string {
	n := len(elements)
	totalSubsets := 1 << n // 2^n
	result := make([][]string, 0, totalSubsets)

	for mask := 0; mask < totalSubsets; mask++ {
		current := []string{}
		for i := 0; i < n; i++ {
			if (mask & (1 << i)) != 0 {
				current = append(current, elements[i])
			}
		}
		result = append(result, current)
	}

	return result
}
⌂ All Guides