9

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.

someone
  • 1,638
  • 3
  • 21
  • 36
  • 4
    My counter-question would be: How the hell do you set or reset a bit with branching? – Art Jul 23 '13 at 07:30
  • By "set or reset" do they mean toggle? You can do that with an xor. – Matthew Mellott Jul 23 '13 at 07:32
  • @Art...I know nothing about branching...Simply I can do bit manipulation and set or reset a bit... I want to know what is branching? – someone Jul 23 '13 at 07:33
  • + I do not know how does setting or resetting a bit have to do with braching. Want to know that from this qustion. – lulyon Jul 23 '13 at 07:33
  • @MatthewMellott... if the bit is `0` then make it `1`.just once. – someone Jul 23 '13 at 07:34
  • @Krishna: If the bit is 0, make it 1; Else if the bit is 1, make it 0? That would be a toggle. If that is not what they were asking for them I'm confused. – Matthew Mellott Jul 23 '13 at 07:36
  • @MatthewMellott... Not toggle. Let I have a number 32 . make the third bit set. this is the question. – someone Jul 23 '13 at 07:39
  • possible duplicate of [How do you set, clear and toggle a single bit in C?](http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c) – devnull Jul 23 '13 at 07:41
  • @devnull... My question is about branching. I didnt ask here how to set, reset or togle a bit. – someone Jul 23 '13 at 07:43

2 Answers2

16

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
6502
  • 112,025
  • 15
  • 165
  • 265
14

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 question and answer for an excellent explanation of why it matters.

Community
  • 1
  • 1
Art
  • 19,807
  • 1
  • 34
  • 60
  • toggle : `i ^= (1 << bit);` – Matthew Mellott Jul 23 '13 at 07:36
  • @Art... Is it related to x86 programming? Sorry if my question is wrong. – someone Jul 23 '13 at 07:37
  • No, this is general programming. All (unless you go to some really esoteric stuff) CPUs have branch instructions and the concept of branching is more or less the same across all of them. – Art Jul 23 '13 at 07:38
  • @Art... Thanks... Now I`ll search for CPU branch instructions. What they are and how they`ll work? – someone Jul 23 '13 at 07:42
  • 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. – Art Jul 23 '13 at 07:46
  • @Art...Ohhh this is so simple explanation...really good. Now I understand the logic. – someone Jul 23 '13 at 07:48