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'.
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.