Programming Notes Fall 25

Bit Hacking

Removing Decision Statements

If you have a boolean (false == 0; true == 1) and you want to assign a variable based on its value,

let boolean_var = true;
let other;
if (boolean_var) {
    other = 123;
} else {
    other = 456;
}

You can do this without branching, assuming the other variable is an integer. Here’s an example in Rust:

// If flag == 0, then return a, if flag == 1, then return b.
// If flag > 1, result will be nonsense. 
fn a_or_b(a: u16, b: u16, flag: u16) -> u16 {
// if flag == 1, addition will overflow making `flag` all zeroes.
// if flag == 0, addition will do nothing, making `flag` all ones.
    let mask = u16::MAX.wrapping_add(flag);

// mask desired variable and throw away other
    (mask & a) | (!mask & b)
}

If instead you have a boolean where (false == 0; true != 0), the following tweak can be used:

fn a_or_b2(a: u16, b: u16, flag: u16) -> u16 {
    let flag = 1u16.wrapping_shr(flag as u32);
    let mask = u16::MAX.wrapping_add(flag);

    (mask & b) | (!mask & a)
}

According to Compiler Explorer, the following assembly is generated for the functions:

a_or_b:
        lea     eax, [rdx - 1]
        neg     edx
        and     edx, esi
        and     eax, edi
        or      eax, edx
        ret

a_or_b2:
        mov     ecx, edx
        and     ecx, 15
        mov     eax, 1
        shr     eax, cl
        test    ecx, ecx
        cmovne  ecx, esi
        neg     eax
        and     eax, edi
        or      eax, ecx
        ret