Bit Shifting - Learning Module

Loading content...

0/276

Right Shift — Divide by 2

Division at the Speed of Light

If left shift is the fastest multiplication, then right shift is the fastest division. The right shift operator (>>) divides by powers of 2 in a single CPU cycle—far faster than the division instruction, which can take 10-30+ cycles on modern processors.

But right shift hides a subtlety that left shift doesn't face: what fills the vacated positions on the left? For unsigned numbers, the answer is always zeros. For signed numbers, the answer depends on whether you're performing a logical or arithmetic shift—a distinction that has profound implications for correctness.

What You Will Learn

By the end of this page, you will understand exactly how right shift performs division, why the division truncates toward zero (or negative infinity, depending on the variant), how unsigned and signed values behave differently, and how to use right shift correctly in practical code. You'll gain the intuition to avoid the subtle bugs that arise from misunderstanding this operation.

The Mechanics of Right Shift

The right shift operation moves every bit in the binary representation of a number n positions to the right. The n rightmost bits are discarded (shifted out), and n new bits appear on the left. What those new bits are is the central question.

For unsigned integers: The new bits are always 0. This is a logical right shift (also called unsigned right shift).

Let's trace through a concrete example with an 8-bit unsigned integer:

Right Shifting the Unsigned Value 200 by Different Amounts
Expression	Binary Before	Binary After	Decimal Result
200 >> 0	11001000	11001000	200
200 >> 1	11001000	01100100	100
200 >> 2	11001000	00110010	50
200 >> 3	11001000	00011001	25
200 >> 4	11001000	00001100	12
200 >> 5	11001000	00000110	6
200 >> 6	11001000	00000011	3
200 >> 7	11001000	00000001	1
200 >> 8	11001000	00000000	0

Observe the pattern: each right shift by 1 roughly halves the value, but with truncation toward zero. When 25 (an odd number) is shifted right by 1, the rightmost bit (which represents 1) is discarded, yielding 12, not 12.5. This is integer division behavior: 25 >> 1 = 25 ÷ 2 = 12 (remainder discarded).

The mathematical identity:

x >> k = floor(x / 2^k) for unsigned (and non-negative signed) integers

This truncation toward zero is exactly what integer division produces. Right shift and division by 2 are thus equivalent for non-negative values—but not for negative values, as we'll see.

Bits Discarded Are Lost Forever

Unlike division, which could preserve a remainder, right shift permanently discards the low-order bits. There's no way to recover x from x >> k without additional information. This is analogous to how floor division in mathematics loses the fractional part.

The Mathematical Foundation

Just as left shift multiplies because it moves bits to higher positional values, right shift divides because it moves bits to lower positional values.

Recall the binary representation:

value = bₙ₋₁ × 2^(n-1) + bₙ₋₂ × 2^(n-2) + ... + b₁ × 2¹ + b₀ × 2⁰

For the number 200 (binary 11001000):

200 = 1×2⁷ + 1×2⁶ + 0×2⁵ + 0×2⁴ + 1×2³ + 0×2² + 0×2¹ + 0×2⁰ 200 = 128 + 64 + 8 = 200

When we right shift by 1:

100 = 0×2⁷ + 1×2⁶ + 1×2⁵ + 0×2⁴ + 0×2³ + 1×2² + 0×2¹ + 0×2⁰ 100 = 64 + 32 + 4 = 100

Each term has moved to the next lower power of 2. The bit that was at position 7 (contributing 128) is now at position 6 (contributing 64). The bit that was at position 0 (contributing its value) has been shifted out entirely—gone forever.

Key Mathematical Properties

•Division by power of 2: x >> k = floor(x / 2^k) for non-negative x
•Identity: x >> 0 = x — Shifting by zero leaves the value unchanged
•Associativity: (x >> a) >> b = x >> (a + b) — Multiple shifts combine (within bounds)
•Zero production: For any x, sufficient right shifts eventually produce 0
•Relationship with left shift: (x << k) >> k = x only when no overflow occurred during left shift; otherwise bits are lost
•Monotonicity: If a ≤ b, then a >> k ≤ b >> k (for non-negative values)

Why right shift is faster than division:

