Практика языка C (МФТИ, 2023-2024). Семинар 2.2. Побитовые вычисления.

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.

Весь этот семинар посвящён работе с отдельными битами. Мы начнём с мотивирующего примера решета с побитовым хранением признаков и разберем многие интересные битовые трюки и техники.

Семинарист: Константин Владимиров.
Дата: 29 сентября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.

Timeline
00:00 Неэкономичность решета
08:50 Побитовые операции
13:45 Практика вычислений
33:00 Манипуляции с битами
41:47 Время решать задачи
50:49 popcount и 2-адические числа
56:44 Интересные трюки
01:07:14 Ковры
01:14:23 Ревью заданий и завершение

Errata:
* когда решали примеры с битовыми операциями, в последнем ответ не 0x8c, а 0x30
* 41:47 опечатка, ответ должен быть 28 1
* 10100 ^ 0хFF = 11101011, на слайде не сделана операция для лидирующих нулей.

[alex_s_ciframi]

спасибо за лекцию! Про ковры шикарно, можно делать уникальные для фона фотографий :D

[MikhailGoncharov-tlcr]

я никогда не слышал о том что между числами возможно делать логические операции вот это шедевр

[neromoonnn]

41:47 очепятка, ответ должен быть 28 1

[ДенисСомин]

Отличный семинар, спасибо огромное, хотелось бы побольше битовых хаков посмотреть, я же смогу их в трёхтомнике Кнута найти?
По поводу опечаток, когда решали примеры с битовыми операциями, в последнем ответ не 0x8c (это вы на 2 бита сдвинули), а 0x30

[voffkaopera]

Были ли у вас ситуация когда надо было применять GOTO ?

[smolewood]

Спасибо за ликбез. Единственно не понял, зачем при манипуляции с битами, что бы узнать единица или ноль в конкретном бите, сдвигать вправо все биты? Если мы применили маску с побитовым "И" к искомому биту, то обычная проверка итогового числа (на > 0) покажет ноль там или единица .

[EugeneS-RU]

сколько ни стараюсь, не могу быстро и в уме оперировать числами в системах, отличных от десятичной :(

[anton.]

если сделать не 2 массива, а 4 для чисел оканчивающихся на 1, 3, 7 и 9, то можно исключить цифры с окончанием 5. Они как и четные не будут простыми. И арифметика ни сколько не усложнится.

[orion_]

Мне кажется, что на 54 слайде в расчётах последней строки допущена ошибка: я уже несколько раз пересчитал результат выражения 𝑥 = 1, 𝑥 = 1 − 69 & 69 и у меня получается 4, а не 9

[Zelourses]

53:59 — Константин, подскажите, где можно почитать про трюки, представленные с p-адическими числами, поскольку своими рукомахательствами я не смог получить вменяемого, как на слайде, результата, а гугление не особо помогает (Конкретно не очень понятно, откуда при раскрытии скобок получается +1)

[dominatormercurial]

Доброго времени суток! Контесты на данный момент недоступны, подскажите, пожалуйста, это временно или их отключили на совсем?

[stanislavstanislavius]

Почему 10100 ^ 0хFF = 1011?
Разве не должен быть ответ равен 11101011?

[DIY_PLC]

#include <iso646.h> можно применять?

[gdygdy]

Проблема в том, что сдвиг на 8*sizeof(int) -- это UB.
Сдвиг инта вправо не создаёт никаких проблем сам по себе.

[stanislavstanislavius]

Константин, а как вы относитесь к компилятору pelles c?

[EvgenyChannel]

0x23 << 4 Конечно 0x230 Что-то или студенты не очень, или Вы их подавляете своим авторитетом