понимание некоторого кода C

Question

Быстрый вопрос. У меня никогда не было опыта работы с 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;
}

Это итерационная башня Ханоя. Что означают такие вещи, как (x & x-1) и (x | x-1) +1? Я считаю, что% делает модуль. а% i это способ распечатки целых чисел в C?

Спасибо

Answer 1

1. Оператор &, такой как оператор * ¹ , может использоваться для двух разных целей в зависимости от того, используется ли он как бинарный или унарный оператор.
   1. Унарный &, как &var, принимает адрес var. Это необходимо, чтобы передать его scanf.
   2. Binary & как var & var является побитовым AND, как элемент # 2.
      • Обратите внимание, что расстояние не имеет значения. Имеет значение то, есть ли операнды с обеих сторон &. Таким образом, & var все еще остается одинарным &, а var &var все еще является двоичным &.
2. (x&x-1) выполняет побитовое И с x и x-1.
3. (x|x-1) выполняет побитовое ИЛИ с x и x-1.
4. Да % означает модуль.
5. 1 << n выполняет битовое смещение 1 влево n цифр
6. %i, который вы видите в качестве первого аргумента для printf, являются символами формата, для которых указывается, что следующим аргументом является int, так что printf может его правильно распечатать (потому что он не знает какой это тип сам по себе, так что вы должны сказать это). Это не имеет ничего общего с модулем. Вы можете увидеть очень подробное определение printf здесь: http://pubs.opengroup.org/onlinepubs/9699919799/ (спасибо, pmg)
   • Если бы %i находилось вне строки, он был бы слева от какого-то другого операнда и означал бы модуль.
   • %i в строке ничего не значит само по себе. Это означает что-то только для printf, потому что printf относится к этому специально. Он ищет строку, которую получает, для вхождений %format (где format - это формат, а не слово «формат») и делает что-то в зависимости от того, в каком формате он встречается.

¹ Оператор * также имеет две разные версии: унарная версия и бинарная версия. Унарная версия означает косвенность указателя, а двоичная версия означает умножение.

Answer 2

• | равно поразрядно ИЛИ .
• & - это поразрядно И .
• << - это битовый сдвиг .
• % - модуль.
• %i строка формата печатает целое число.

Answer 3

Что означают такие вещи, как (x & x-1) и (x | x-1) +1?

(x&x-1) эквивалентно (x & (x-1)).& - это оператор побитовое-И .Аналогично для второго примера, где | является оператором побитового ИЛИ .

Я считаю, что% выполняет модуль.

Да .

и% i - это способ вывода целых чисел в C?

Да .

Answer 4

& и | - побитовые операторы (соответственно, операторы AND и OR).

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


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

Поскольку приоритет оператора вычитания выше, чем приоритет битовых операторов:

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

Answer 5

Строка:

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

инициализирует x в 1 и повторяется / повторяется до x <(1 сдвинут влево на n).Сдвиг влево в основном перемещает двоичное представление 1 левого n двоичных пространств.Итак, 0001 будет 0010 после сдвига влево на 1 - это похоже на умножение на 2 ^ n.х затем увеличивается на 1 (х ++).В конечном итоге увеличение x должно в конечном итоге привести к прекращению цикла из-за условия x <(1 << n). </p>

(x&x-1)%3

говорит "Остаток значения x (двоичное и) значение x-1 разделенона 3. Итак, если x равен 4, и мы используем 4-битное число (глупо, я знаю, но оно показывает смысл):

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.

Следующее утверждение:

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

Говорит x (двоичный или) x-1, с добавленным к этому значению значением 1. Вся сумма там модифицируется на 3, что снова погружает ее на 3 и берет остаток, поэтому, если x снова равно 4, и мыИспользование 4-битных целых чисел:

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 позволяет форматировать печать из списка аргументов переменной длины, которые могут быть выражениями, поэтому здесь будет напечатано:

move from tower 0 to tower 1 <new line>

Замена%я с нашими ответами.

Answer 6

printf - это форматированная функция вывода, в которой %i означает, что аргумент является целым числом.Более подробная информация доступна, например, здесь .

Оператор % действительно является модулем.& - побитовое И, а | - побитовое ИЛИ.

Answer 7

Больше информации: http://en.wikipedia.org/wiki/Boolean_algebra