Division is one of the slowest arithmetic operations. On x86, a 64-bit unsigned division can take 30-90 cycles depending on the operand values. Right shift takes 1 cycle. For division by compile-time constant powers of 2, compilers automatically convert to shifts. But understanding this lets you recognize the optimization in complex expressions and apply it manually when working with runtime values that happen to be powers of 2.

Extracting Bit Fields

Right shift combined with masking is the standard way to extract bit fields from packed values. To extract bits [a, b) from value x: (x >> a) & ((1 << (b - a)) - 1). The shift brings the field to the lowest bits; the mask isolates just those bits.

Practical Applications of Right Shift

Right shift appears throughout computing, often paired with left shift for complete bit field manipulation. Here are the most important applications:

Common Applications

•Fast division by powers of 2 — Halving values, computing averages, binary search midpoint calculations, and any division by 2, 4, 8, etc.
•Extracting packed values — Unpacking RGB colors, extracting bit fields from protocol headers, and reading hardware register fields.
•Computing logarithms — Counting right shifts until a value becomes 0 gives floor(log₂(x)) + 1 (the position of the highest set bit).
•Hashing and checksums — Mixing bits from high positions to low positions for better distribution.
•Binary search and divide-and-conquer — Computing midpoints as (low + high) >> 1 or low + ((high - low) >> 1) to avoid overflow.
•Sign extension detection — Examining the MSB by shifting it to the LSB position.

right_shift_examples.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
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
78
79
80
81
82
# Example 1: Fast division by powers of 2
def halve(x: int) -> int:
    """Divide by 2 using right shift (for non-negative x)."""
    return x >> 1
 
def divide_by_8(x: int) -> int:
    """Divide by 8 (2^3) using right shift."""
    return x >> 3
 
def divide_by_power_of_2(x: int, power: int) -> int:
    """Divide by 2^power using right shift."""
    return x >> power
 
# Example 2: Extracting RGB from packed 32-bit color
def extract_rgb(color: int) -> tuple:
    """Extract 8-bit RGB components from 0x00RRGGBB format."""
    r = (color >> 16) & 0xFF  # Shift red to lowest byte, mask
    g = (color >> 8) & 0xFF   # Shift green to lowest byte, mask
    b = color & 0xFF          # Blue is already in lowest byte
    return (r, g, b)
 
def extract_rgba(color: int) -> tuple:
    """Extract 8-bit RGBA components from 0xAARRGGBB format."""
    a = (color >> 24) & 0xFF
    r = (color >> 16) & 0xFF
    g = (color >> 8) & 0xFF
    b = color & 0xFF
    return (r, g, b, a)
 
# Example 3: Computing floor(log2(x)) using right shift
def floor_log2(x: int) -> int:
    """Compute floor of log base 2 of x using right shifts.
    
    Returns -1 for x <= 0.
    This counts the position of the highest set bit (0-indexed).
    """
    if x <= 0:
        return -1
    
    log = 0
    while x > 1:
        x >>= 1
        log += 1
    return log
 
# Example 4: Safe binary search midpoint (avoiding overflow)
def binary_search_midpoint(low: int, high: int) -> int:
    """Compute midpoint avoiding integer overflow.
    
    The naive (low + high) // 2 can overflow if low + high > MAX_INT.
    This version avoids that issue.
    """
    return low + ((high - low) >> 1)
 
# Example 5: Extracting bit at position
def get_bit(value: int, position: int) -> int:
    """Get the bit at the specified position (0-indexed from right)."""
    return (value >> position) & 1
 
def get_bits(value: int, start: int, count: int) -> int:
    """Extract 'count' bits starting at position 'start'."""
    mask = (1 << count) - 1  # Creates 'count' ones
    return (value >> start) & mask
 
