Set or reset a given bit without branching

Question

in one interview they asked me: how do you install or reset a bit? This is a very simple question, and I answered that.

After that they asked me, do it without branching . I do not know what branching is. I am looking for this and I came here http://graphics.stanford.edu/~seander/bithacks.html

But so far, the concept of branching and non-branching has not worked out. Please explain Branching .

Answer 1

Branching means that instructions executed by the processor contain a conditional branch. Or - or a choice. This may mean if , a for -loop, while -loop, switch , ?: Or something that makes a decision based on a logical one.

One class of branches that people often forget is also a short-circuited Boolean operator and possibly (but not necessarily on all CPUs) things that evaluate truth values, so int foo; ...; foo = !foo; int foo; ...; foo = !foo; will be a branch on some processors, but not all (not on x86).

So, to set the bit:

 i |= (1 << bit); 

Reset Bit:

 i &= ~(1 << bit); 

Toggle Bit:

 i ^= (1 << bit); 

There are no branches. In fact, I don’t see how to make it so complicated that I need to use a branch.

The reason someone might worry about branches is branch prediction. See this question and answer for a great explanation of why this is important.

Answer 2

Maybe they wanted you to show how to write a common set / reset fragment without branches ...

This can be done using

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

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

Something a little more general:

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

which 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 change several value bits to

• aj=0 , xj=0 → setting them to 0
• aj=0 , xj=1 → setting them to 1
• aj=1 , xj=0 → leave them untouched
• aj=1 , xj=1 → flip them

depending on the previously calculated constants a and x ( aj and xj is the value of the jth bit in constants).

for instance

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

with one operation will be

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