3

К примеру есть участки кода, подобные этим:

d[1 << i][i] = 1;

if (!((mask >> j) & 1) && g[i][j])
    d[mask ^ (1 << j)][j] += d[mask][i];

Что означают вот эти знаки >>, <<, ^, & ?

И где можно почитать литературу про подобное?

И как это применяется в олимпиадных задачах?

1
  • Это бинарные операторы, работа с байтами. В данном случае это сдвиг влево или в право. Можно почитать в любой книге по СИ, тут есть примеры с таблицами radio-blogs.ru/blog/mikrokontrollery/…
    – Павел
    2 мар 2019 в 9:13

3 ответа 3

11

где почитать:

в абсолютно любой книге по с/с++ в первых главах, где описываются арифметические и логические операции. >> называется "оператор сдвига влево". << называется "оператор сдвига вправо". ^ называется "исключающее или". Если в книге этого нет, выкидывайте такую книгу.

где применяется

Операторы сдвига применяют в "олимпиадных задачах" для быстрого умножения/деления на степени двойки (и не только). Но современные компиляторы часто сами могут это сделать не хуже.

А еще операторы сдвига в С++ являются перегруженными операторами для некоторых классов. Например для cout и cin и позволяют делать ввод-вывод более "человечным".

К примеру конструкция 1 << i очень популярна, если нужно получать степени двойки (очень быстро). 1 << 2 = 4 = 2 в степени 2, 1 << n = 2 в степени n.

1
  • 3
    Операторы сдвига применяются для выполнения умножения на степени двойки тогода, когда множитель является run-time значением, т.е. компилятор не может знать, что это степень двойки. Если же множитель - константа времени компиляции, то замена такого умножения на сдвиг - яркий пример "пионэрской оптимизации" в наивном студенческом коде, от которой нет никакой пользы и в которой нет никакого смысла. 30 мар 2017 в 6:52
11

Попробую объяснить немного неформально, что означает << и >>. Например у нас есть такой код:

#include <stdio.h>

main ()
{
  char a = 5 << 2;
  printf("%d\n", a);
}

У нас есть число 5 в десятичной системе счисления. Если его перевести в двоичную, будет: 0000 0101. Теперь берём и "сдвигаем" это двоичное представление влево на 2 позиции, добавляя справа нули: 0001 0100. А теперь переведём обратно получившееся двоичное число в десятичную систему счисления: 20. Если скомпилировать данный код и запустить, будет выведено: 20. Аналогично и для операции >>, только сдвиг вправо.

4

Это бинарные операторы.

<< >> - Операторы сдвига.

& - Побитовое "И"

| - Побитовое "ИЛИ"

^ - Исключающее "ИЛИ"

~ - Оператор дополнения.

Подробнее об бинарных операторах и операциях можно почитать тут: Habrahabr.ru - Очень доступно описано.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.