Set or Reset a given bit without branching

Question

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

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

But still not getting concept of branching and non-branching. Please explain Branching.

Answer 1

May be 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 precomputed 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