Branchless Algorithms

Branchless programming is the process of removing branches from code using only mathematical operators. This page will list multiple branchless algorithms as well as the operators needed for each. Normally branchless programming is used to speed up something by avoiding branching, but this page is not focused on performance. All code on this page will be written in Python.

All of these algorithms are total and so forth can be used in complex enough total programming languages. Most of these examples will consist of purely integer programming as it is more esoterically friendly, however some examples can use array and string operations if necessary.

Loops in Branchless Programming

In branchless programming, loops can often be "unrolled" that is to say, replaced with equivalent arithmetic expressions. This eliminates the branching part of looping constructs. Infinite loops can never be replaced with a total function but if you know the upper bound of a loop, and it is finite then it can always be replaced by a total function. For some of these longer algorithms a list of operators used will be shown.

Simple Example

Consider a basic loop:

a = 0
b = 10
for x in range(5):
    a += 2
    b -= 3

Instead of iterating, we can compute the total change directly:

a = 0
b = 10
a += 2 * 5   <!-- 2 added 5 times -->
b -= 3 * 5   <!-- 3 subtracted 5 times -->

This produces the same result without a loop.

Cumulative Example

Branchless programming becomes more powerful when the loop contains cumulative operations:

# Original loop
a = 0
b = 1
for x in range(1, 6):
    a += x      # cumulative sum
    b *= 2      # multiply by 2 each iteration

Unrolled using branchless arithmetic:

a = 0
b = 1
a += 5 * (5 + 1) // 2   # sum of first 5 numbers
b *= 2 ** 5             # multiplying by 2 five times

This replaces the loop entirely with mathematical formulas, making the code fully branchless.

Summary

Loop unrolling in branchless programming works by analyzing the cumulative effect of each iteration and expressing it as arithmetic expressions. This technique can be applied to addition, subtraction, multiplication, powers, and more complex cumulative operations.

Algorithms

Boolean functions

This will show you how to do Boolean functions, to replace branching conditionals with branchless ones.

NOT (Negation)

Not !

If A is either 0 or 1, this operation flips its value: 0 becomes 1, and 1 becomes 0.

A = 1 - A  # Flips the value of A

IF

If statements in branchless programming languages are best depicted as being like ternary operators.

variable = condition ? value_if_true : value_if_false;

Where the "value_if_false" is replaced with the original value of the variable so there is no change when the condition is ran.

Now you can't use that in branchless programming because that is using conditionals which is branching. So you can convert it into this instead

variable = ((condition==1)*(value_if_true))+((condition!=1)*(value_if_false))

AND

This will show two different versions of the AND && operator. One used for branchless conditionals and one used for simply getting the AND of a 2 Boolean integer values.

For the if statement we will use condition_a and condition_b it looks like

variable = (((condition_a+condition_b)==2)*(value_if_true))+(((condition_a+condition_b)!=2)*(value_if_false))

Now to simply get the AND value of 2 conditions you can just simplify it down to.

AND = ((condition_a+condition_b)==2)

OR

Now to finally demonstrate OR || it will follow the same format as showcasing AND.

The OR branchless conditional statement looks like this

variable = (((condition_a+condition_b)!=0)*(value_if_true))+(((condition_a+condition_b)==0)*(value_if_false))

Now to simply get the OR value of 2 conditions you can preform this.

OR = ((condition_a+condition_b)!=0)

Replacement of the == operator

Well what if you don't have == or !=. That is fine because you can recreate the == operator using simple math operators. The operators needed are *-//+. The algorithm goes like this

diff = a - b
is_equal = 1 - (2 * diff * diff) // (diff * diff + 1)

and to get != you can simply drop the 1 - at the start.

diff = a - b
is_not_equal = (2 * diff * diff) // (diff * diff + 1)

Print integer as a series of ASCII numbers

Operators used in this algorithm

+	‎ -‎ ‎	*	‎‎ / ‎	//	%	&	‎ |‎ ‎	^	~	<<	>>	&&	||	!	==	!=	<	>	<=	>=	min	max	abs
$\checkmark$		$\checkmark$		$\checkmark$								$\checkmark$	$\checkmark$	$\checkmark$

This program is useful in programming languages that allow you to print integer values as ASCII characters but does not directly allow for integer printing. This program can print up to 5 digits of a number. N is the number being printed

n = 1542

# precompute divisions
n1 = n // 10
n2 = n1 // 10
n3 = n2 // 10
n4 = n3 // 10

# digits to ASCII
a = (n4 % 10) + 48
b = (n3 % 10) + 48
c = (n2 % 10) + 48
d = (n1 % 10) + 48
e = (n  % 10) + 48

# length detection
L = (n  != 0) + (n1 != 0) + (n2 != 0) + (n3 != 0) + (n4 != 0)

# mask leading zeros
a = a*((L == 5))
b = b*((L == 5) + (L == 4))
c = c*((L == 5) + (L == 4) + (L == 3))
d = d*((L == 5) + (L == 4) + (L == 3) + (L == 2))

print(chr(a) + chr(b) + chr(c) + chr(d) + chr(e))

See also

• General blindfolded arithmetic
• Windmill
• Branchless Programming: Why "If" is Sloowww... and what we can do about it!, Creel