program.js

/*
 * Branchless Programming Examples in JavaScript
 *
 * "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.
 *
 * Why? Modern CPUs "guess" which branch an if-statement will take
 * (branch prediction). When they guess wrong, they waste 10-20 cycles
 * flushing the pipeline. Branchless code has no guesses to get wrong.
 *
 * JAVASCRIPT NOTE:
 *   JS bitwise operators (>>, &, |, ^, ~) internally convert numbers
 *   to 32-bit signed integers, perform the operation, then convert back.
 *   This means >> 31 works like C's arithmetic right shift for values
 *   that fit in 32 bits. For numbers outside ±2^31, results are unreliable.
 */

/**
 * getSign — Returns +1 for positive, 0 for zero, -1 for negative.
 *
 * TRICK: We extract two pieces of information using arithmetic right shift:
 *   1. Is the number negative?  →  num >> 31 gives 0 or -1
 *   2. Is the number positive?  →  (-num) >> 31 gives 0 or -1
 * Then we combine: isPositive - isNegative
 *
 * WORKED EXAMPLE (num = -7):
 *
 *   Step 1: isNegative
 *     -7 in 32-bit:  11111111 11111111 11111111 11111001
 *     >> 31:         11111111 11111111 11111111 11111111  = -1
 *     negate:        -(-1) = 1
 *     → isNegative = 1
 *
 *   Step 2: isPositive
 *     -(-7) = 7:     00000000 00000000 00000000 00000111
 *     >> 31:         00000000 00000000 00000000 00000000  = 0
 *     negate:        -(0) = 0
 *     → isPositive = 0
 *
 *   Step 3: isPositive - isNegative = 0 - 1 = -1  ✓
 *
 * WORKED EXAMPLE (num = 42):
 *     isNegative = -(42 >> 31)    = -(0)  = 0
 *     isPositive = -((-42) >> 31) = -(-1) = 1
 *     Result: 1 - 0 = 1  ✓
 *
 * WORKED EXAMPLE (num = 0):
 *     isNegative = -(0 >> 31)    = 0
 *     isPositive = -((-0) >> 31) = 0   (−0 is still 0 in bitwise ops)
 *     Result: 0 - 0 = 0  ✓
 */
function getSign(num) {
    let isNegative = -(num >> 31);    // 1 if num < 0, else 0
    let isPositive = -((-num) >> 31); // 1 if num > 0, else 0
    return isPositive - isNegative;
}

/**
 * minBranchless — Returns the smaller of two integers using bit masking.
 *
 * TRICK: Compute (a - b), then use its sign bit as a mask.
 *   - If a < b, then diff is negative → mask = 0xFFFFFFFF (all 1s, = -1)
 *   - If a >= b, then diff is non-negative → mask = 0x00000000 (all 0s, = 0)
 *
 * Formula: min = b + (diff & mask)
 *
 * WORKED EXAMPLE (a=15, b=9):
 *     diff = 15 - 9 = 6
 *     6 >> 31 = 0  (mask)
 *     diff & 0 = 0
 *     result = 9 + 0 = 9  ✓
 *
 * WORKED EXAMPLE (a=3, b=7):
 *     diff = 3 - 7 = -4
 *     -4 >> 31 = -1  (mask = all 1s)
 *     diff & (-1) = -4  (AND with all 1s keeps value unchanged)
 *     result = 7 + (-4) = 3  ✓
 */
function minBranchless(a, b) {
    let diff = a - b;
    let mask = diff >> 31;  // 0 if a >= b, -1 if a < b
    return b + (diff & mask);
}

/**
 * isSmaller — Returns 1 if a < b, 0 otherwise.
 *
 * NOTE: In JavaScript, (a - b) < 0 returns a boolean.
 * Number(true) = 1, Number(false) = 0 — we use this to get 0 or 1.
 */
function isSmaller(a, b) {
    return Number((a - b) < 0);
}

/**
 * minWithHelper — Alternative branchless min using multiplication.
 *
 * Instead of bit masking, we multiply by 0 or 1 to "select" a value.
 *
 *   result = a + (b - a) * isSmaller(b, a)
 *
 * WORKED EXAMPLE (a=15, b=9):
 *     isSmaller(9, 15) = 1  (9 < 15 → true → 1)
 *     result = 15 + (9 - 15) * 1 = 15 + (-6) = 9  ✓
 *
 * WORKED EXAMPLE (a=3, b=7):
 *     isSmaller(7, 3) = 0  (7 < 3 → false → 0)
 *     result = 3 + (7 - 3) * 0 = 3 + 0 = 3  ✓
 */
function minWithHelper(a, b) {
    return a + (b - a) * isSmaller(b, a);
}

// === Demo ===
let num1 = 42;
let num2 = -7;
let num3 = 0;

console.log("=== Branchless Sign Detection ===");
console.log(`sign(${num1})  = ${getSign(num1) > 0 ? "+" : ""}${getSign(num1)}`);
console.log(`sign(${num2}) = ${getSign(num2) > 0 ? "+" : ""}${getSign(num2)}`);
console.log(`sign(${num3})  = ${getSign(num3) > 0 ? "+" : ""}${getSign(num3)}`);

let a = 15;
let b = 9;

console.log("\n=== Branchless Minimum ===");
console.log(`min(${a}, ${b}) via bitmask:        ${minBranchless(a, b)}`);
console.log(`min(${a}, ${b}) via multiplication: ${minWithHelper(a, b)}`);