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

def demonstrate_rounding_difference():
    """Show the difference between arithmetic shift and division for negative odds."""
    
    print("Comparison: Arithmetic Shift vs Integer Division")
    print("-" * 60)
    print(f"{'Value':<10} {'>> 1':<10} {'// 2':<10} {'true ÷ 2':<12} {'Match?':<10}")
    print("-" * 60)
    
    for x in range(-10, 11):
        shift_result = x >> 1  # Arithmetic right shift
        div_result = x // 2    # Integer division (Python: floor toward -inf)
        true_div = x / 2       # True division
        
        # In Python, // also rounds toward -inf, so they match!
        # In C/Java, / rounds toward zero, so they differ for negative odds
        match = "✓" if shift_result == div_result else "✗"
        
        print(f"{x:<10} {shift_result:<10} {div_result:<10} {true_div:<12.1f} {match:<10}")
 
def show_c_style_difference():
    """Demonstrate what happens with C-style truncating division."""
    
    print("\nC-style truncating division vs shift (for negative odds):")
    print("-" * 50)
    
    # Python's // is floor division. To simulate C truncation:
    def c_style_div(x, y):
        # math.trunc would also work
        result = x // y
        if x < 0 and x % y != 0:
            result += 1  # Adjust for truncation toward zero
        return result
    
    for x in [-7, -5, -3, -1]:
        shift = x >> 1         # -4, -3, -2, -1 (floor toward -inf)
        c_div = c_style_div(x, 2)  # -3, -2, -1, 0 (truncate toward zero)
        print(f"{x} >> 1 = {shift}, {x} / 2 (C) = {c_div}, differ = {shift != c_div}")
 
if __name__ == "__main__":
    demonstrate_rounding_difference()
    show_c_style_difference()

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

public class ShiftComparison {
    public static void main(String[] args) {
        int negative = -8;  // 11111111 11111111 11111111 11111000 (32-bit)
        
        System.out.println("Original: " + negative + " = " + 
                           Integer.toBinaryString(negative));
        
        // Arithmetic right shift (>>)
        int arithmetic = negative >> 1;
        System.out.println(">> 1:     " + arithmetic + " = " + 
                           Integer.toBinaryString(arithmetic));
        // Output: -4 = 11111111111111111111111111111100
        
        // Logical right shift (>>>)
        int logical = negative >>> 1;
        System.out.println(">>> 1:    " + logical + " = " + 
                           Integer.toBinaryString(logical));
        // Output: 2147483644 = 01111111111111111111111111111100
        
        // The difference is dramatic:
        // Arithmetic: -8 >> 1 = -4 (correct half)
        // Logical:    -8 >>> 1 = 2147483644 (not a half at all!)
        
        // Common use case for >>>: 
        // Computing midpoint without overflow
        int low = 0, high = Integer.MAX_VALUE;
        int badMid = (low + high) / 2;  // Might overflow!
        int goodMid = (low + high) >>> 1;  // Safe: treats as unsigned
        
        System.out.println("\nMidpoint calculation:");
        System.out.println("Bad mid:  " + badMid);   // Works here by luck
        System.out.println("Good mid: " + goodMid);  // Works always
        
        // When high = MAX_VALUE and low = MAX_VALUE - 10:
        // low + high overflows!
        int low2 = Integer.MAX_VALUE - 10;
        int high2 = Integer.MAX_VALUE;
        int badMid2 = (low2 + high2) / 2;   // Overflow -> negative -> wrong!
        int goodMid2 = (low2 + high2) >>> 1;  // Treats as unsigned -> correct
        
        System.out.println("\nOverflow case:");
        System.out.println("low=" + low2 + ", high=" + high2);
        System.out.println("Bad mid:  " + badMid2);   // Negative garbage!
        System.out.println("Good mid: " + goodMid2);  // Correct value
    }
}

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

#include <stdint.h>
 
// Logical right shift - guaranteed zero-fill
// Works by casting to unsigned, shifting, and casting back
static inline int32_t logical_right_shift(int32_t x, unsigned int n) {
    return (int32_t)((uint32_t)x >> n);
}
 
// Arithmetic right shift - guaranteed sign-extension
// Portable implementation that doesn't rely on implementation-defined behavior
static inline int32_t arithmetic_right_shift(int32_t x, unsigned int n) {
    // Method 1: Rely on common implementation (pragmatic)
    // Most compilers implement >> as arithmetic for signed types
    // return x >> n;
    
    // Method 2: Fully portable (paranoid)
    if (x >= 0) {
        return x >> n;  // Positive: logical == arithmetic
    } else {
        // Negative: compute logical shift, then set high bits
        uint32_t ux = (uint32_t)x;
        uint32_t shifted = ux >> n;
        
        // Create mask for sign extension
        // If n=1, mask = 0x80000000 (just the MSB)
        // If n=2, mask = 0xC0000000 (top 2 bits)
        uint32_t mask = ~((~(uint32_t)0) >> n);
        
        return (int32_t)(shifted | mask);
    }
}
 
// Example usage with clear intent
int divide_by_4_signed(int x) {
    // Use arithmetic shift to divide signed value
    // Note: rounds toward -infinity, not zero
    return arithmetic_right_shift(x, 2);
}
 
uint32_t extract_high_byte(uint32_t value) {
    // Use logical shift to extract bits
    return logical_right_shift((int32_t)value, 24);
}

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

