program.c

/*
 * Branchless Programming Examples in C
 *
 * "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.
 *
 * KEY CONCEPT — Arithmetic Right Shift (>>):
 *   In C, shifting a signed negative integer right fills with 1s (the sign bit).
 *   This is called "arithmetic right shift" and is implementation-defined in C,
 *   but works this way on virtually all modern compilers/platforms.
 *
 *     42 >> 31  →  0x00000000  →  0   (positive: filled with 0s)
 *     -7 >> 31  →  0xFFFFFFFF  → -1   (negative: filled with 1s)
 *      0 >> 31  →  0x00000000  →  0
 */

#include <stdio.h>

/*
 * 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 them with subtraction.
 *
 * WORKED EXAMPLE (num = -7, 32-bit signed integer):
 *
 *   Step 1: isNegative
 *     -7 in binary:  11111111 11111111 11111111 11111001
 *     >> 31:         11111111 11111111 11111111 11111111  = -1 (all 1s)
 *     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: Result
 *     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
 *     Result: 0 - 0 = 0  ✓
 *
 * NOTE: -INT_MIN is undefined behavior in C. This function works for all
 *       32-bit signed integers EXCEPT INT_MIN (-2147483648).
 */
int getSign(int num) {
    int isNegative = -(num >> 31);    /* 1 if num < 0, else 0 */
    int isPositive = -((-num) >> 31); /* 1 if num > 0, else 0 */
    return isPositive - isNegative;
}

/*
 * minBranchless — Returns the smaller of two integers.
 *
 * TRICK: We compute (a - b), then use its sign bit as a mask.
 *   - If a < b, then (a - b) is negative → sign bit = 1 → mask = 0xFFFFFFFF (-1)
 *   - If a >= b, then (a - b) is non-negative → sign bit = 0 → mask = 0x00000000 (0)
 *
 * The formula is:  min = b + (diff & mask)
 *   - When a < b:  mask = -1 (all 1s), so (diff & mask) = diff = (a - b)
 *                  b + (a - b) = a  ✓  (a is the smaller one)
 *   - When a >= b: mask = 0, so (diff & mask) = 0
 *                  b + 0 = b  ✓  (b is the smaller one)
 *
 * WORKED EXAMPLE (a=15, b=9):
 *     diff = 15 - 9 = 6
 *     6 in binary:     00000000 00000000 00000000 00000110
 *     >> 31:           00000000 00000000 00000000 00000000  = 0 (mask)
 *     diff & 0 = 0
 *     b + 0 = 9  ✓
 *
 * WORKED EXAMPLE (a=3, b=7):
 *     diff = 3 - 7 = -4
 *     -4 in binary:    11111111 11111111 11111111 11111100
 *     >> 31:           11111111 11111111 11111111 11111111  = -1 (mask)
 *     diff & (-1) = -4   (AND with all 1s keeps the value unchanged)
 *     b + (-4) = 7 + (-4) = 3  ✓
 *
 * WARNING: Overflows if (a - b) exceeds 32-bit range. For production use,
 *          consider wider intermediate types or a different approach.
 */
int minBranchless(int a, int b) {
    int diff = a - b;
    int mask = diff >> 31; /* 0 if a >= b, -1 if a < b */
    return b + (diff & mask);
}

/*
 * minWithHelper — An alternative branchless min using multiplication.
 *
 * IDEA: Instead of bit masking, we multiply by 0 or 1 to "select" a value.
 *
 *   isSmaller = 1 when a < b, 0 otherwise
 *   result = a + (b - a) * isSmaller
 *
 *   When a < b:  a + (b - a) * 1 = a + b - a = b  ... wait, that gives b!
 *   Actually:    a + (b - a) * isSmaller(b, a) ... let me re-examine.
 *
 *   We need: if a < b, return a. So we want to ADD NOTHING when a < b.
 *   Rephrased: result = a + (b - a) * isSmaller(b, a)
 *   Or equivalently: if a IS the smaller, select a; else select b.
 *
 *   isASmaller = (a < b) → 1 or 0
 *   result = a * isASmaller + b * (1 - isASmaller)
 *
 *   But the code below uses a terser form:
 *     result = a + (b - a) * (1 - isSmaller(a, b))
 *            = a + (b - a) * isBSmallerOrEqual
 *   Hmm, let me just trace the actual formula used:
 *
 *     return a + (b - a) * isSmaller(b, a)
 *
 *   a=15, b=9: isSmaller(9, 15) = 1 → a + (b - a) * 1 = 15 + (9-15) = 15 - 6 = 9  ✓
 *   a=3, b=7:  isSmaller(7, 3)  = 0 → a + (b - a) * 0 = 3 + 0 = 3  ✓
 */
int isSmaller(int a, int b) {
    /* In C, (a - b) < 0 compiles to a comparison that returns 0 or 1.
     * On most architectures, this uses a SETcc instruction — no branch. */
    return (a - b) < 0;
}

int minWithHelper(int a, int b) {
    /* Multiply (b - a) by 1 if b < a (so we subtract to get b),
     * or by 0 if b >= a (so we keep a). */
    return a + (b - a) * isSmaller(b, a);
}

int main() {
    /* --- Sign detection --- */
    int num1 = 42;
    int num2 = -7;
    int num3 = 0;

    printf("=== Branchless Sign Detection ===\n");
    printf("sign(%d)  = %+d\n", num1, getSign(num1));   /* +1 */
    printf("sign(%d) = %+d\n", num2, getSign(num2));     /* -1 */
    printf("sign(%d)  = %+d\n", num3, getSign(num3));    /*  0 */

    /* --- Minimum --- */
    int a = 15, b = 9;

    printf("\n=== Branchless Minimum ===\n");
    printf("min(%d, %d) via bitmask:        %d\n", a, b, minBranchless(a, b));
    printf("min(%d, %d) via multiplication: %d\n", a, b, minWithHelper(a, b));

    return 0;
}