Common Integer Operations and… — Integer Data Types | OneNoughtOne

0/86

Data Structures & AlgorithmsInteger Data Types

Integer Data Types

LevelBeginner

Duration75 mins

TopicInteger Data Types

4 / 5

Common Integer Operations and Their Cost Model

The Foundation of Algorithmic Cost

When we analyze algorithms and say something takes "O(n) time," what are we actually counting? At the lowest level, algorithms execute primitive operations —additions, comparisons, memory accesses. Understanding the cost of these operations is fundamental to accurate algorithm analysis. But here's a question that should trouble you: is addition really O(1)? What about multiplication? Division? These operations involve different amounts of work at the hardware level. Why do we treat them as constant-time? This page connects integer operations to the RAM (Random Access Machine) model —the theoretical framework underlying most algorithm analysis. You'll learn not just what operations cost, but why we model costs the way we do, and when that model breaks down.

What You Will Learn

By the end of this page, you will understand: (1) The RAM model and its assumptions, (2) Costs of basic integer operations (add, subtract, multiply, divide), (3) Costs of bit manipulation operations, (4) Costs of comparison and branching, (5) When the constant-time assumption fails, and (6) How to reason about operation costs in algorithm design.

The RAM Model: Our Theoretical Framework

Algorithm analysis typically uses the Random Access Machine (RAM) model, a simplified abstraction of how computers work. Understanding this model helps you know when standard complexity analysis applies and when it doesn't. Key assumptions of the RAM model: Unlimited memory: You can store an arbitrary amount of data. Constant-time memory access: Accessing any memory location takes the same time, regardless of its address. This is the "Random Access" part. Fixed-width words: All data fits in a constant-size machine word (typically O(log n) bits for a problem of size n). Constant-time primitive operations: Each arithmetic operation (+, -, \times, \div), comparison, and memory access takes O(1) time. Sequential execution: Operations execute one at a time (ignoring parallelism).

RAM Model Operations and Their Assumed Costs
Operation Category	Examples	Assumed Cost
Arithmetic	Addition, subtraction, multiplication, division	O(1)
Comparison	Less than, equal, greater than	O(1)
Bitwise	AND, OR, XOR, NOT, shifts	O(1)
Memory read	Load from any address	O(1)
Memory write	Store to any address	O(1)
Assignment	x = y	O(1)

Why this approximation works: The RAM model is a simplification, but it works remarkably well for most algorithms because: Proportionality matters, not absolutes: We care whether an algorithm is O(n) vs O(n²), not whether one operation takes 3 vs 5 nanoseconds. Operations scale together: On real CPUs, all primitive operations take roughly the same order of magnitude of time (nanoseconds). Larger effects dominate: The difference between comparing 1000 vs 1,000,000 elements matters far more than micro-optimizing individual operations. When the model becomes inaccurate: The RAM model's assumptions fail in specific situations: Cache effects: Memory access is NOT constant-time in practice; cache hits are ~100x faster than cache misses Big integers: Arbitrary-precision arithmetic is O(n) or worse, not O(1) Parallelism: Modern CPUs execute multiple operations simultaneously Branch prediction: Conditional branches have variable costs

The Word RAM Model

A more precise model is the Word RAM model, which explicitly assumes word size w = O(log n) bits for problems of size n. This is needed because if we allowed arbitrarily large words, we could cheat by encoding entire algorithms into single numbers. The O(log n) word size matches reality: 32-bit for billions of items, 64-bit for quintillions.

Arithmetic Operations: Addition, Subtraction, Multiplication, Division

Let's examine the actual hardware costs of fundamental arithmetic operations. While we treat them as O(1) in algorithm analysis, understanding their relative costs informs practical optimization.

Typical Latency of Integer Operations on Modern CPUs
Operation	Latency (cycles)	Throughput (per cycle)	Notes
Addition	1	4	Fastest; multiple adders in parallel
Subtraction	1	4	Same as addition
Multiplication (32-bit)	3-4	1	Slower but pipelined
Multiplication (64-bit)	3-5	1	Slightly slower than 32-bit
Division (32-bit)	20-30	1/10 - 1/20	Much slower; not pipelined
Division (64-bit)	30-50	1/20 - 1/30	Slowest arithmetic operation
Modulo (%)	Same as division	Same as division	Computed alongside quotient

Key observations: 1. Addition/Subtraction are lightning fast: Modern CPUs can execute multiple additions per cycle. The adder circuit is among the most optimized components. If your inner loop only does additions and comparisons, it can be extraordinarily fast. 2. Multiplication is reasonably fast: Despite being mathematically more complex, dedicated multiplier circuits make multiplication only 3-5x slower than addition in latency. Throughput is lower because there are fewer multiplier units. 3. Division is expensive: Division is 20-50x slower than addition. This dramatic difference arises because division requires iterative approximation (similar to long division). There's no efficient parallel circuit for division. 4. Modulo shares division's cost: The % operator requires performing a division. When you write x % 10, the CPU divides x by 10 and gives you the remainder. This is why modulo is expensive.

