understanding some C code

Quick question. I've never had experience with C.

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int n, x;
   printf( "How many disks? " );
   scanf( "%d", &n )开发者_如何学JAVA;
   printf("\n");
   for (x=1; x < (1 << n); x++)
      printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
    return 0;
}

This is an iterative tower of hanoi. What do things like (x&x-1) and (x|x-1)+1 mean? I figure the % is doing modulus. and %i is a way of printing out integers in C?

Thanks

---

1. The & operator, like the * operator¹ can be used for two different things depending on whether it's used as a binary or unary operator.
   1. Unary & like &var takes the address of var. This is necessary to pass it to scanf.
   2. Binary & like var & var is a bitwise AND, like item #2.
      • Notice that the spacing doesn't matter. What does matter is if there's operands on both sides of the &. So & var is still unary & and var &var is still binary &.
2. (x&x-1) is doing a bitwise AND with x and x-1.
3. (x|x-1) is doing a bitwise OR with x and x-1.
4. Yes % means modulus.
5. 1 << n is doing a bitwise shift of 1 to the left n digits
6. the %i you are seeing as the first argument to printf are format symbols to which specify that the next argument is an int, so that printf can print it properly (because it doesn't know what type it is by itself, so you have to tell it). It has nothing to do with modulus. You can see a very in-depth definition of printf here: http://pubs.opengroup.org/onlinepubs/9699919799/ (thanks pmg)
   • If %i were outside a string, it would be to the left of some other operand, and mean modulus.
   • %i in a string doesn't mean anything by itself. It only means something to printf because printf treats it specially. It searches the string it gets for occurrences of %format (where format is a format, not the word "format") and does something depending on what format it encounters.

¹ The * operator also has two different versions: a unary version and a binary version. The unary version means pointer indirection, and the binary version means multiplication.

---

What do things like (x&x-1) and (x|x-1)+1 mean?

(x&x-1) is equivalent to (x & (x-1)). & is the bitwise-AND operator. Similarly for the second example, where | is the bitwise-OR operator.

I figure the % is doing modulus.

Yes.

and %i is a way of printing out integers in C?

Yes.

---

• | is bitwise OR.
• & is bitwise AND.
• << is bitwise shift.
• % is modulus.
• %i format string prints an integer.

---

printf is a formatted output function, in which %i means that the argument is an integer. More information is availible here for instance.

The % operator is indeed modulus. & is bitwise AND, and | is bitwise OR.

---

The line:

for (x=1; x < (1 << n); x++)

initializes x to 1 and repeats/iterates until x < (1 left shifted by n). The left shift basically moves the binary representation of 1 left n binary spaces. so, 0001 would be 0010 after left shifting 1 - this is similar to multiplying by 2^n. x is then increased by 1 (x++). Eventually the increase of x should eventually cause the loop to terminate due to the x < (1 << n) condition.

(x&x-1)%3

Says "The remainder of value x (binary and) value x-1 divided by 3. So, if x is 4, and we're using a 4 bit number (stupid, I know - but it shows the point):

0100 &
0011
_______
0000        (binary and means both spots being added are 1, none are here).

= 0
0/3 = 0 R 0 - no remainder here, so print 0.

The next statement:

(x|x-1)+1)%3

Says x (binary or) x-1, with 1 added to that value. The whole sum there is modded by 3 which is again diving it by 3 and taking the remainder, so if x is 4 again and we're using 4 bit integers:

0100 |
0011
_______
0111    (Binary or means either binary number has a 1 in that slot).

= 4 + 2 + 1 = 7 --> 7 mod 3 = 7 / 3 --> 2 R 1, print  remainder of 1 here.

printf allows formatted print out of a variable length list of arguments which can be expressions, so here it will print:

move from tower 0 to tower 1 <new line>

Replacing the %i's with our answers.

---

& and | are bitwise operators (respectively, AND and OR operators).

  0101 (decimal 5)
& 0011 (decimal 3)
------
= 0001 (decimal 1)


  0101 (decimal 5)
| 0011 (decimal 3)
------
= 0111 (decimal 7)

Since the substraction operator's precedence is higher than bitwise operators' precedence :

(x&x-1) = (x&(x-1)) 
(x|x-1) = (x|(x-1))

---

More informations : http://en.wikipedia.org/wiki/Boolean_algebra