# Demonstration
if __name__ == "__main__":
    print(f"halve(17) = {halve(17)}")          # 8 (truncates 0.5)
    print(f"divide_by_8(100) = {divide_by_8(100)}")  # 12
    
    color = 0xFF8040  # RGB: 255, 128, 64
    print(f"extract_rgb(0x{color:06X}) = {extract_rgb(color)}")  # (255, 128, 64)
    
    print(f"floor_log2(1) = {floor_log2(1)}")    # 0
    print(f"floor_log2(8) = {floor_log2(8)}")    # 3
    print(f"floor_log2(15) = {floor_log2(15)}")  # 3
    print(f"floor_log2(16) = {floor_log2(16)}")  # 4
    
    print(f"binary_search_midpoint(0, 100) = {binary_search_midpoint(0, 100)}")  # 50
    
    print(f"get_bit(0b1010, 1) = {get_bit(0b1010, 1)}")  # 1
    print(f"get_bit(0b1010, 2) = {get_bit(0b1010, 2)}")  # 0
    print(f"get_bits(0b11110011, 2, 4) = {bin(get_bits(0b11110011, 2, 4))}")  # 0b1100

The binary search midpoint example is particularly important. The classic formula (low + high) / 2 can overflow when low + high exceeds the maximum integer value. Using low + ((high - low) >> 1) avoids this by never exceeding the range of valid indices. This seemingly minor detail has caused real bugs in production systems, including in early Java standard library implementations.

Right Shift and Truncation Behavior

A critical detail of right shift is its truncation behavior. When you divide an odd number by 2, the mathematical result is not an integer. Right shift, like integer division, must produce an integer, so it truncates.

For positive numbers: Right shift truncates toward zero (equivalent to floor). This matches natural division behavior:

5 >> 1 = 2 (not 2.5)
7 >> 2 = 1 (not 1.75)
15 >> 3 = 1 (not 1.875)

The truncated fractional part is effectively the bits that were shifted out, interpreted as a fraction.

Truncation in Right Shift Operations
Value	Value >> 1	Mathematical ÷ 2	Bits Lost	Fractional Part
10 (1010)	5 (0101)	5.0	0	0.0
11 (1011)	5 (0101)	5.5	1	0.5
12 (1100)	6 (0110)	6.0	0	0.0
13 (1101)	6 (0110)	6.5	1	0.5
14 (1110)	7 (0111)	7.0	0	0.0
15 (1111)	7 (0111)	7.5	1	0.5

Notice that the bit shifted out (the LSB) directly tells you whether truncation occurred. If the LSB is 1 (odd number), you're truncating by 0.5. If the LSB is 0 (even number), no truncation occurs.

For shifting by more than 1:

When shifting by k positions, you're dividing by 2^k and truncating. The k least significant bits represent the fractional part:

7 >> 2 = 1 — The lost bits are 11 (binary), representing 3. In fractional terms: 7 = 1×4 + 3, so 7/4 = 1.75, truncated to 1.
26 >> 3 = 3 — The lost bits are 010 (binary), representing 2. 26 = 3×8 + 2, so 26/8 = 3.25, truncated to 3.

Recovering the Remainder

You can recover the truncated portion using a mask. For x >> k, the lost bits are x & ((1 << k) - 1). This gives you the equivalent of x % (2^k) without using the expensive modulo operation. Combined with the quotient from the shift, you have both parts of integer division.

quotient_remainder.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
def divmod_power_of_2(x: int, k: int) -> tuple:
    """Compute quotient and remainder of x / 2^k using shifts and masks.
    
    Much faster than using / and % operators.
    
    Returns: (quotient, remainder)
    """
    quotient = x >> k
    remainder = x & ((1 << k) - 1)  # Equivalent to x % (2^k)
    return (quotient, remainder)
 
