CODEWITHSUNDEEP
c
bdeonovic
bdeonovic

Reputation: 4220

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 );
   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

Upvotes: 2

Views: 2759

Answers (7)

Seth Carnegie
Seth Carnegie

Reputation: 75130

  1. The & operator, like the * operator1 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.

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

Upvotes: 4

Mourad
Mourad

Reputation: 404

& 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))

Upvotes: 1

John Humphreys
John Humphreys

Reputation: 39294

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.

Upvotes: 1

Whiskas
Whiskas

Reputation: 352

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

Upvotes: 0

carlpett
carlpett

Reputation: 12583

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.

Upvotes: 1

David Heffernan
David Heffernan

Reputation: 612954

Upvotes: 2

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272497

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.

Upvotes: 2

Related Questions