Optimization: Avoid Division in Hot Loops

In performance-critical code, replacing division with multiplication by the inverse (precomputed) or using bit shifts (for powers of two) can yield significant speedups. x / 8 can be replaced with x >> 3 for unsigned integers. Modern compilers often do this automatically, but understanding the principle helps you avoid anti-patterns.

division_optimization.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdint.h>
 
// SLOW: Division in a loop
uint32_t count_multiples_slow(const uint32_t* arr, size_t n, uint32_t divisor) {
    uint32_t count = 0;
    for (size_t i = 0; i < n; i++) {
        if (arr[i] % divisor == 0) {  // Division every iteration!
            count++;
        }
    }
    return count;
}
 
// FAST: For power-of-2 divisors, use bit masking
uint32_t count_multiples_pow2(const uint32_t* arr, size_t n, uint32_t power_of_2) {
    uint32_t count = 0;
    uint32_t mask = power_of_2 - 1;  // e.g., 8-1 = 7 = 0b111
    for (size_t i = 0; i < n; i++) {
        if ((arr[i] & mask) == 0) {  // Fast bit operation!
            count++;
        }
    }
    return count;
}
 
// FAST: For arbitrary divisors, use multiplication by magic constant
// Compilers often do this transformation automatically
// x / d ≈ (x * magic_number) >> shift
// The magic number and shift are precomputed based on divisor
 
// Example: Checking if a number is a multiple of a known constant
int is_multiple_of_3(uint32_t x) {
    // Compiler will optimize x % 3 == 0 using this technique
    return x % 3 == 0;
}

Comparison Operations and Branching

Comparison operations (<, >, ==, <=, >=,!=) are fundamental to control flow. While individually O(1), their interaction with branch prediction affects real-world performance.

How comparison works at the hardware level: A comparison is essentially a subtraction where we discard the result but keep the flags :; Compare x and y (x86 assembly) cmp eax, ebx ; Subtracts ebx from eax, sets flags, discards result jl smaller ; Jump if Less (signed) jg greater ; Jump if Greater (signed) The comparison sets CPU flags (zero, negative, overflow, carry), and a conditional jump checks these flags. Comparison cost: O(1) with a caveat: The comparison instruction itself is O(1) and fast. However, the conditional branch that follows introduces unpredictability.

Branch Prediction and Its Impact

•Pipeline stages: Modern CPUs have deep pipelines (15-20 stages). The CPU starts executing the next instruction before knowing if the branch is taken.
•Branch prediction: The CPU predicts which way the branch will go and speculatively executes that path.
•Prediction hit: If correct, no penalty—full speed ahead.
•Prediction miss: If wrong, the CPU must flush the pipeline and restart from the correct path—a penalty of 10-20 cycles.
•Predictable patterns are fast: Branches that are almost always true (or always false) are predicted correctly.
•Random patterns are slow: Branches with 50/50 probability cause frequent mispredictions.

branch_prediction.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define SIZE 100000
 
// This function will run SLOWER with random data than sorted data
// due to branch mispredictions
long sum_positive_branched(const int* arr, size_t n) {
    long sum = 0;
    for (size_t i = 0; i < n; i++) {
        if (arr[i] > 0) {  // Branch: Prediction depends on data pattern
            sum += arr[i];
        }
    }
    return sum;
}
 
// Branchless alternative using conditional move
// Runs at consistent speed regardless of data pattern
long sum_positive_branchless(const int* arr, size_t n) {
    long sum = 0;
    for (size_t i = 0; i < n; i++) {
        // (arr[i] > 0) converts to 0 or 1
        // When 0, adds 0; when 1, adds arr[i]
        int mask = -(arr[i] > 0);  // All 0s or all 1s
        sum += arr[i] & mask;
    }
    return sum;
}
 
