1

I am a beginner to C language.I have a code for towers of hanoi but can someone explain me what are these bitwise operators doing ie if value of i is 1 what will be the source and target output value ?

source = (i & i-1) % 3;
target = ((i | i-1) + 1) % 3;
Govind Parmar
  • 20,656
  • 7
  • 53
  • 85
LOLprogrammer
  • 11
  • 1
  • do you understand what bitwise operators do, and just want to know what they are used for in this case, or do you want an explanation of bitwise operators? – CoffeeTableEspresso May 27 '19 at 18:09
  • i have some knowledge on bitwise operators but couldn't understand in this case.Yes i want explanation on working of bitwise operators in this case. – LOLprogrammer May 27 '19 at 18:18

3 Answers3

1

i & i-1 turns off the lowest set bit in i (if there are any set). For example, consider i=200:

  • 200 in binary is 1100 1000. (The space is inserted for visual convenience.)
  • To subtract one, the zeros cause us to “borrow” from the next position until we reach a one, producing 1100 0111. Note that, working from the right, all the zeros became ones, and the first one became a zero.
  • The & produces the bits that are set in both operands. Since i-1 changed all the bits up to the first one, those bits are clear in the &—none of the changed bits are the same in both i and i-1, so none of them is a one in both. The other ones in i, above the lowest one bit, are the same in both i and i-1, so they remain ones in i & i-1. The result of i & i-1 is 1100 0000.
  • 1100 0000 is 1100 1000 with the lowest set bit turned off.

Then the % 3 is selecting which pole in Towers of Hanoi to use as the source. This is discussed in this question.

Similarly i | i-1 turns on all the low zeros in i, all the zeros up to the lowest one bit. Then (i | i-1) + 1 adds one to that. The result is the same as adding one to the lowest one bit in i. That is, the result is i + x, where x is the lowest bit set in i. Using our example value:

  • i is 1100 1000 and i-1 is 1100 0111.
  • i | i-1 is 1100 1111.
  • (i | i-1) + 1 is 1101 0000, which equals 1100 1000 + 0000 1000.

And again, the % 3 selects a pole.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
0

A quick overview of bitwise operators:

Each operator takes the bits of both numbers and applies the operation to each bit of it.

& Bitwise AND

True only if both bits are true.

Truth table:

A | B | A & B
-------------
0 | 0 | 0
1 | 0 | 0
0 | 1 | 0
1 | 1 | 1

| Bitwise OR

True if either bit is true.

Truth table:

A | B | A | B
-------------
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 1

^ Bitwise XOR

True if only one bit is true.

Truth table:

A | B | A ^ B
-------------
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 0

~ Bitwise NOT

Inverts each bit. 1 -> 0, 0 -> 1. This is a unary operator.

Truth table:

A | ~A
------
0 | 1
1 | 0

In your case, if i = 1, the expressions would be evaluated as:

source = (1 & 1-1) % 3;
target = ((1 | 1-1) + 1) % 3;
// =>
source = (1 & 0) % 3;
target = ((1 | 0) + 1) % 3;
// =>
source = 0 % 3;
target = (1 + 1) % 3;
// =>
source = 0;
target = 2 % 3;
// =>
source = 0;
target = 2;
uanirudhx
  • 196
  • 1
  • 6
0

Good answer above, here is a high-level approach:

i == 1: source: (1 & 0). Are both of these values true or >= 1? No they are not. So the overall result is 0, 0 % 3 = 0.

target: ((1 | 0) + 1) % 3. (1 | 0) evaluates to 1(true) since one of the two values on the sides of the | operator are 1, so now we have (1 + 1). so then it follows we have 2 % 3 = 2.

Source: 0, target: 2

clocksw
  • 68
  • 5