Приветственный пост
Рады приветствовать всех на нашем канале!
Вы устали от скучного, монотонного, обезличенного контента по плюсам?
Тогда мы идем к вам!
Здесь не будет бесполезных 30 IQ постов, сгенеренных ChatGPT, накрученных подписчиков и активности.
Канал ведут два сеньора, Денис и Владимир, которые искренне хотят делится своими знаниями по С++ и создать самое уютное коммьюнити позитивных прогеров в телеге!
(ну вы поняли, да? с++, плюс плюс, плюс типа
позитивный?.. ай ладно)
Жмакай и попадешь в наш чат. Там обсуждения не привязаны к постам, можете общаться на любые темы.
Материалы для новичка
ГАЙДЫ:
Мини-гайд по собеседованиям
Гайд по тестовым заданиям
Гайд по категория выражения и мув-семантике
Гайд по inline
Дальше пойдет список хэштегов, которыми вы можете пользоваться для более удобной навигации по каналу и для быстрого поиска группы постов по интересующей теме:
#algorithms
#datastructures
#cppcore
#stl
#goodoldc
#cpp11
#cpp14
#cpp17
#cpp20
#commercial
#net
#database
#hardcore
#memory
#goodpractice
#howitworks
#NONSTANDARD
#interview
#digest
#OS
#tools
#optimization
#performance
#fun
#compiler
#multitasking
#design
#exception
#guide
#задачки
#base
#quiz
#concurrency
#ЧЗХ
#ревью
Рады приветствовать всех на нашем канале!
Вы устали от скучного, монотонного, обезличенного контента по плюсам?
Тогда мы идем к вам!
Здесь не будет бесполезных 30 IQ постов, сгенеренных ChatGPT, накрученных подписчиков и активности.
Канал ведут два сеньора, Денис и Владимир, которые искренне хотят делится своими знаниями по С++ и создать самое уютное коммьюнити позитивных прогеров в телеге!
(ну вы поняли, да? с++, плюс плюс, плюс типа
позитивный?.. ай ладно)
Жмакай и попадешь в наш чат. Там обсуждения не привязаны к постам, можете общаться на любые темы.
Материалы для новичка
ГАЙДЫ:
Мини-гайд по собеседованиям
Гайд по тестовым заданиям
Гайд по категория выражения и мув-семантике
Гайд по inline
Дальше пойдет список хэштегов, которыми вы можете пользоваться для более удобной навигации по каналу и для быстрого поиска группы постов по интересующей теме:
#algorithms
#datastructures
#cppcore
#stl
#goodoldc
#cpp11
#cpp14
#cpp17
#cpp20
#commercial
#net
#database
#hardcore
#memory
#goodpractice
#howitworks
#NONSTANDARD
#interview
#digest
#OS
#tools
#optimization
#performance
#fun
#compiler
#multitasking
#design
#exception
#guide
#задачки
#base
#quiz
#concurrency
#ЧЗХ
#ревью
Telegram
Грокаем C++ Chat
You’ve been invited to join this group on Telegram.
🔥36❤18👍15🤔2🐳1
Знак-амплитуда
Начнем раскрывать тему вариантов представления отрицательных чисел с метода "знак-величина" или sign-magnitude. Это самый интуитивно понятный для нас способ репрезентации целых чисел. В обычной математике как: есть грубо говоря модуль числа и его знак.
И это довольно просто перенести в память. Мы просто обговариваем, что наиболее значимый бит числа мы отводим по бит знака, а остальные биты обозначают модуль числа. Если знаковый бит - 0, значит число положительное. Если 1 - отрицательное. Таким образом получается вполне естественная ассоциация с привычными нам правилами. Есть натуральный ряд чисел плюс ноль. Чтобы получить множество всех целых чисел, нужно ко множеству натуральных чисел прибавить множество чисел, которое получается из натуральных путем добавления минуса в начале числа.
Давайте на примере. В восьмибитном числе только 7 бит будут описывать модуль числа, который может находится в отрезке [0, 127]. А самый старший бит будет отведен для знака. С добавлением знака мы теперь может кодировать все числа от -127 до 127. Так, число -43 будет выглядеть как 10101011, в то время как 43 будет выглядеть как 00101011. Однако очень внимательные читатели уже догадались, что эта форма представления отрицательных чисел имеет некоторые side-effect'ы, которые усложняют внедрение этого способа в реальные архитектуры:
1️⃣ Появление двух способов изображения нуля: 00000000 и 10000000.
2️⃣ Представление числа из определения разбивается на 2 части, каждая из которых должна иметься в виду и каким-то образом обрабатываться.
3️⃣ Из предыдущего пункта выходит, что операции сложения и вычитания чисел с таким представлением требуют разной логики в зависимости от знакового бита. Мы должны в начале "отрезать" знаковый бит, сделать операцию, которая соответствует комбинации знаковых битов операндов и первоначальной операции, и потом обратно совместить результат со знаком.
4️⃣ Раз у нас 2 нуля, мы можем представлять на 1 число меньше, чем могли бы в идеале.
В общем, минусы значительные. И хоть такое представление и использовалось в ранних компьютерах из-за интуитивной понятности для инженеров, однако в наше время этот способ представления знаковых целых чисел практически не используется.
Однако "знак-величина" используется по сей день, но немного для другого. IEEE floating point использует этот метод для отображения мантиссы числа. Есть модуль мантиссы(ее абсолютное значение) и есть ее знаковый бит. Кстати поэтому у нас есть положительные и отрицательные нули, бесконечности и NaN'ы во флотах. Вот как оно оказывается работает.
Apply yourself in the proper place. Stay cool.
#cppcore #base
Начнем раскрывать тему вариантов представления отрицательных чисел с метода "знак-величина" или sign-magnitude. Это самый интуитивно понятный для нас способ репрезентации целых чисел. В обычной математике как: есть грубо говоря модуль числа и его знак.
И это довольно просто перенести в память. Мы просто обговариваем, что наиболее значимый бит числа мы отводим по бит знака, а остальные биты обозначают модуль числа. Если знаковый бит - 0, значит число положительное. Если 1 - отрицательное. Таким образом получается вполне естественная ассоциация с привычными нам правилами. Есть натуральный ряд чисел плюс ноль. Чтобы получить множество всех целых чисел, нужно ко множеству натуральных чисел прибавить множество чисел, которое получается из натуральных путем добавления минуса в начале числа.
Давайте на примере. В восьмибитном числе только 7 бит будут описывать модуль числа, который может находится в отрезке [0, 127]. А самый старший бит будет отведен для знака. С добавлением знака мы теперь может кодировать все числа от -127 до 127. Так, число -43 будет выглядеть как 10101011, в то время как 43 будет выглядеть как 00101011. Однако очень внимательные читатели уже догадались, что эта форма представления отрицательных чисел имеет некоторые side-effect'ы, которые усложняют внедрение этого способа в реальные архитектуры:
1️⃣ Появление двух способов изображения нуля: 00000000 и 10000000.
2️⃣ Представление числа из определения разбивается на 2 части, каждая из которых должна иметься в виду и каким-то образом обрабатываться.
3️⃣ Из предыдущего пункта выходит, что операции сложения и вычитания чисел с таким представлением требуют разной логики в зависимости от знакового бита. Мы должны в начале "отрезать" знаковый бит, сделать операцию, которая соответствует комбинации знаковых битов операндов и первоначальной операции, и потом обратно совместить результат со знаком.
4️⃣ Раз у нас 2 нуля, мы можем представлять на 1 число меньше, чем могли бы в идеале.
В общем, минусы значительные. И хоть такое представление и использовалось в ранних компьютерах из-за интуитивной понятности для инженеров, однако в наше время этот способ представления знаковых целых чисел практически не используется.
Однако "знак-величина" используется по сей день, но немного для другого. IEEE floating point использует этот метод для отображения мантиссы числа. Есть модуль мантиссы(ее абсолютное значение) и есть ее знаковый бит. Кстати поэтому у нас есть положительные и отрицательные нули, бесконечности и NaN'ы во флотах. Вот как оно оказывается работает.
Apply yourself in the proper place. Stay cool.
#cppcore #base
👍38❤🔥6❤5⚡1😁1
Обратный код
Обратный код или ones' complement - уже более совершенное представление целых чисел в двоичном виде. Этот код позволяет очень легко выполнять операции сложения/вычитания над числами, используя только лишь операцию сложения.
Вообще говоря, в арифметике операцию вычитания можно переопределить через операцию сложения. Вместо вычитания одного числа из другого, вы инвертируете вычитаемое и складываете с уменьшаемым. Типа того:
Обратный код очень удобно использовать именно в контексте такого свойства, потому что в нем очень просто инвертируются числа.
Как и во всех системах, поддерживающих представление отрицательных чисел, в нем есть зарезервированный знаковый бит, а затем идет "модуль" числа. Например, число 5 в двоичном виде представляется, как 101. Восьмибиное знаковое число 5 в обратном коде представляется, как 00000101. Старший бит 0 значит, что число положительное, дальше идут незначащие нули и в конце наше число.
Инвертированное же число получается просто обращением всех битов в обратные. 0 в 1 и 1 в 0.
То есть число -5 представляется, как 11111010.
И если мы сложим 2 обратных числа, то получим естественно 0:
Причем складываются два числа без учета "особенности" старшего бита. Сложение происходит просто как сложение двух двоичных чисел. Если сумма не умещается в заданное количество бит, то есть произошло "переполнение", то нужно сделать end-round carry aka добавление этого переполненного бита к сумме. Пока не очень понятно, но давайте попробуем что-нибудь посчитать:
Получили ожидаемое положительное(знаковый бит 0) число 19.
Можем уйти в минуса:
Вот так все просто.
Но и у этого кода есть недостатки. Главный из них вы уже могли заметить в посте. Ноль представляется, как 11111111. Точнее, у нуля 2 значения - все нули и все единички. То есть появляется +0 и -0.
С точки зрения вычислений это особо никак не влияет на результат, но добавляет головной боли при разработке, так как надо тестировать софт и для отрицательного нуля.
Недостаток довольно надоедливый. Поэтому, и хоть динозавристые компьютеры использовали этот код, все современный машины используют дополнительный код. О нем в следующем посте.
Ну и вот этот end-round carry создает дополнительный этап вычисления: carry flag в процессоре нужно складывать с результатом.
Remove inconvenience from your life. Stay cool.
#base
Обратный код или ones' complement - уже более совершенное представление целых чисел в двоичном виде. Этот код позволяет очень легко выполнять операции сложения/вычитания над числами, используя только лишь операцию сложения.
Вообще говоря, в арифметике операцию вычитания можно переопределить через операцию сложения. Вместо вычитания одного числа из другого, вы инвертируете вычитаемое и складываете с уменьшаемым. Типа того:
a - b = a + (-b)
Обратный код очень удобно использовать именно в контексте такого свойства, потому что в нем очень просто инвертируются числа.
Как и во всех системах, поддерживающих представление отрицательных чисел, в нем есть зарезервированный знаковый бит, а затем идет "модуль" числа. Например, число 5 в двоичном виде представляется, как 101. Восьмибиное знаковое число 5 в обратном коде представляется, как 00000101. Старший бит 0 значит, что число положительное, дальше идут незначащие нули и в конце наше число.
Инвертированное же число получается просто обращением всех битов в обратные. 0 в 1 и 1 в 0.
То есть число -5 представляется, как 11111010.
И если мы сложим 2 обратных числа, то получим естественно 0:
00000101 + 11111010 = 11111111 = 0
Причем складываются два числа без учета "особенности" старшего бита. Сложение происходит просто как сложение двух двоичных чисел. Если сумма не умещается в заданное количество бит, то есть произошло "переполнение", то нужно сделать end-round carry aka добавление этого переполненного бита к сумме. Пока не очень понятно, но давайте попробуем что-нибудь посчитать:
31 - 12 = 31 + (-12) = 00011111 + (-00001100) = 00011111+ 11110011 = 1'00010010(произошло переполнение, поэтому отбрасываем старший бит и добавляем его к сумме) = 00010010 + 1 = 00010011 = 19
Получили ожидаемое положительное(знаковый бит 0) число 19.
Можем уйти в минуса:
25 - 29 = 25 + (-29) = 00011001 + (-00011101) = 00011001 + 11100010 = 11111011 = -00000100 = -4
Вот так все просто.
Но и у этого кода есть недостатки. Главный из них вы уже могли заметить в посте. Ноль представляется, как 11111111. Точнее, у нуля 2 значения - все нули и все единички. То есть появляется +0 и -0.
С точки зрения вычислений это особо никак не влияет на результат, но добавляет головной боли при разработке, так как надо тестировать софт и для отрицательного нуля.
Недостаток довольно надоедливый. Поэтому, и хоть динозавристые компьютеры использовали этот код, все современный машины используют дополнительный код. О нем в следующем посте.
Ну и вот этот end-round carry создает дополнительный этап вычисления: carry flag в процессоре нужно складывать с результатом.
Remove inconvenience from your life. Stay cool.
#base
1👍33🔥7❤6🤔2🤨2
Дополнительный код
Вот мы и дошли до самого распространенного способа представления знаковых целых чисел в современных компьютерах. Это дополнительный код или two's complement на бездуховном.
По своей сути, это чуть усложненный обратный код. Если там для представления отрицательного числа нам нужно было инвертировать все биты числа и дело в шляпе, то здесь нам к получившемуся результату добавить единичку.
То есть:
Дополнительный код также поддерживает замену операции вычитания через сложение с обратным вычитаемым. В случае переполнения просто откидываем новый получившийся разряд.
Можем проверить, кстати, что при сложении 2 обратных друг другу чисел, мы получим 0.
Именно за счет добавления единички мы избегаем ситуации, когда у нас есть 2 разных способа кодирования нуля.
Однако теперь у нас несимметричный диапазон представляемых чисел, так как место одного из нулей должно занять другое число. Если для обратного кода он был [-(2^(N-1) - 1), 2^(N-1) - 1] ([-127, 127] для восьмибитных чисел), то для дополнительного кода он такой [-2^(N-1), 2^(N-1) - 1] ([-128, 127] для восьмибитных чисел).
Вы наверное все это читаете и немного грустите. Во-первых, скучно. Во-вторых, это надо просто заучить(возможно только для экзамена). Никаких аналогий в голове на это особо не придумаешь.
Но на мой взгляд, здесь тот случай когда русскоязычное научное сообщество с переводами перемудрило, усложнив понимание. Сейчас все будет намного понятнее.
В английском достаточно знать слово complement и иметь немного воображения.
Complement - дополнение. Грубо говоря если у вас есть часть предмета, то compliment это остальная часть, которой нужно дополнить вашу, чтобы получить целое.
В случае обратного кода (one's complement), отрицательное значение дополняет положительное так, чтобы их сумма давала в результате единицы во всех разрядах. Технически мы просто инвертируем биты, а идейно дополняем до всех единиц.
Дополнительный код (two's complement) - похожий принцип. Здесь two (2) это основание системы счисления. Если у нас двоичная система счисления и есть N разрядов, то представление отрицательного значения должно дополнять представление положительного так, чтобы в сумме они давали 2^N. Например, для трёх бит 2^3 это (8) 1000. Следовательно:
А теперь еще немного магии для тех, кто путался, куда ставить апостроф в этих комплементах. Ones' complement -"дополнение до единиц". Единиц во множественном числе. То есть должны во всех разрядах получиться единицы при сложении с обратным. Two's complement - "дополнение до двойки". Двойки в единственном числе. Дополняем так, чтобы в сумме получилась степень двойки.
В английском апострофом обозначается принадлежность одного объекта другому. И для обозначения принадлежности существительным в единственном числе после слова идет апостроф и 's'. А для множественных просто апостроф(типа потому что s на конце уже есть).
Вот такие дела. Надеюсь, что последние абзацы мощно добавили вам понимания и раскрыли секреты вуду.
Have a deep meaning in your life. Stay cool.
#base
Вот мы и дошли до самого распространенного способа представления знаковых целых чисел в современных компьютерах. Это дополнительный код или two's complement на бездуховном.
По своей сути, это чуть усложненный обратный код. Если там для представления отрицательного числа нам нужно было инвертировать все биты числа и дело в шляпе, то здесь нам к получившемуся результату добавить единичку.
То есть:
-5 = ~5 + 1 = ~0000101 + 1 = 11111010 + 1 = 11111011
Дополнительный код также поддерживает замену операции вычитания через сложение с обратным вычитаемым. В случае переполнения просто откидываем новый получившийся разряд.
Можем проверить, кстати, что при сложении 2 обратных друг другу чисел, мы получим 0.
13 - 13 = 13 + (-13) = 13 + ~13 + 1 = 00001101 + 11110010 + 1 = 11111111 + 1 = 1'00000000 = 0
Именно за счет добавления единички мы избегаем ситуации, когда у нас есть 2 разных способа кодирования нуля.
Однако теперь у нас несимметричный диапазон представляемых чисел, так как место одного из нулей должно занять другое число. Если для обратного кода он был [-(2^(N-1) - 1), 2^(N-1) - 1] ([-127, 127] для восьмибитных чисел), то для дополнительного кода он такой [-2^(N-1), 2^(N-1) - 1] ([-128, 127] для восьмибитных чисел).
Вы наверное все это читаете и немного грустите. Во-первых, скучно. Во-вторых, это надо просто заучить(возможно только для экзамена). Никаких аналогий в голове на это особо не придумаешь.
Но на мой взгляд, здесь тот случай когда русскоязычное научное сообщество с переводами перемудрило, усложнив понимание. Сейчас все будет намного понятнее.
В английском достаточно знать слово complement и иметь немного воображения.
> Ones' complement (обратный код)
> Two's complement (дополнительный код).
Complement - дополнение. Грубо говоря если у вас есть часть предмета, то compliment это остальная часть, которой нужно дополнить вашу, чтобы получить целое.
В случае обратного кода (one's complement), отрицательное значение дополняет положительное так, чтобы их сумма давала в результате единицы во всех разрядах. Технически мы просто инвертируем биты, а идейно дополняем до всех единиц.
> (0) 000 -> 111 (-0)
> (1) 001 -> 110 (-1)
> (2) 010 -> 101 (-2)
> (3) 011 -> 100 (-3)
То есть: 000 + 111 = 001 + 110 = 010 + 101 = 011 + 100 == 111 - тот самый отрицательный ноль
Дополнительный код (two's complement) - похожий принцип. Здесь two (2) это основание системы счисления. Если у нас двоичная система счисления и есть N разрядов, то представление отрицательного значения должно дополнять представление положительного так, чтобы в сумме они давали 2^N. Например, для трёх бит 2^3 это (8) 1000. Следовательно:
> (0) 000 - у него нет "дополнения"
> (1) 001 -> 111 (-1)
> (2) 010 -> 110 (-2)
> (3) 011 -> 101 (-3)
001 + 111 = 010 + 110 = 011 + 101 = 1'000(2^3, откидываем старший разряд) == 0
А теперь еще немного магии для тех, кто путался, куда ставить апостроф в этих комплементах. Ones' complement -"дополнение до единиц". Единиц во множественном числе. То есть должны во всех разрядах получиться единицы при сложении с обратным. Two's complement - "дополнение до двойки". Двойки в единственном числе. Дополняем так, чтобы в сумме получилась степень двойки.
В английском апострофом обозначается принадлежность одного объекта другому. И для обозначения принадлежности существительным в единственном числе после слова идет апостроф и 's'. А для множественных просто апостроф(типа потому что s на конце уже есть).
Вот такие дела. Надеюсь, что последние абзацы мощно добавили вам понимания и раскрыли секреты вуду.
Have a deep meaning in your life. Stay cool.
#base
🔥25❤🔥6👍3⚡2❤2
Как компилятор определяет переполнение
В прошлом посте я рассказал, как можно детектировать signed integer overflow с помощью готовых функций. Сегодня рассмотрим, что ж за магия такая используется для таких заклинаний.
Сразу с места в карьер. То есть в ассемблер.
Есть функция
Посмотрим, во что эта штука компилируется под гцц х86.
Все немного упрощаю, но в целом картина такая:
Подготавливаем регистры, делаем сложение. А далее идет инструкция
Инструкция
1️⃣ Если операция между двумя положительными числами дает отрицательное число.
2️⃣ Если сумма двух отрицательных чисел дает в результате положительное число.
Можно считать, что это два условия для переполнения знаковых чисел. Например
127 + 127 = 0111 1111 + 0111 1111 = 1111 1110 = -2 (в дополнительном коде)
Результат сложения двух положительных чисел - отрицательное число, поэтому при таком сложении выставится регист OF.
Для беззнаковых чисел тоже кстати есть похожий флаг. CF или Carry Flag. Мы говорили, что переполнение для беззнаковых - не совсем переполнение, но процессор нам и о таком событии дает знать через выставление carry флага.
Собственно, вы и сами можете детектировать переполнение подобным образом. Конечно, придется делать асемблерную вставку, но тем не менее.
Но учитывая все условия для overflow, есть более простые способы его задетектить, чисто на арифметике. Но об этом позже.
Detect problems. Stay cool.
#base #cppcore #compiler
В прошлом посте я рассказал, как можно детектировать signed integer overflow с помощью готовых функций. Сегодня рассмотрим, что ж за магия такая используется для таких заклинаний.
Сразу с места в карьер. То есть в ассемблер.
Есть функция
int add(int lhs, int rhs) {
int sum;
if (__builtin_add_overflow(lhs, rhs, &sum))
abort();
return sum;
}Посмотрим, во что эта штука компилируется под гцц х86.
Все немного упрощаю, но в целом картина такая:
mov %edi, %eax
add %esi, %eax
jo call_abort
ret
call_abort:
call abort
Подготавливаем регистры, делаем сложение. А далее идет инструкция
jo. Это условный прыжок. Если условие истино - прыгаем на метку call_abort, если нет - то выходим из функции.Инструкция
jo выполняет прыжок, если выставлен флаг OF в регистре EFLAGS. То есть Overflow Flag. Он выставляется в двух случаях:1️⃣ Если операция между двумя положительными числами дает отрицательное число.
2️⃣ Если сумма двух отрицательных чисел дает в результате положительное число.
Можно считать, что это два условия для переполнения знаковых чисел. Например
127 + 127 = 0111 1111 + 0111 1111 = 1111 1110 = -2 (в дополнительном коде)
Результат сложения двух положительных чисел - отрицательное число, поэтому при таком сложении выставится регист OF.
Для беззнаковых чисел тоже кстати есть похожий флаг. CF или Carry Flag. Мы говорили, что переполнение для беззнаковых - не совсем переполнение, но процессор нам и о таком событии дает знать через выставление carry флага.
Собственно, вы и сами можете детектировать переполнение подобным образом. Конечно, придется делать асемблерную вставку, но тем не менее.
Но учитывая все условия для overflow, есть более простые способы его задетектить, чисто на арифметике. Но об этом позже.
Detect problems. Stay cool.
#base #cppcore #compiler
❤🔥16👍5🔥4😁3❤1