program.sh

#!/bin/bash
#
# Branchless Programming Examples in Bash
#
# "Branchless" means we avoid if/else and other conditional jumps.
# Instead, we use arithmetic and bit tricks so the CPU executes
# the SAME instructions regardless of the input values.
#
# BASH NOTE:
#   Bash arithmetic $(( )) uses the host platform's integer size
#   (typically 64-bit on modern Linux). The right-shift operator >>
#   performs arithmetic shift (fills with sign bit) on most systems.
#   We shift by 63 (not 31) because Bash integers are 64-bit.

# ─────────────────────────────────────────────
# get_sign — Returns +1 for positive, 0 for zero, -1 for negative.
#
# TRICK:
#   is_negative = -(num >> 63)     → 1 if num < 0, else 0
#   is_positive = -((-num) >> 63)  → 1 if num > 0, else 0
#   sign = is_positive - is_negative
#
# WORKED EXAMPLE (num = -7):
#   -7 >> 63 = -1  →  is_negative = 1
#   7 >> 63  =  0  →  is_positive = 0
#   Result: 0 - 1 = -1  ✓
#
# WORKED EXAMPLE (num = 42):
#   42 >> 63  = 0  →  is_negative = 0
#   -42 >> 63 = -1 →  is_positive = 1
#   Result: 1 - 0 = 1  ✓
# ─────────────────────────────────────────────
get_sign() {
    local num=$1
    local is_negative=$(( -(num >> 63) ))
    local is_positive=$(( -((-num) >> 63) ))
    echo $(( is_positive - is_negative ))
}

# ─────────────────────────────────────────────
# min_branchless — Returns the smaller of two integers using bit masking.
#
# TRICK:
#   diff = a - b
#   mask = diff >> 63     → -1 (all 1s) if a < b, 0 if a >= b
#   min = b + (diff & mask)
#
# WORKED EXAMPLE (a=15, b=9):
#   diff = 6, mask = 0
#   result = 9 + (6 & 0) = 9  ✓
#
# WORKED EXAMPLE (a=3, b=7):
#   diff = -4, mask = -1
#   result = 7 + (-4 & -1) = 7 + (-4) = 3  ✓
# ─────────────────────────────────────────────
min_branchless() {
    local a=$1
    local b=$2
    local diff=$((a - b))
    local mask=$((diff >> 63))
    echo $((b + (diff & mask)))
}

# ─────────────────────────────────────────────
# min_with_helper — Alternative branchless min using multiplication.
#
# TRICK:
#   smaller = (b - a) >> 63 & 1   → 1 if b < a, 0 if b >= a
#   result = a + (b - a) * smaller
#
# When b < a (smaller=1): a + (b - a) * 1 = b  ✓
# When b >= a (smaller=0): a + (b - a) * 0 = a  ✓
# ─────────────────────────────────────────────
min_with_helper() {
    local a=$1
    local b=$2
    # Extract the sign bit: 1 if (b - a) is negative (meaning b < a)
    local smaller=$(( ((b - a) >> 63) & 1 ))
    echo $((a + (b - a) * smaller))
}

# === Demo ===
num1=42
num2=-7
num3=0

echo "=== Branchless Sign Detection ==="
echo "sign($num1)  = $(get_sign $num1)"
echo "sign($num2) = $(get_sign $num2)"
echo "sign($num3)  = $(get_sign $num3)"

a=15
b=9

echo ""
echo "=== Branchless Minimum ==="
echo "min($a, $b) via bitmask:        $(min_branchless $a $b)"
echo "min($a, $b) via multiplication: $(min_with_helper $a $b)"