Практика языка C (МФТИ, 2023-2024). Семинар 2.2. Побитовые вычисления.
Вставка
- Опубліковано 13 чер 2024
- Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
Весь этот семинар посвящён работе с отдельными битами. Мы начнём с мотивирующего примера решета с побитовым хранением признаков и разберем многие интересные битовые трюки и техники.
Семинарист: Константин Владимиров.
Дата: 29 сентября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
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, на слайде не сделана операция для лидирующих нулей.
Просто нереально класний викладач!
спасибо за лекцию! Про ковры шикарно, можно делать уникальные для фона фотографий :D
41:47 очепятка, ответ должен быть 28 1
Отличный семинар, спасибо огромное, хотелось бы побольше битовых хаков посмотреть, я же смогу их в трёхтомнике Кнута найти?
По поводу опечаток, когда решали примеры с битовыми операциями, в последнем ответ не 0x8c (это вы на 2 бита сдвинули), а 0x30
В четырёхтомнике ))
Все примеры из тома 4а.
Да, спасибо за внимательность, сдвинул не на то число.
@@tilir понял, ещё раз спасибо!
Алгоритмические трюки для программистов
2-е издание
Генри С. Уоррен
Hacker's Delight, 2nd Edition
Henry S. Warren
Тоже хорошая книжка но по сравнению с 4А Кнута несколько поверхностная. Кнут вскрывает основы трюков и учит вас делать свои.
Мне кажется, что на 54 слайде в расчётах последней строки допущена ошибка: я уже несколько раз пересчитал результат выражения 𝑥 = 1, 𝑥 = 1 − 69 & 69 и у меня получается 4, а не 9
сколько ни стараюсь, не могу быстро и в уме оперировать числами в системах, отличных от десятичной :(
53:59 - Константин, подскажите, где можно почитать про трюки, представленные с p-адическими числами, поскольку своими рукомахательствами я не смог получить вменяемого, как на слайде, результата, а гугление не особо помогает (Конкретно не очень понятно, откуда при раскрытии скобок получается +1)
Кнут, TAOCP, том 4а.
Были ли у вас ситуация когда надо было применять GOTO ?
В жизни да конечно. В этом курсе к счастью пока нет, но я про goto обязательно расскажу позднее.
#include можно применять?
Для начинающих я бы не советовал.
если сделать не 2 массива, а 4 для чисел оканчивающихся на 1,3,7 и 9, то можно исключить цифры с окончанием 5. Они как и четные не будут простыми. И арифметика ни сколько не усложнится.
Спасибо за ликбез. Единственно не понял, зачем при манипуляции с битами, что бы узнать единица или ноль в конкретном бите, сдвигать вправо все биты? Если мы применили маску с побитовым "И" к искомому биту, то обычная проверка итогового числа (на > 0) покажет ноль там или единица .
Сравнить с нулём не дешевле чем сдвинуть вправо. Но тоже вполне возможный вариант.
Константин, а как вы относитесь к компилятору pelles c?
Ну примерно как к tinyc, localc и прочим наколенным поделкам. Оптимизирующим компилятором это не является, но как игра -- почему нет.
@@tilir мы в универе, на первом курсе на нем писали программы на c)
@@stanislavstanislavius7618 не вижу в этом ничего плохого. Главное понимать что это не индустриальный стандарт. А для обучения -- не хуже чего угодно. Хотя я предпочитаю учить сразу на gcc.
@@tilir это да), теперь и я на gcc, а также godbolt)
Почему 10100 ^ 0хFF = 1011?
Разве не должен быть ответ равен 11101011?
Да действительно я не сделал операцию для лидирующих нулей. Надо внести в errata.
42:10 наверно Выход будет 28 и 1 ?
да, можно на калькуляторе проверить
ua-cam.com/video/ZizuOhdl5oA/v-deo.htmlsi=9XAUWA0anhg_YIK1&t=4616
Проблема в том, что сдвиг на 8*sizeof(int) -- это UB.
Сдвиг инта вправо не создаёт никаких проблем сам по себе.
Да, но я пока не вводил термина UB. У меня будет насчёт этого отдельное занятие.
0x23