int main() {
    int* sorted = malloc(SIZE * sizeof(int));
    int* random_arr = malloc(SIZE * sizeof(int));
    
    // Initialize: sorted = {-N/2, ..., 0, ..., N/2}
    // random = random shuffle of the same
    for (int i = 0; i < SIZE; i++) {
        sorted[i] = i - SIZE/2;
        random_arr[i] = i - SIZE/2;
    }
    
    // Shuffle random array
    srand(42);
    for (int i = SIZE - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = random_arr[i];
        random_arr[i] = random_arr[j];
        random_arr[j] = temp;
    }
    
    // Sorted data: branch predictor learns the pattern
    // First half: always NOT taken, second half: always taken
    
    // Random data: branch predictor can't learn; 50% misprediction
    
    printf("Sorted result: %ld
", sum_positive_branched(sorted, SIZE));
    printf("Random result: %ld
", sum_positive_branched(random_arr, SIZE));
    
    free(sorted);
    free(random_arr);
    return 0;
}

Algorithm Analysis vs Reality

Standard algorithm analysis counts both branches as O(1). In practice, unpredictable branches can be 10x slower than predictable ones. This is why sorted data sometimes processes faster than random data, even when the algorithm's theoretical complexity is identical.

Bit Manipulation Operations

Bit manipulation operations (&, |,^, ~, <<, >>) are among the fastest operations a CPU can perform. Understanding them enables powerful optimizations.

Bit Manipulation Operations and Typical Uses
Operation	Symbol	Use Cases	Cost (cycles)
AND	&	Masking, checking bits, clearing bits	1
OR	\|	Setting bits, combining flags	1
XOR	^	Toggling bits, swapping without temp, checksums	1
NOT	~	Bitwise complement, inverting masks	1
Left shift	<<	Multiplication by power of 2, bit insertion	1
Right shift (logical)	or >>	Division by power of 2 (unsigned), bit extraction	1
Right shift (arithmetic)		Division by power of 2 (signed)	1

Why bit operations are so fast: Single-cycle execution: Each bit operation completes in one clock cycle. Massive parallelism: A 64-bit AND performs 64 independent AND operations simultaneously—essentially O(1) for 64 parallel operations. No carry propagation: Unlike addition, bit operations don't need to propagate carries between bit positions. Simple circuits: The hardware for AND, OR, XOR is simpler than for addition. Common bit manipulation idioms:

bit_tricks.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdint.h>
#include <stdbool.h>
 
// Check if nth bit is set
bool is_bit_set(uint32_t value, int n) {
    return (value & (1u << n)) != 0;
}
 
// Set nth bit
uint32_t set_bit(uint32_t value, int n) {
    return value | (1u << n);
}
 
// Clear nth bit
uint32_t clear_bit(uint32_t value, int n) {
    return value & ~(1u << n);
}
 
// Toggle nth bit
uint32_t toggle_bit(uint32_t value, int n) {
    return value ^ (1u << n);
}
 
// Check if power of 2 (fast!)
bool is_power_of_2(uint32_t n) {
    return n && !(n & (n - 1));
    // e.g., 8 = 1000, 7 = 0111, 8 & 7 = 0
}
 
// Round up to next power of 2
uint32_t next_power_of_2(uint32_t n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;
}
 
// Count set bits (population count)
int popcount_naive(uint32_t n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Count set bits - Brian Kernighan's algorithm (faster)
int popcount_kernighan(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // Clear lowest set bit
        count++;
    }
    return count;
}
 
// Modern CPUs have a single instruction: __builtin_popcount(n)
 
// Swap without temporary variable (XOR trick)
void swap_xor(int* a, int* b) {
    if (a != b) {  // Important: fails if a and b point to same location
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}
 
// Compute absolute value without branching (for 32-bit int)
int32_t abs_branchless(int32_t x) {
    int32_t mask = x >> 31;  // All 0s if positive, all 1s if negative
    return (x ^ mask) - mask;
}

Modern CPU Instructions

Modern CPUs include specialized bit manipulation instructions: popcnt (population count), lzcnt (leading zero count), tzcnt (trailing zero count), pdep / pext (parallel bit deposit/extract). These single instructions replace multi-cycle loops, providing O(1) complexity for operations that would otherwise be O(log n) or O(n).

Memory Access: The Hidden Cost

The RAM model assumes memory access is O(1). This is a crucial simplification that enables algorithm analysis but hides significant real-world performance differences.

Memory Hierarchy Access Latency
Level	Typical Size	Latency (cycles)	Latency (nanoseconds)
Registers	~100 bytes	0	< 1 ns
L1 Cache	32-64 KB	3-4	~1 ns
L2 Cache	256 KB - 1 MB	10-12	~3-4 ns
L3 Cache	4-32 MB	30-50	~10-15 ns
Main Memory (RAM)	GB	100-300	~50-100 ns
SSD	GB-TB	10,000-100,000	~10-100 μs
HDD	TB	1,000,000+	~5-10 ms

The staggering gap: A cache miss to main memory is 100-300 cycles—the same CPU could have executed 100-300 additions! This means: $$\text{1 cache miss} \approx \text{100 arithmetic operations}$$ Why this matters for algorithms: Locality is king: Algorithms that access memory sequentially (arrays) outperform those that jump around (linked lists), even if they do the same number of operations. Cache-oblivious algorithms: Some algorithms are designed to minimize cache misses without knowing the cache size. Big-O can be misleading: An O(n) algorithm with poor cache behavior can be slower than an O(n log n) algorithm with good cache behavior for reasonable n.

Cache-Friendly Patterns

•Sequential array access
•Processing data in chunks that fit in cache
•Struct of Arrays (SoA) for SIMD
•Loop tiling / blocking
•Data structure choices that minimize pointer chasing

Cache-Hostile Patterns

•Random access across large arrays
•Linked list traversal (pointer chasing)
•Column-major access of row-major arrays
•Hash table with poor locality
•Excessive indirection (pointers to pointers)

The 90% Rule

For most programs, 90% of execution time is spent in 10% of the code. Outside hot loops, cache behavior rarely matters. But in hot loops processing large data, cache optimization can yield 10x or greater speedups—often more impactful than algorithmic improvements.

When O(1) Fails: Big Integer Arithmetic

The O(1) cost for integer operations assumes numbers fit in fixed-width types. When working with arbitrary-precision integers (big integers), this assumption breaks. Big integer operation costs: For numbers with d digits:

Operation	Naive Cost	Optimized Cost
Addition/Subtraction	O(d)	O(d)
Multiplication	O(d²)	O(d^1.58) Karatsuba, O(d log d) FFT
Division	O(d²)	O(d log d) Newton-Raphson
Modular exponentiation	O(d² × e)	O(d² × log e)

When big integers appear: Cryptography: RSA typically uses 2048-bit or 4096-bit integers. These are 600-1200 decimal digits! Financial calculations: Some financial systems use arbitrary-precision to avoid floating-point errors. Competitive programming: Some problems require numbers larger than 64-bit. Exact arithmetic: Scientific computing sometimes needs exact rationals.

big_integer_complexity.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import time
 
def measure_addition(bits):
    """Measure time for big integer addition"""
    a = 2**bits - 1  # All 1s in binary
    b = 2**bits - 1
    
    start = time.perf_counter()
    for _ in range(10000):
        c = a + b
    end = time.perf_counter()
    
    return (end - start) / 10000
 
def measure_multiplication(bits):
    """Measure time for big integer multiplication"""
    a = 2**bits - 1
    b = 2**bits - 1
    
    start = time.perf_counter()
    for _ in range(1000):
        c = a * b
    end = time.perf_counter()
    
    return (end - start) / 1000
 
# Demonstrate that big integer operations scale with size
print("Big Integer Addition (scales linearly with bits):")
for bits in [64, 256, 1024, 4096, 16384]:
    t = measure_addition(bits)
    print(f"  {bits:5d} bits: {t*1e9:8.1f} ns")
 
print("
Big Integer Multiplication (scales super-linearly):")
for bits in [64, 256, 1024, 4096, 16384]:
    t = measure_multiplication(bits)
    print(f"  {bits:5d} bits: {t*1e6:8.3f} μs")
 
# RSA-2048 multiplication (real-world crypto)
print("
RSA-2048 single multiplication:")
t = measure_multiplication(2048)
print(f"  {t*1e6:.3f} μs")
print(f"  ~{int(t*1e9/0.3)} additions could be done in the same time!")

Accidental Big Integers

In Python, integers automatically promote to arbitrary precision. This can cause accidental quadratic behavior: if you compute 2**n repeatedly in a loop, performance degrades as n grows. Similarly, factorial(10000) involves thousands of big integer multiplications. Always be aware of number sizes in interpreted languages.

Practical Cost Comparison: Operation Benchmarks

To ground our theoretical understanding in reality, let's examine actual benchmark data for integer operations on a modern CPU.

Approximate Operation Throughput (Modern x86-64)
Operation	Throughput (billion ops/sec)	Relative Speed
64-bit addition	10-15	1.0x (baseline)
64-bit subtraction	10-15	1.0x
64-bit bitwise AND/OR/XOR	10-15	1.0x
64-bit left/right shift	10-15	1.0x
64-bit multiplication	2-4	0.25x
32-bit division	0.05-0.1	0.005x
64-bit division	0.03-0.05	0.003x
Branch (predicted)	10+	~1.0x
Branch (mispredicted)	0.2-0.5	0.02x
L1 cache access	10-15	~1.0x
L2 cache access	3-5	0.3x
L3 cache access	1-2	0.1x
RAM access	0.05-0.1	0.005x

Key insights from benchmarks: Division is 100-300x slower than addition. If your algorithm is division-heavy, consider restructuring. Mispredicted branches are 50x slower than predicted branches. Sorting data or using branchless code can be transformative. RAM access is 100-300x slower than L1 cache. Data locality often matters more than algorithmic cleverness. Addition, subtraction, bitwise, and shifts are effectively "free" in comparison to division and cache misses. Implications for algorithm design: Replace division with multiplication where possible (multiply by reciprocal) Use branchless techniques for unpredictable conditions Optimize data layout for cache efficiency Treat all basic arithmetic except division as roughly equal cost

The Modern Optimization Hierarchy

In rough order of impact: (1) Algorithmic complexity, (2) Data locality/cache efficiency, (3) Branch predictability, (4) SIMD/parallelism, (5) Avoiding division, (6) Micro-optimizations. Most programs only need to care about #1 and #2. Only hot paths justify #3-6.

Data Structures & AlgorithmsInteger Data Types

Integer Data Types

LevelBeginner

Duration75 mins

TopicInteger Data Types

4 / 5

Common Integer Operations and Their Cost Model

The Foundation of Algorithmic Cost

When we analyze algorithms and say something takes "O(n) time," what are we actually counting? At the lowest level, algorithms execute primitive operations —additions, comparisons, memory accesses. Understanding the cost of these operations is fundamental to accurate algorithm analysis. But here's a question that should trouble you: is addition really O(1)? What about multiplication? Division? These operations involve different amounts of work at the hardware level. Why do we treat them as constant-time? This page connects integer operations to the RAM (Random Access Machine) model —the theoretical framework underlying most algorithm analysis. You'll learn not just what operations cost, but why we model costs the way we do, and when that model breaks down.

What You Will Learn

By the end of this page, you will understand: (1) The RAM model and its assumptions, (2) Costs of basic integer operations (add, subtract, multiply, divide), (3) Costs of bit manipulation operations, (4) Costs of comparison and branching, (5) When the constant-time assumption fails, and (6) How to reason about operation costs in algorithm design.

The RAM Model: Our Theoretical Framework

Algorithm analysis typically uses the Random Access Machine (RAM) model, a simplified abstraction of how computers work. Understanding this model helps you know when standard complexity analysis applies and when it doesn't. Key assumptions of the RAM model: Unlimited memory: You can store an arbitrary amount of data. Constant-time memory access: Accessing any memory location takes the same time, regardless of its address. This is the "Random Access" part. Fixed-width words: All data fits in a constant-size machine word (typically O(log n) bits for a problem of size n). Constant-time primitive operations: Each arithmetic operation (+, -, \times, \div), comparison, and memory access takes O(1) time. Sequential execution: Operations execute one at a time (ignoring parallelism).

RAM Model Operations and Their Assumed Costs
Operation Category	Examples	Assumed Cost
Arithmetic	Addition, subtraction, multiplication, division	O(1)
Comparison	Less than, equal, greater than	O(1)
Bitwise	AND, OR, XOR, NOT, shifts	O(1)
Memory read	Load from any address	O(1)
Memory write	Store to any address	O(1)
Assignment	x = y	O(1)

Why this approximation works: The RAM model is a simplification, but it works remarkably well for most algorithms because: Proportionality matters, not absolutes: We care whether an algorithm is O(n) vs O(n²), not whether one operation takes 3 vs 5 nanoseconds. Operations scale together: On real CPUs, all primitive operations take roughly the same order of magnitude of time (nanoseconds). Larger effects dominate: The difference between comparing 1000 vs 1,000,000 elements matters far more than micro-optimizing individual operations. When the model becomes inaccurate: The RAM model's assumptions fail in specific situations: Cache effects: Memory access is NOT constant-time in practice; cache hits are ~100x faster than cache misses Big integers: Arbitrary-precision arithmetic is O(n) or worse, not O(1) Parallelism: Modern CPUs execute multiple operations simultaneously Branch prediction: Conditional branches have variable costs

The Word RAM Model

A more precise model is the Word RAM model, which explicitly assumes word size w = O(log n) bits for problems of size n. This is needed because if we allowed arbitrarily large words, we could cheat by encoding entire algorithms into single numbers. The O(log n) word size matches reality: 32-bit for billions of items, 64-bit for quintillions.

Arithmetic Operations: Addition, Subtraction, Multiplication, Division

Let's examine the actual hardware costs of fundamental arithmetic operations. While we treat them as O(1) in algorithm analysis, understanding their relative costs informs practical optimization.

Typical Latency of Integer Operations on Modern CPUs
Operation	Latency (cycles)	Throughput (per cycle)	Notes
Addition	1	4	Fastest; multiple adders in parallel
Subtraction	1	4	Same as addition
Multiplication (32-bit)	3-4	1	Slower but pipelined
Multiplication (64-bit)	3-5	1	Slightly slower than 32-bit
Division (32-bit)	20-30	1/10 - 1/20	Much slower; not pipelined
Division (64-bit)	30-50	1/20 - 1/30	Slowest arithmetic operation
Modulo (%)	Same as division	Same as division	Computed alongside quotient

Key observations: 1. Addition/Subtraction are lightning fast: Modern CPUs can execute multiple additions per cycle. The adder circuit is among the most optimized components. If your inner loop only does additions and comparisons, it can be extraordinarily fast. 2. Multiplication is reasonably fast: Despite being mathematically more complex, dedicated multiplier circuits make multiplication only 3-5x slower than addition in latency. Throughput is lower because there are fewer multiplier units. 3. Division is expensive: Division is 20-50x slower than addition. This dramatic difference arises because division requires iterative approximation (similar to long division). There's no efficient parallel circuit for division. 4. Modulo shares division's cost: The % operator requires performing a division. When you write x % 10, the CPU divides x by 10 and gives you the remainder. This is why modulo is expensive.

Optimization: Avoid Division in Hot Loops

In performance-critical code, replacing division with multiplication by the inverse (precomputed) or using bit shifts (for powers of two) can yield significant speedups. x / 8 can be replaced with x >> 3 for unsigned integers. Modern compilers often do this automatically, but understanding the principle helps you avoid anti-patterns.

division_optimization.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdint.h>
 
// SLOW: Division in a loop
uint32_t count_multiples_slow(const uint32_t* arr, size_t n, uint32_t divisor) {
    uint32_t count = 0;
    for (size_t i = 0; i < n; i++) {
        if (arr[i] % divisor == 0) {  // Division every iteration!
            count++;
        }
    }
    return count;
}
 
// FAST: For power-of-2 divisors, use bit masking
uint32_t count_multiples_pow2(const uint32_t* arr, size_t n, uint32_t power_of_2) {
    uint32_t count = 0;
    uint32_t mask = power_of_2 - 1;  // e.g., 8-1 = 7 = 0b111
    for (size_t i = 0; i < n; i++) {
        if ((arr[i] & mask) == 0) {  // Fast bit operation!
            count++;
        }
    }
    return count;
}
 
// FAST: For arbitrary divisors, use multiplication by magic constant
// Compilers often do this transformation automatically
// x / d ≈ (x * magic_number) >> shift
// The magic number and shift are precomputed based on divisor
 
// Example: Checking if a number is a multiple of a known constant
int is_multiple_of_3(uint32_t x) {
    // Compiler will optimize x % 3 == 0 using this technique
    return x % 3 == 0;
}

Comparison Operations and Branching

Comparison operations (<, >, ==, <=, >=,!=) are fundamental to control flow. While individually O(1), their interaction with branch prediction affects real-world performance.

How comparison works at the hardware level: A comparison is essentially a subtraction where we discard the result but keep the flags :; Compare x and y (x86 assembly) cmp eax, ebx ; Subtracts ebx from eax, sets flags, discards result jl smaller ; Jump if Less (signed) jg greater ; Jump if Greater (signed) The comparison sets CPU flags (zero, negative, overflow, carry), and a conditional jump checks these flags. Comparison cost: O(1) with a caveat: The comparison instruction itself is O(1) and fast. However, the conditional branch that follows introduces unpredictability.

Branch Prediction and Its Impact

•Pipeline stages: Modern CPUs have deep pipelines (15-20 stages). The CPU starts executing the next instruction before knowing if the branch is taken.
•Branch prediction: The CPU predicts which way the branch will go and speculatively executes that path.
•Prediction hit: If correct, no penalty—full speed ahead.
•Prediction miss: If wrong, the CPU must flush the pipeline and restart from the correct path—a penalty of 10-20 cycles.
•Predictable patterns are fast: Branches that are almost always true (or always false) are predicted correctly.
•Random patterns are slow: Branches with 50/50 probability cause frequent mispredictions.

branch_prediction.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define SIZE 100000
 
// This function will run SLOWER with random data than sorted data
// due to branch mispredictions
long sum_positive_branched(const int* arr, size_t n) {
    long sum = 0;
    for (size_t i = 0; i < n; i++) {
        if (arr[i] > 0) {  // Branch: Prediction depends on data pattern
            sum += arr[i];
        }
    }
    return sum;
}
 
// Branchless alternative using conditional move
// Runs at consistent speed regardless of data pattern
long sum_positive_branchless(const int* arr, size_t n) {
    long sum = 0;
    for (size_t i = 0; i < n; i++) {
        // (arr[i] > 0) converts to 0 or 1
        // When 0, adds 0; when 1, adds arr[i]
        int mask = -(arr[i] > 0);  // All 0s or all 1s
        sum += arr[i] & mask;
    }
    return sum;
}
 
int main() {
    int* sorted = malloc(SIZE * sizeof(int));
    int* random_arr = malloc(SIZE * sizeof(int));
    
    // Initialize: sorted = {-N/2, ..., 0, ..., N/2}
    // random = random shuffle of the same
    for (int i = 0; i < SIZE; i++) {
        sorted[i] = i - SIZE/2;
        random_arr[i] = i - SIZE/2;
    }
    
    // Shuffle random array
    srand(42);
    for (int i = SIZE - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = random_arr[i];
        random_arr[i] = random_arr[j];
        random_arr[j] = temp;
    }
    
    // Sorted data: branch predictor learns the pattern
    // First half: always NOT taken, second half: always taken
    
    // Random data: branch predictor can't learn; 50% misprediction
    
    printf("Sorted result: %ld
", sum_positive_branched(sorted, SIZE));
    printf("Random result: %ld
", sum_positive_branched(random_arr, SIZE));
    
    free(sorted);
    free(random_arr);
    return 0;
}

Algorithm Analysis vs Reality

Standard algorithm analysis counts both branches as O(1). In practice, unpredictable branches can be 10x slower than predictable ones. This is why sorted data sometimes processes faster than random data, even when the algorithm's theoretical complexity is identical.

Bit Manipulation Operations

Bit manipulation operations (&, |,^, ~, <<, >>) are among the fastest operations a CPU can perform. Understanding them enables powerful optimizations.

Bit Manipulation Operations and Typical Uses
Operation	Symbol	Use Cases	Cost (cycles)
AND	&	Masking, checking bits, clearing bits	1
OR	\|	Setting bits, combining flags	1
XOR	^	Toggling bits, swapping without temp, checksums	1
NOT	~	Bitwise complement, inverting masks	1
Left shift	<<	Multiplication by power of 2, bit insertion	1
Right shift (logical)	or >>	Division by power of 2 (unsigned), bit extraction	1
Right shift (arithmetic)		Division by power of 2 (signed)	1

Why bit operations are so fast: Single-cycle execution: Each bit operation completes in one clock cycle. Massive parallelism: A 64-bit AND performs 64 independent AND operations simultaneously—essentially O(1) for 64 parallel operations. No carry propagation: Unlike addition, bit operations don't need to propagate carries between bit positions. Simple circuits: The hardware for AND, OR, XOR is simpler than for addition. Common bit manipulation idioms:

bit_tricks.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdint.h>
#include <stdbool.h>
 
// Check if nth bit is set
bool is_bit_set(uint32_t value, int n) {
    return (value & (1u << n)) != 0;
}
 
// Set nth bit
uint32_t set_bit(uint32_t value, int n) {
    return value | (1u << n);
}
 
// Clear nth bit
uint32_t clear_bit(uint32_t value, int n) {
    return value & ~(1u << n);
}
 
// Toggle nth bit
uint32_t toggle_bit(uint32_t value, int n) {
    return value ^ (1u << n);
}
 
// Check if power of 2 (fast!)
bool is_power_of_2(uint32_t n) {
    return n && !(n & (n - 1));
    // e.g., 8 = 1000, 7 = 0111, 8 & 7 = 0
}
 
// Round up to next power of 2
uint32_t next_power_of_2(uint32_t n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;
}
 
// Count set bits (population count)
int popcount_naive(uint32_t n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Count set bits - Brian Kernighan's algorithm (faster)
int popcount_kernighan(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // Clear lowest set bit
        count++;
    }
    return count;
}
 
// Modern CPUs have a single instruction: __builtin_popcount(n)
 
// Swap without temporary variable (XOR trick)
void swap_xor(int* a, int* b) {
    if (a != b) {  // Important: fails if a and b point to same location
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}
 
// Compute absolute value without branching (for 32-bit int)
int32_t abs_branchless(int32_t x) {
    int32_t mask = x >> 31;  // All 0s if positive, all 1s if negative
    return (x ^ mask) - mask;
}

Modern CPU Instructions

Modern CPUs include specialized bit manipulation instructions: popcnt (population count), lzcnt (leading zero count), tzcnt (trailing zero count), pdep / pext (parallel bit deposit/extract). These single instructions replace multi-cycle loops, providing O(1) complexity for operations that would otherwise be O(log n) or O(n).

Memory Access: The Hidden Cost

The RAM model assumes memory access is O(1). This is a crucial simplification that enables algorithm analysis but hides significant real-world performance differences.

Memory Hierarchy Access Latency
Level	Typical Size	Latency (cycles)	Latency (nanoseconds)
Registers	~100 bytes	0	< 1 ns
L1 Cache	32-64 KB	3-4	~1 ns
L2 Cache	256 KB - 1 MB	10-12	~3-4 ns
L3 Cache	4-32 MB	30-50	~10-15 ns
Main Memory (RAM)	GB	100-300	~50-100 ns
SSD	GB-TB	10,000-100,000	~10-100 μs
HDD	TB	1,000,000+	~5-10 ms

The staggering gap: A cache miss to main memory is 100-300 cycles—the same CPU could have executed 100-300 additions! This means: $$\text{1 cache miss} \approx \text{100 arithmetic operations}$$ Why this matters for algorithms: Locality is king: Algorithms that access memory sequentially (arrays) outperform those that jump around (linked lists), even if they do the same number of operations. Cache-oblivious algorithms: Some algorithms are designed to minimize cache misses without knowing the cache size. Big-O can be misleading: An O(n) algorithm with poor cache behavior can be slower than an O(n log n) algorithm with good cache behavior for reasonable n.

Cache-Friendly Patterns

•Sequential array access
•Processing data in chunks that fit in cache
•Struct of Arrays (SoA) for SIMD
•Loop tiling / blocking
•Data structure choices that minimize pointer chasing

Cache-Hostile Patterns

•Random access across large arrays
•Linked list traversal (pointer chasing)
•Column-major access of row-major arrays
•Hash table with poor locality
•Excessive indirection (pointers to pointers)

The 90% Rule

For most programs, 90% of execution time is spent in 10% of the code. Outside hot loops, cache behavior rarely matters. But in hot loops processing large data, cache optimization can yield 10x or greater speedups—often more impactful than algorithmic improvements.

When O(1) Fails: Big Integer Arithmetic

The O(1) cost for integer operations assumes numbers fit in fixed-width types. When working with arbitrary-precision integers (big integers), this assumption breaks. Big integer operation costs: For numbers with d digits:

Operation	Naive Cost	Optimized Cost
Addition/Subtraction	O(d)	O(d)
Multiplication	O(d²)	O(d^1.58) Karatsuba, O(d log d) FFT
Division	O(d²)	O(d log d) Newton-Raphson
Modular exponentiation	O(d² × e)	O(d² × log e)

When big integers appear: Cryptography: RSA typically uses 2048-bit or 4096-bit integers. These are 600-1200 decimal digits! Financial calculations: Some financial systems use arbitrary-precision to avoid floating-point errors. Competitive programming: Some problems require numbers larger than 64-bit. Exact arithmetic: Scientific computing sometimes needs exact rationals.

big_integer_complexity.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import time
 
def measure_addition(bits):
    """Measure time for big integer addition"""
    a = 2**bits - 1  # All 1s in binary
    b = 2**bits - 1
    
    start = time.perf_counter()
    for _ in range(10000):
        c = a + b
    end = time.perf_counter()
    
    return (end - start) / 10000
 
def measure_multiplication(bits):
    """Measure time for big integer multiplication"""
    a = 2**bits - 1
    b = 2**bits - 1
    
    start = time.perf_counter()
    for _ in range(1000):
        c = a * b
    end = time.perf_counter()
    
    return (end - start) / 1000
 
# Demonstrate that big integer operations scale with size
print("Big Integer Addition (scales linearly with bits):")
for bits in [64, 256, 1024, 4096, 16384]:
    t = measure_addition(bits)
    print(f"  {bits:5d} bits: {t*1e9:8.1f} ns")
 
print("
Big Integer Multiplication (scales super-linearly):")
for bits in [64, 256, 1024, 4096, 16384]:
    t = measure_multiplication(bits)
    print(f"  {bits:5d} bits: {t*1e6:8.3f} μs")
 
# RSA-2048 multiplication (real-world crypto)
print("
RSA-2048 single multiplication:")
t = measure_multiplication(2048)
print(f"  {t*1e6:.3f} μs")
print(f"  ~{int(t*1e9/0.3)} additions could be done in the same time!")

Accidental Big Integers

In Python, integers automatically promote to arbitrary precision. This can cause accidental quadratic behavior: if you compute 2**n repeatedly in a loop, performance degrades as n grows. Similarly, factorial(10000) involves thousands of big integer multiplications. Always be aware of number sizes in interpreted languages.

Practical Cost Comparison: Operation Benchmarks

To ground our theoretical understanding in reality, let's examine actual benchmark data for integer operations on a modern CPU.

Approximate Operation Throughput (Modern x86-64)
Operation	Throughput (billion ops/sec)	Relative Speed
64-bit addition	10-15	1.0x (baseline)
64-bit subtraction	10-15	1.0x
64-bit bitwise AND/OR/XOR	10-15	1.0x
64-bit left/right shift	10-15	1.0x
64-bit multiplication	2-4	0.25x
32-bit division	0.05-0.1	0.005x
64-bit division	0.03-0.05	0.003x
Branch (predicted)	10+	~1.0x
Branch (mispredicted)	0.2-0.5	0.02x
L1 cache access	10-15	~1.0x
L2 cache access	3-5	0.3x
L3 cache access	1-2	0.1x
RAM access	0.05-0.1	0.005x

Key insights from benchmarks: Division is 100-300x slower than addition. If your algorithm is division-heavy, consider restructuring. Mispredicted branches are 50x slower than predicted branches. Sorting data or using branchless code can be transformative. RAM access is 100-300x slower than L1 cache. Data locality often matters more than algorithmic cleverness. Addition, subtraction, bitwise, and shifts are effectively "free" in comparison to division and cache misses. Implications for algorithm design: Replace division with multiplication where possible (multiply by reciprocal) Use branchless techniques for unpredictable conditions Optimize data layout for cache efficiency Treat all basic arithmetic except division as roughly equal cost

The Modern Optimization Hierarchy

In rough order of impact: (1) Algorithmic complexity, (2) Data locality/cache efficiency, (3) Branch predictability, (4) SIMD/parallelism, (5) Avoiding division, (6) Micro-optimizations. Most programs only need to care about #1 and #2. Only hot paths justify #3-6.

Common Integer Operations and Their Cost Model

The Foundation of Algorithmic Cost

The RAM Model: Our Theoretical Framework

Arithmetic Operations: Addition, Subtraction, Multiplication, Division

Comparison Operations and Branching

Bit Manipulation Operations

Memory Access: The Hidden Cost

When O(1) Fails: Big Integer Arithmetic

Practical Cost Comparison: Operation Benchmarks

There’s more to understand.

Common Integer Operations and Their Cost Model

The Foundation of Algorithmic Cost

The RAM Model: Our Theoretical Framework

Arithmetic Operations: Addition, Subtraction, Multiplication, Division

Comparison Operations and Branching

Bit Manipulation Operations

Memory Access: The Hidden Cost

When O(1) Fails: Big Integer Arithmetic

Practical Cost Comparison: Operation Benchmarks

There’s more to understand.