What does 'branching' mean in terms of setting/resetting bits?

Question

In an interview, I was asked "How do you set or reset a bit?" This is a very simple question, and I answered it.

After that, they asked me how to do the same thing, but without branching. I don't know what branching is.

I search and found Bit Twiddling Hacks by Sean Eron Anderson, but I'm still not getting concept of branching and non-branching.

Please explain 'branching'.

Answer 1

In short, a branch instruction is something like:

If the result of the last operation was zero/non-zero/overflow/underflow/compared smaller/compared bigger/etc. (there are lots of different conditions that can be tested), then jump to that instruction over there, otherwise keep executing here.

Almost all CPUs have branch instructions, and the concept is more or less the same across them all. Branching means that the instructions the CPU executes contain a conditional jump. An either-or choice. Which could mean an if, a for-loop, while-loop, switch, ?: or something that makes a decision based on a boolean.

One class of branches that people often forget are also short-circuiting boolean operators and possibly (but not necessarily on all CPUs) things that evaluate to truth values, so int foo; ...; foo = !foo; will be a branch on some CPUs, but not all (not on x86).

So to set a bit:

i |= (1 << bit);

Reset a bit:

i &= ~(1 << bit);

Toggle a bit:

i ^= (1 << bit);

No branches. I actually don't see how to make this so complicated to have to use a branch.

The reason why someone might want to worry about branches is branch prediction. See this Stack Overflow answer on branch prediction failure for an excellent explanation of why that matters.

Answer 2

Maybe they wanted you to show how to write a generic set/reset snippet without branches.

This could be accomplished with

value = (value & ~(1 << bit)) | (bitval << bit);

where bit is the bit position and bitval is 1 for set and 0 for reset.

Something even slightly more general is the following:

value = (value & ~(k1 << bit)) ^ (k2 << bit);

that implements several operations:

• k1=0 and k2=0 does nothing
• k1=0 and k2=1 toggles the bit
• k1=1 and k2=0 clears the bit
• k1=1 and k2=1 sets the bit

More generally with

value = (value & a) ^ x;

you can decide to change several bits of value at the same time by

• aj=0, xj=0 → setting them to 0
• aj=0, xj=1 → setting them to 1
• aj=1, xj=0 → leaving them untouched
• aj=1, xj=1 → flipping them

depending on the pre-computed constants a and x (aj and xj are the value of the j-th bit in the constants).

For example

value = (value & 0x0F) ^ 0x3C;

with a single operation will

- leave untouched bit 0 and 1
- flip bits 2 and 3
- set to 1 bits 4 and 5
- set to 0 all other bits