# Demonstration
if __name__ == "__main__":
    # Divide 100 by 8 (2^3)
    q, r = divmod_power_of_2(100, 3)
    print(f"100 / 8 = {q} remainder {r}")  # 12 remainder 4
    print(f"Verification: 12 * 8 + 4 = {12 * 8 + 4}")  # 100
    
    # Divide 1000 by 16 (2^4)
    q, r = divmod_power_of_2(1000, 4)
    print(f"1000 / 16 = {q} remainder {r}")  # 62 remainder 8
    print(f"Verification: 62 * 16 + 8 = {62 * 16 + 8}")  # 1000
    
    # This is exactly what integer division gives us
    assert divmod_power_of_2(100, 3) == (100 // 8, 100 % 8)
    assert divmod_power_of_2(1000, 4) == (1000 // 16, 1000 % 16)
    print("All verifications passed!")

Right Shift with Unsigned Integers

Unsigned right shift is the simplest case and is called logical right shift. Zeros always fill the vacated positions on the left. This is the natural interpretation when there's no sign to preserve.

Languages and their unsigned right shift:

C/C++: The >> operator on unsigned types performs logical shift
Java: The >>> operator always performs logical shift (even on signed types)
Python: Integers have arbitrary precision; >> on positive numbers works as logical shift
JavaScript: >>> performs 32-bit unsigned right shift

Logical Right Shift Examples (8-bit)
Decimal	Binary	1 (Binary)	1 (Decimal)
255	11111111	01111111	127
128	10000000	01000000	64
200	11001000	01100100	100
64	01000000	00100000	32
1	00000001	00000000	0

Notice that for 255 and 128, where the MSB is 1, the logical right shift inserts a 0, which is correct for unsigned interpretation. The value 255 (all bits set) becomes 127 (all bits except MSB set) after shifting right by 1—exactly what 255 / 2 = 127.5, truncated, should give.

The pure mathematical relationship:

For unsigned x and shift amount k where 0 ≤ k < bit_width:

x >> k = floor(x / 2^k)

This is a clean, intuitive relationship with no surprises. Unsigned right shift is conceptually simple—which is why experienced programmers prefer unsigned types for bit manipulation.

unsigned_right_shift.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
#include <stdint.h>
#include <stdio.h>
 
// Demonstrate logical (unsigned) right shift
void demonstrate_logical_shift(void) {
    uint8_t values[] = {255, 128, 200, 64, 1};
    size_t count = sizeof(values) / sizeof(values[0]);
    
    printf("Logical Right Shift (unsigned 8-bit):\n");
    printf("%-10s %-12s %-12s %-10s\n", "Decimal", "Binary", ">> 1 Bin", ">> 1 Dec");
    printf("-----------------------------------------\n");
    
    for (size_t i = 0; i < count; i++) {
        uint8_t v = values[i];
        uint8_t shifted = v >> 1;
        
        // Print binary representation
        printf("%-10u ", v);
        for (int b = 7; b >= 0; b--) printf("%d", (v >> b) & 1);
        printf("   ");
        for (int b = 7; b >= 0; b--) printf("%d", (shifted >> b) & 1);
        printf("   %-10u\n", shifted);
    }
}
 
// Use unsigned right shift for bit extraction
uint8_t extract_high_nibble(uint8_t byte) {
    // Extract bits 4-7 by shifting them to positions 0-3
    return byte >> 4;
}
 
uint8_t extract_low_nibble(uint8_t byte) {
    // Low nibble is already in positions 0-3; just mask
    return byte & 0x0F;
}
 
int main(void) {
    demonstrate_logical_shift();
    
    printf("\nNibble extraction from 0xAB:\n");
    uint8_t value = 0xAB;  // 10101011 in binary
    printf("High nibble: 0x%X\n", extract_high_nibble(value));  // 0xA = 10
    printf("Low nibble:  0x%X\n", extract_low_nibble(value));   // 0xB = 11
    
    return 0;
}

Consistency is Key

When performing bit manipulation, stick with unsigned types from start to finish. Mixing signed and unsigned in shift operations creates subtle bugs and platform-dependent behavior. The mental model is much simpler when all values are unsigned.

Rounding Behavior Compared to Division

It's tempting to think of right shift as simply 'fast division.' For non-negative values, this is essentially true. But the behavior diverges in subtle ways that matter for certain algorithms.

Right shift vs. integer division for unsigned/positive values:

5 >> 1 = 2 and 5 // 2 = 2 ✓ (same)
17 >> 2 = 4 and 17 // 4 = 4 ✓ (same)
100 >> 3 = 12 and 100 // 8 = 12 ✓ (same)

For positive numbers, x >> k and x // (2**k) are always identical. The truncation is always toward zero, which is also toward negative infinity for positive numbers, so there's no ambiguity.

When to Use Right Shift vs. Division

•Use right shift when: The divisor is a power of 2, you're working with unsigned values, maximum performance is needed, or you're performing bit-level operations like field extraction.
•Use regular division when: The divisor might not be a power of 2, readability is more important than micro-optimization, you're working with signed values (unless you understand the difference), or the compiler will optimize it anyway.
•Both are equivalent when: Working with non-negative values and dividing by 2^k. In these cases, use whichever is more readable for the context.

The compiler's perspective:

Modern compilers are extremely good at converting division by constant powers of 2 into shift operations. In fact, they're often better at it than humans because they handle edge cases correctly. Consider this practical advice:

Write x / 2 for clarity when dividing by 2 conceptually
Write x >> 1 when you're explicitly performing bit-level work
The generated assembly will likely be identical in both cases

The exception is when working with runtime-determined power-of-2 divisors, where you must use shift explicitly.

Checking if a Value is a Power of 2

Before using right shift for 'division by a power of 2' when the divisor is a variable, verify it actually is a power of 2. The trick: (n > 0) && ((n & (n - 1)) == 0) returns true only for positive powers of 2. This works because powers of 2 have exactly one bit set, and n-1 has all lower bits set, so they share no common bits.

Performance Characteristics

Right shift has the same excellent performance profile as left shift—single-cycle execution on all modern processors. But the comparison with division is where the performance story becomes dramatic.

Performance Comparison: Right Shift vs. Division (x86-64)
Operation	Instruction	Latency (cycles)	Throughput
x >> k (constant k)	shr/sar	1	~0.25 cycles
x >> n (variable n)	shr/sar	1-2	~0.5 cycles
x / 2 (signed)	sar + add + sar	2-3	~1 cycle
x / n (32-bit unsigned)	div	20-30	~8 cycles
x / n (64-bit unsigned)	div	30-90	~20+ cycles

The difference is stark: right shift is 20-90x faster than general division. Even when the compiler transforms division by a constant into shift-based code, understanding this allows you to recognize optimization opportunities in complex expressions.

Why division is so slow:

Division requires iterative algorithms internally—essentially a loop that runs once per bit of precision. Multiplication can be parallelized at the hardware level (using techniques like Wallace trees), but division is inherently sequential. Modern CPUs have heavily optimized dividers, but they still can't compete with the simplicity of shifting bits.

Practical implications:

When Performance Matters

•Image processing: Computing averages of pixel values across millions of pixels. (a + b) >> 1 instead of (a + b) / 2 compounds significantly.
•Game engines: Physics calculations, coordinate transformations, and level-of-detail decisions run every frame at 60+ FPS.
•Embedded systems: Low-power microcontrollers may not have hardware dividers at all; division is emulated in software.
•Cryptographic code: Constant-time operations are required; division time varies with operand values, potentially leaking information.
•High-frequency trading: Every nanosecond matters; avoiding division in hot paths is table stakes.

Summary: Mastering Right Shift

We've explored the right shift operator for unsigned values in depth. Here are the essential takeaways:

Key Takeaways

•Right shift moves bits rightward, discarding low-order bits. For logical (unsigned) right shift, zeros fill the left side.
•x >> k = floor(x / 2^k) for non-negative values. This is the fundamental mathematical relationship.
•Truncation discards the fractional part. The shifted-out bits are lost; use masking to recover them as a 'remainder'.
•Unsigned right shift is straightforward. With unsigned types, there are no surprises—always logical shift, always zeros on the left.
•Applications are ubiquitous: fast division, bit field extraction, computing logarithms, binary search midpoints, and hashing.
•Performance is exceptional. Right shift is 1 cycle; division can be 30-90 cycles. The difference is dramatic.
•Prefer unsigned types for bit manipulation. The mental model is simpler, and behavior is consistent across platforms.

Next up: We'll tackle the more complex topic of signed right shift—the distinction between logical and arithmetic shifts. When negative numbers are involved, the filled bits are no longer always zeros, and different languages make different choices. Understanding this is essential for correct bit manipulation in real-world code.

Page Complete

You now understand right shift for unsigned values—the logical shift that fills with zeros and divides by powers of 2 with truncation toward zero. Next, we'll explore the critical distinction between logical and arithmetic shifts that determines how negative numbers behave.