import numpy as np
 
def demonstrate_minus_one_shift():
    """Show that -1 arithmetic shifted remains -1."""
    
    print("Arithmetic shift of -1 (using numpy for fixed-width):")
    x = np.int8(-1)  # 8-bit signed -1 = 11111111
    
    for shift in range(8):
        result = x >> shift
        print(f"  -1 >> {shift} = {result} (binary: {format(result & 0xFF, '08b')})")
 
def create_sign_mask(value: int, bits: int = 32) -> int:
    """
    Create a mask that's all 1s if value is negative, all 0s if non-negative.
    
    Uses arithmetic right shift to replicate the sign bit across all positions.
    """
    # Shift right by (bits - 1) positions
    # This moves the sign bit to the LSB, with all higher bits being copies
    # For negative: result is all 1s (-1)
    # For non-negative: result is all 0s (0)
    return value >> (bits - 1)
 
def absolute_value_branchless(x: int) -> int:
    """
    Compute absolute value without branches using sign mask.
    
    For 32-bit signed integers.
    Note: Has issues with INT_MIN, which has no positive counterpart.
    """
    # Get mask: all 1s if negative, all 0s if positive
    mask = x >> 31
    
    # XOR with mask: if negative, this inverts all bits
    # Adding 1 to inverted bits gives two's complement (negation)
    # If positive, XOR with 0 and add 0 does nothing
    return (x ^ mask) - mask
 
def conditional_negate_branchless(x: int, should_negate: bool) -> int:
    """
    Negate x if should_negate is True, otherwise return x.
    No branching.
    """
    # Convert bool to mask: -1 if True, 0 if False
    mask = -int(should_negate)
    
    # XOR negates if mask is all 1s
    # Subtracting mask adds 1 if we negated (completes two's complement)
    return (x ^ mask) - mask
 
if __name__ == "__main__":
    demonstrate_minus_one_shift()
    
    print("\nSign mask demonstration:")
    for val in [-100, -1, 0, 1, 100]:
        mask = create_sign_mask(val, 8)
        print(f"  sign_mask({val:4d}) = {mask:4d} ({format(mask & 0xFF, '08b')})")
    
    print("\nBranchless absolute value:")
    for val in [-42, -1, 0, 1, 42]:
        result = absolute_value_branchless(val)
        print(f"  abs({val:3d}) = {result}")

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

public class ShiftBugs {
    
    // Bug 1: Using >> when >>> was needed for bit extraction
    public static int extractHighByteBuggy(int value) {
        // If value is negative, >> sign-extends!
        // 0x80000000 >> 24 = 0xFFFFFF80, not 0x00000080
        return value >> 24;  // BUG: sign extension pollutes result
    }
    
    public static int extractHighByteCorrect(int value) {
        // >>> ensures zeros fill from the left
        return value >>> 24;  // CORRECT: always gives 0x000000XX
    }
    
    // Bug 2: Using >>> when >> was needed for signed division
    public static int halveBuggy(int value) {
        // If value is negative, >>> gives huge positive number!
        // -8 >>> 1 = 2147483644, not -4
        return value >>> 1;  // BUG: wrong for negative values
    }
    
    public static int halveCorrect(int value) {
        // >> preserves sign for proper division
        return value >> 1;  // CORRECT: -8 >> 1 = -4
        // Note: rounds toward -inf, not zero. 
        // -7 >> 1 = -4, but -7 / 2 = -3
    }
    
    // Bug 3: Byte shift sign extension issue
    public static int processByteBuggy(byte b) {
        // byte is signed in Java, -128 to 127
        // When shifted, byte is first widened to int (sign-extended)
        // byte -1 (0xFF) becomes int -1 (0xFFFFFFFF)
        // Then shifted: still 0xFFFFFFFF if we expect 0x0000007F
        return b >> 1;  // May give unexpected sign-extended results
    }
    
    public static int processByteCorrect(byte b) {
        // Mask to treat byte as unsigned before shifting
        return (b & 0xFF) >> 1;  // Now b is treated as 0-255
    }
    
    public static void main(String[] args) {
        // Demonstrate Bug 1
        int val = 0x80000000; // Negative (MSB set)
        System.out.println("High byte extraction from " + 
                           Integer.toHexString(val) + ":");
        System.out.println("  Buggy:   0x" + 
                           Integer.toHexString(extractHighByteBuggy(val)));
        // Expected: 0x80, Actual: 0xFFFFFF80
        System.out.println("  Correct: 0x" + 
                           Integer.toHexString(extractHighByteCorrect(val)));
        // Expected: 0x80, Actual: 0x80
        
        // Demonstrate Bug 2
        System.out.println("\nHalving -8:");
        System.out.println("  Buggy:   " + halveBuggy(-8));
        // Expected: -4, Actual: 2147483644
        System.out.println("  Correct: " + halveCorrect(-8));
        // Expected: -4, Actual: -4
        
        // Demonstrate Bug 3
        byte negByte = -1;  // 0xFF in bits
        System.out.println("\nProcessing byte " + negByte + " (0xFF):");
        System.out.println("  Buggy:   " + processByteBuggy(negByte));
        // May be -1 (sign-extended then shifted)
        System.out.println("  Correct: " + processByteCorrect(negByte));
        // Should be 127 (0x7F)
    }
}