Двоичная система счисления. Бит и байт. Сегментация памяти.
Вообще, как компьютер может хранить, например, слово «диск»? Главный принцип — намагничивание и размагничивание одной дорожки (назовем ее так). Одна микросхема памяти — это, грубо говоря, огромное количество дорожек. Сейчас попробуем разобраться. Например:
нуль будет обозначаться как 0000 (четыре нуля),
(т.е. правую единицу заменяем на 0 и вторую устанавливаем в 1).
Уловили принцип? «0» и «1» — это т.н. биты. Один бит, как вы уже заметили, может быть нулем или единицей, т.е. размагничена или намагничена та или иная дорожка («0» и «1» это условное обозначение). Если еще присмотреться, то можно заметить, что каждый следующий установленный бит (начиная справа) увеличивает число в два раза: 0001 в нашем примере = 1; 0010 два; 0100 четыре; 1000 восемь и т.д. Это и есть т.н. двоичная форма представления данных.
Т.о. чтобы обозначить числа от 0 до 9 нам нужно четыре бита (хоть они и не до конца использованы. Можно было бы продолжить: десять 1010, одиннадцать 1011 , пятнадцать 1111).
Компьютер хранит данные в памяти именно так. Для обозначения какого-нибудь символа (цифры, буквы, запятой, точки. ) в компьютере используется определенное количество бит. Компьютер «распознает» 256 (от 0 до 255) различных символов по их коду. Этого достаточно, чтобы вместить все цифры (0 — 9), буквы латинского алфавита (a — z, A — Z), русского (а — я, А — Я), а также другие символы. Для представления символа с максимально возможным кодом (255) нужно 8 бит. Эти 8 бит называются байтом. Т.о. один любой символ — это всегда 1 байт (см. рис. 1).
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| р | н | р | н | н | р | н | р |
Рис. 1. Один байт с кодом буквы Z
(буквы н и р обозначают: намагничено или размагничено соответственно)
Можно элементарно проверить. Создайте в текстовом редакторе файл с любым именем и запишите в нем один символ, например, «М» (но не нажимайте Enter!). Если вы посмотрите его размер, то файл будет равен 1 байту. Если ваш редактор позволяет смотреть файлы в шестнадцатеричном формате, то вы сможете узнать и код сохраненного вами символа. В данном случае буква «М» имеет код 4Dh в шестнадцатеричной системе, которую мы уже знаем или 1001101 в двоичной.
Т.о. слово «диск» будет занимать 4 байта или 4*8 = 32 бита. Как вы уже поняли, компьютер хранит в памяти не сами буквы этого слова, а последовательность «единичек» и «ноликов». «Почему же тогда на экране мы видим текст, а не «единички-нолики»? — спросите вы. Чтобы удовлетворить ваше любопытство, я забегу немного вперед и скажу, что всю работу по выводу самого символа на экран (а не битов) выполняет видеокарта (видеоадаптер), которая находится в вашем компьютере. И если бы ее не было, то мы, естественно, ничего бы не видели, что у нас творится на экране.
В Ассемблере после двоичного числа всегда должна стоять буква «b». Это нужно для того, чтобы при ассемблировании нашей программы Ассемблер смог отличать десятичные, шестнадцатеричные и двоичные числа. Например: 10 — это «десять», 10h — это «шестнадцать» а 10b — это «два» в десятичной системе.
Т.о. в регистры можно загружать двоичные, десятичные и шестнадцатеричные числа.
В результате в регистрах AX, BH и CL будет находится одно и тоже число, только загружаем мы его в разных системах. Компьютер же будет хранить его в двоичном формате (как в регистре BH).
Итак, подведем итог. В компьютере вся информация хранится в двоичном формате (двоичной системе) примерно в таком виде: 10101110 10010010 01111010 11100101 (естественно, без пробелов. Для удобства я разделили биты по группам). Восемь бит — это один байт. Один символ занимает один байт, т.е. восемь бит. По-моему, ничего сложного. Очень важно уяснить данную тему, так как мы будем постоянно пользоваться двоичной системой, и вам необходимо знать ее на «отлично».
Как перевести двоичное число в десятичное:
Надо сложить двойки в степенях, соответствующих позициям, где в двоичном стоят единицы. Например:
Возьмем число 20. В двоичной системе оно имеет следующий вид: 10100b
Итак (начнем слева направо, считая от 4 до 0; число в нулевой степени всегда равно единице (вспоминаем школьную программу по математике)):
Как перевести десятичное число в двоичное:
Можно делить его на два, записывая остаток справа налево:
В результате получаем: 10100b = 20
Как перевести шестнадцатеричное число в десятичное:
В шестнадцатеричной системе номер позиции цифры в числе соответствует степени, в которую надо возвести число 16:
В настоящий момент есть множество калькуляторов, которые могут считать и переводить числа в разных системах счисления. Например, калькулятор Windows, который должен быть в инженерном виде. Очень удобен калькулятор и в DOS Navigator’е. Если у вас есть он, то отпадает необходимость в ручном переводе одной системы в другую, что, естественно, упростит вам работу. Однако, знать этот принцип крайне важно!
Сегментация памяти в DOS.
Возьмем следующее предложение: «Изучаем сегменты памяти». Теперь давайте посчитаем, на каком месте стоит буква «ы» в слове «сегменты» от начала предложения включая пробелы. На шестнадцатом. Подчеркну, что мы считали слово от начала предложения.
Теперь немного усложним задачу и разобьем предложение следующим образом (символом «_» обозначен пробел):
В слове «Изучаем» символ «И» стоит на нулевом месте; символ «з» на первом, «у» на втором и т.д. В данном случае мы считаем буквы начиная с нулевой позиции, используя два числа. Назовем их сегмент и смещение. Тогда, символ «ч» будет иметь следующий адрес: 0000:0003, т.е. сегмент 0000, смещение 0003. Проверьте.
В слове «сегменты» будем считать буквы начиная с десятой позиции, но с нулевого смещения. Тогда символ «н» будет иметь следующий адрес: 0010:0005, т.е. пятый символ начиная с десятой позиции. 0010 — сегмент, 0005 смещение. Тоже проверьте.
В слове «память» считаем буквы начиная с 0020 сегмента и также с нулевой позиции. Т.о. символ «а» будет иметь аодрес 0020:0001, т.е. сегмент 0020, смещение 0001. Опять проверим.
Итак, мы выяснили, что для того, чтобы найти адрес нужного символа необходимо два числа: сегмент и смещение внутри этого сегмента. В Ассемблере сегменты хранятся в сегментных регистрах: CS, DS, ES, SS (см. предыдущий выпуск ), а смещения могут храниться в других (но не во всех).
Регистр CS служит для хранения сегмента кода программы (Code Segment — сегмент кода);
Регистр DS для хранения сегмента данных (Data Segment — сегмент данных);
Регистр SS для хранения сегмента стека (Stack Segment — сегмент стека);
Регистр ES дополнительный сегментный регистр, который может хранить любой другой сегмент (например, сегмент видеобуфера).
Пример N 2:
Давайте попробуем загрузить в пару регистров ES:DI сегмент и смещение буквы «м» в слове «памяти» из примера N 1 (см. выше). Вот как это запишется на Ассемблере:
Теперь в регистре ES находится сегмент с номером 20, а регистре DI смещение к букве «м» в слове «памяти». Проверьте, пожалуйста.
Здесь стоит отметить, что загрузка числа (т.е. какого-нибудь сегмента) напрямую в сегментый регистр запрещена. Поэтому мы в строке (1) загрузили сегмент в AX, а в строке (2) загрузили в регистр ES число 20, которое находилось в регистре AX:
Когда мы загружаем программу в память, она автоматически располагается в первом свободном сегменте. В файлах типа *.com все сегментные регистры автоматически инициализируются для этого сегмента (устанавливаются значения равные тому сегменту, в который загружена программа). Это можно проверить при помощи отладчика. Если, например, мы загружаем программу типа *.com в память, и компьютер находит первый свободный сегмент с номером 5674h, то сегментные регистры будут иметь следующие значения:
Код программы типа *.com должны начинаться со смещения 100h. Для этого мы, собственно, и ставили в наших прошлых примерах программ оператор org 100h, указывая Ассемблеру при ассемблировании использовать смещение 100h от начала сегмента, в который загружена наша программа (позже мы рассмотрим для чего это нужно). Сегментные же регистры, как я уже говорил, автоматически принимают значение того сегмента, в который загрузилась наша программа.
Пара регистров CS:IP задает текущий адрес кода. Теперь рассмотрим, как все это происходит на конкретном примере:
Пример N 3.
Итак, строки (1) и (8) описывают сегмент: CSEG (даем имя сегменту) segment (оператор Ассемблера, указывающий, что имя CSEG — это название сегмента); CSEG ends (end segment — конец сегмента) указывает Ассемблеру на конец сегмента.
Строка (2) сообщает, что код программы (как и смещения внутри сегмента CSEG) необходимо отсчитывать с 100h. По этому адресу в память всегда загружаются программы типа *.com.
Запускаем программу из Примера N 3 в отладчике. Допустим, она загрузилась в свободный сегмент 1234h. Первая команда в строке (4) будет располагаться по такому адресу:
1234h:0100h (т.е. CS = 1234h, а IP = 0100h) (посмотрите в отладчике на регистры CS и IP).
Перейдем к следующей команде (в отладчике CodeView нажмите клавишу F8, в другом посмотрите какая клавиша нужна; будет написано что-то вроде «F8-Step»). Теперь вы видите, что изменились следующие регистры:
AX = 0900h (точнее, AH = 09h, а AL = 0, т.к. мы загрузили командой mov ah,9 число 9 в регистр AH, при этом не трогая AL. Если бы AL был равен, скажем, 15h, то после выполнения данной команды AX бы равнялся 0915h)
IP = 102h (т.е. указывает на адрес следующей команды. Из этого можно сделать вывод, что команда mov ah,9 занимает 2 байта: 102h — 100h = 2).
Следующая команда (нажимаем клавишу F8) изменяет регистры DX и IP. Теперь DX указывает на смещение нашей строки («Oleg$») относительно начала сегмента, т.е. 109h, а IP равняется 105h, т.е. адрес следующей команды. Нетрудно посчитать, что команда mov dx,offset My_name занимает 3 байта (105h — 102h = 3).
Обратите внимание, что в Ассемблере мы пишем:
а в отладчике видим следующее:
mov dx,109 (109 — шестнадцатеричное число, но CodeView символ ‘h’ не ставит. Это надо иметь в виду).
Почему так происходит? Дело в том, что при ассемблировании программы, Ассемблер подставляет вместо offset My_name реальный адрес строки с именем My_name в памяти. Можно, конечно, записать сразу
Программа будет работать нормально. Но для этого нам нужно высчитать самим этот адрес. Попробуйте вставить следующие команды, начиная со строки (7) в примере N 3:
Просто продублируем команду int 20h (хотя, как вы уже знаете, до строки (8) программа не дойдет).
Теперь ассемблируйте программу заново. Запускайте ее под отладчиком. Вы увидите, что в DX загружается не 109h, а другое число. Подумайте, почему так происходит. Это просто!
В окне «Memory» («Память») вы должны увидеть примерно такое:
Позиция N1 (1234) — сегмент, в который загрузилась наша программа (может быть любым).
Позиция N2 (0000) — смещение в данном сегменте (сегмент и смещение отделяются двоеточием (:)).
Позиция N3 (CD 20 00 . F0 FE) — код в шестнадцатеричной системе, который располагается с адреса 1234:0000.
Позиция N4 (= .a.) — код в ASCII (ниже рассмотрим), соответствующий шестнадцатеричным числам с правой стороны.
В Позиции N2 (смещение) введите значение, которое находится в регистре DX после выполнения строки (5). После этого в Позиции N4 вы увидите строку «Oleg$», а в Позиции N3 — код символов «Oleg$» в шестнадцатеричной системе. Вот что загружается в DX! Это не что иное, как АДРЕС (смещенеие) нашей строки в сегменте!
Но вернемся. Итак, мы загрузили в DX адрес строки в сегменте, который мы назвали CSEG (строки (1) и (9) в Прмере N 3). Теперь переходим к следующей команде: int 21h. Вызываем прерывание DOS с функцией 9 (mov ah,9) и адресом строки в DX (mov dx,offset My_name).
Как я уже говорил раньше, для использования прерываний в программах, в AH заносится номер функции. Номера функций нужно запоминать.
Наше первое прерывание.
Функция 09h прерывания 21h выводит строку на экран, адрес которой указан в регистре DX.
Вообще, любая строка, состоящая из ASCII символов, называется ASCII-строка. ASCII символы — это символы от 0 до 255 в DOS, куда входят буквы русского и латинского алфавитов, цифры, знаки препинания и пр.
Изобразим это в таблице (так всегда теперь будем делать):
Функция 09h прерывания 21h — вывод строки символов на экран в текущую позицию курсора:
Вход: AH = 09h, DX = адрес ASCII-строки символов, заканчивающийся ‘$’
Выход: ничего
В поле «Вход» мы указываем, в какие регистры что загружать, а в поле «Выход» — что возвращает функция. Сравните эту таблицу с Примером N 3.
Вот мы и рассмотрели сегментацию памяти. Если я что-то упустил, то это рассмотрим в последующих выпусках. Очень надеюсь на то, что вы разобрались в данной теме.
Теперь интересная программка для практики, которая выводит в верхний левый угол экрана веселую рожицу на синем фоне:
Многие операторы вы уже знаете. Поэтому я буду объяснять только новые.
В данном примере мы используем вывод символа прямым отображением в видеобуфер.
В строках (4) и (5) загружаем в сегментный регистр ES число 0B800h, которое соответствует сегменту дисплея в текстовом режиме (запомните его!). В строке (6) загружаем в регистр DI нуль. Это будет смещение относительно сегмента 0B800h. В строках (8) и (9) в регистр AH заносится атрибут символа (31 — ярко-белый символ на синем фоне) и в AL — ASCII-код символа (01 — это рожица) соответственно.
В строке (10) заносим по адресу 0B800:0000h (т.е. первый символ в первой строке дисплея — верхний левый угол) атрибут и ASCII-код символа (31 и 01 соответственно) (сможете разобраться?).
Обратите внимание на запись регистров в строке (10). Скобки ( [ ] ) указывают на то, что надо загрузить число не в регистр, а по адресу, который содержится в регистре (в данном случае, как уже отмечалось, — это 0B800:0000h).
Можете поэксперементировать с данным примером. Только не меняйте строки (4) и (5). Сегментный регистр должен быть ES (можно, конечно, и DS, но тогда надо быть осторожным). Более подробно данный метод рассмотрим позже. Сейчас нам из него нужно понять принцип сегментации на практике.
Следует отметить, что вывод символа прямым отображением в видеобуфер является самым быстрым. Выполнение команды в строке (10) занимает 3 — 5 тактов. Т.о. на Pentium-100Mhz можно за секунду вывести 20 миллионов(!) символов или чуть меньше точек на экран! Если бы все программисты (а особенно Microsoft) выводили бы символы или точки на экран методом прямого отображения в видеобуфер на Ассемблере, то программы бы работали чрезвычайно быстро. Я думаю, вы представляете.
Перевод чисел в различные системы счислений
Когда занимаешься настройками сетей различного масштаба и каждый день сталкиваешься с вычислениями – то такого рода шпаргалки заводить не обязательно, все и так делается на безусловном рефлексе. Но когда в сетях ковыряешься очень редко, то не всегда вспомнишь какая там маска в десятичной форме для префикса 21 или же какой адрес сети при этом же префиксе. В связи с этим я и решил написать несколько маленьких статей-шпаргалок по переводом чисел в различные системы счислений, сетевым адресам, маскам и т.п. В это части пойдет речь о переводи чисел в различные системы счислений.
1. Системы счислений
Когда вы занимаетесь чем-то связанным с компьютерными сетями и ИТ, вы по любому столкнетесь с этим понятием. И как толковый ИТ-шник вам нужно разбираться в этом хотя бы чу-чуть даже если на практике вы это будете применять очень редко.
Рассмотрим перевод каждой цифры из IP-адреса 98.251.16.138 в следующие системы счислений:
- Двоичная
- Восьмеричная
- Десятичная
- Шестнадцатеричная
1.1 Десятичная
Так как цифры записаны в десятичной, перевод с десятичной в десятичную пропустим ��
1.1.1 Десятичная → Двоичная
Как мы знаем двоичная система счисления используется практически во всех современных компьютерах и многих других вычислительных устройствах. Система очень проста – у нас есть только 0 и 1.
Для преобразования числа с десятиной в двоичную форму нужно использовать деление по модулю 2 (т.е. целочисленное деление на 2) в результате чего мы всегда будем иметь в остатке либо 1, либо 0. При этом результат записываем справа налево. Пример все поставит на свои места:
Рисунок 1.1 – Перевод чисел из десятичной в двоичную систему
Рисунок 1.2 – Перевод чисел из десятичной в двоичную систему
Опишу деление числа 98. Мы делим 98 на 2, в результате имеем 49 и остаток 0. Далее продолжаем деление и делим 49 на 2, в результате имеем 24 с остатком 1. И таким же образом добираемся до 1-ки или 0-ка в делимом. Затем результат записываем справа налево.
1.1.2 Десятичная → Восьмеричная
Восьмеричная система – это целочисленная система счисления с основанием 8. Т.е. все числа в ней представлены диапазоном 0 – 7 и для перевода с десятичной системы нужно использовать деление по модулю 8.
Рисунок 1.3 – Перевод чисел из десятичной в восьмеричную систему
Деление аналогично 2-чной системе.
1.1.3 Десятичная → Шестнадцатеричная
Шестнадцатеричная система почти полностью вытеснила восьмеричную систему. У нее основание 16, но используются десятичные цифры от 0 до 9 + латинские буквы от A(число 10) до F(число 15). С ней вы сталкиваетесь каждый раз, когда проверяете настройки сетевого адаптера — это МАС-адрес. Так же, когда используется IPv6.
Рисунок 1.4 – Перевод чисел из десятичной в шестнадцатеричную систему
1.2 Двоичная
В предыдущем примере мы перевели все десятичные числа в другие системы счислений, одна из которых двоичная. Теперь переведем каждое число с двоичной формы.
1.2.1 Двоичная → Десятичная
Для перевода чисел с двоичной формы в десятичную нужно знать два нюанса. Первый – у каждого нолика и единички есть множитель 2 в n-й степени, при котором n увеличивается справа налево ровно на единичку. Второй – после перемножения все числа нужно сложить и мы получим число в десятичной форме. В итого у нас будет формула такого вида:
Где,
D – это число в десятичной форме, которое мы ищем;
n – количество символов в двоичном числе;
a – число в двоичной форме на n-й позиции (т.е. первый символ, второй, и т.п.);
p – коэффициент, равный 2,8 или 16 в степени n (в зависимости от системы счисления)
К примеру возьмем число 110102. Смотрим на формулу и записываем:
-
Число состоит из 5 символов (n=5)
D = (1 × 2 5-1 ) + (1 × 2 5-2 ) + (0 × 2 5-3 ) + (1 × 2 5-4 ) + (0 × 2 5-5 ) = 16 + 8 + 0 + 2 + 0 = 2610
Кто привык записывать справа на лево, форму будет выглядеть так:
D = (0 × 2 5-5 ) + (1 × 2 5-4 ) + (0 × 2 5-3 ) + (1 × 2 5-2 ) + (1 × 2 5-1 ) = 0 + 2 + 0 + 8 + 16 = 2610
Но, как мы знаем, от перестановки слагаемых сумма не меняется. Давайте теперь переведем наши числа в десятичную форму.
Рисунок 1.5 – Перевод чисел из двоичной в десятичную систему
1.2.2 Двоичная → Восьмеричная
При переводе нам нужно двоичное число разбить на группы по три символа справа налево. Если последняя группа не состоит из трех символов, то мы просто возмещаем недостающие биты ноликами. К примеру:
10101001 = 0 10 101 001
1011100 = 00 1 011 100
Каждая группа битов – это одно из восьмеричных чисел. Чтобы узнать какое, нужно использовать написанную выше формулу 1.2.1 для каждой группы битов. В результате мы получим.
Рисунок 1.6 – Перевод чисел из двоичной в восьмеричную систему
1.2.3 Двоичная → Шестнадцатеричная
Здесь нам нужно двоичное число разбивать на группы по четыре символа справа налево с последующим дополнением недостающих битов группы ноликами, как писалось выше. Если последняя группа состоит из ноликов, то их нужно игнорировать.
110101011 = 000 1 1010 1011
1011100 = 0 101 1100
001010000 = 00 0101 0000 = 0101 0000
Каждая группа битов – это одно из шестнадцатеричных чисел. Используем формулу 1.2.1 для каждой группы битов.
Рисунок 1.7 – Перевод чисел из двоичной в шестнадцатеричную систему
1.3 Восьмеричная
В этой системе у нас могут возникнуть сложности только при переводе в 16-ричную систему, так как остальной перевод проходит гладко.
1.3.1 Восьмеричная → Двоичная
Каждое число в восьмеричной системе – это группа из трех битов в двоичной системе, как писалось выше. Для перевода нам нужно воспользоваться табличкой-шпаргалкой:
Рисунок 1.8 – Шпора по переводу чисел из восьмеричной системы
Используя эту табличку переведем наши числа в двоичную систему.
Рисунок 1.9 – Перевод чисел из восьмеричной в двоичную систему
Немного опишу вывод. Первое число у нас 142, значит будет три группы по три бита в каждой. Юзаем шпору и видим, что цифра 1 это 001, цифра 4 это 100 и цифра 2 это 010. В результате имеем число 001100010.
1.3.2 Восьмеричная → Десятичная
Здесь мы используем формулу 1.2.1 только с коэффициентом 8 (т.е. p=8). В результате имеем
Рисунок 1.10 – Перевод чисел из восьмеричной в десятеричную систему
Возьмем первое число. Исходя из формулы 1.2.1:
-
Число состоит из 3 символов (n=3)
В результате имеем:
D = (1 × 8 3-1 ) + (4 × 8 3-2 ) + (2 × 8 3-3 ) = 64 + 32 + 2 = 9810
1.3.3 Восьмеричная → Шестнадцатеричная
Как писалось раньше, для перевода нам нужно сначала перевести числа в двоичную систему, потом с двоичной в шестнадцатеричную, поделив на группы по 4-ре бита. Можно использовать следующею шпору.
Рисунок 1.11 – Шпора по переводу чисел из шестнадцатеричной системы
Эта табличка поможет перевести из двоичной в шестнадцатеричную систему. Теперь переведем наши числа.
Рисунок 1.12 – Перевод чисел из восьмеричной в шестнадцатеричную систему
1.4 Шестнадцатеричная
В этой системе та же проблема, при переводе в восьмеричную. Но об этом позже.
1.4.1 Шестнадцатеричная → Двоичная
Каждое число в шестнадцатеричной системе – это группа из четырех битов в двоичной системе, как писалось выше. Для перевода нам можно воспользоваться табличкой-шпаргалкой, которая находиться выше. В результате:
Рисунок 1.13 – Перевод чисел из шестнадцатеричной в двоичную систему
Возьмем первое число – 62. Используя табличку (рис. 1.11) мы видим, что 6 это 0110, 2 это 0010, в результате имеем число 01100010.
1.4.2 Шестнадцатеричная → Десятичная
Здесь мы используем формулу 1.2.1 только с коэффициентом 16 (т.е. p=16). В результате имеем
Рисунок 1.14 – Перевод чисел из шестнадцатеричной в десятеричную систему
Возьмем первое число. Исходя из формулы 1.2.1:
-
Число состоит из 2 символов (n=2)
В результате имеем.
D = (6 × 16 2-1 ) + (2 × 16 2-2 ) = 96 + 2 = 9810
1.4.3 Шестнадцатеричная → Восьмеричная
Для перевода в восьмеричную систему нужно сначала перевести в двоичную, затем разбить на группы по 3-и бита и воспользоваться табличкой (рис. 1.8). В результате:
Рисунок 1.15 – Перевод чисел из шестнадцатеричной в восьмеричную систему
Битовое представление чисел
Так как на уровне схем почти вся логика бинарная, ровно такое представление и используется для хранения чисел в компьютерах: каждая целочисленная переменная указывает на какую-то ячейку из 8 ( char ), 16 ( short ), 32 ( int ) или 64 ( long long ) бит.
#Эндианность
Единственная неоднозначность в таком формате возникает с порядком хранения битов — также называемый эндианностью. Зависимости от архитектуры он может быть разным:
- При схеме little-endian сначала идут младшие биты. Например, число $42_<10>$ будет храниться так: $010101$.
- При записи в формате big-endian сначала идут старшие биты. Все примеры из начала статьи даны в big-endian формате.
Хотя big-endian более естественный для понимания — на бумаге мы ровно так обычно и записываем бинарные числа — по разным причинам на большинстве современных процессоров по умолчанию используется little endian.
Иными словами, «$i$-тый бит» означает «$i$-тый младший» или «$i$-тый справа», но на бумаге мы ничего не инвертируем и записываем двоичные числа стандартным образом.
#Битовые операции
Помимо арифметических операций, с числами можно делать и битовые, которые интерпретируют их просто как последовательность битов.
#Сдвиги
Битовую запись числа можно «сдвигать» влево ( x << y ) или вправо ( x >> y ), что эквивалентно умножению или делению на степень двойки с округлением вниз.
Обычное умножение и деление — не самые быстрые операции, однако все битовые сдвиги всегда работают ровно за один такт. Как следствие, умножение и деление на какую-то фиксированную степень двойки всегда работает быстро — даже если вы не используете сдвиги явно, компилятор скорее всего будет проводить подобную оптимизацию.
#Побитовые операции
Помимо && , || и ! , существуют их побитовые версии, которые применяют соответствующую логическую операцию к целым последовательностям битов: & , | ,
Также помимо них есть ещё операция исключающего «или» (XOR), которая записывается как ^ .
- $13$ & $7$ = $1101_2$ & $0111_2$ = $0101_2$ = $5$
- $17$ | $10$ = $10001_2$ | $01010_2$ = $11011_2$ = $27$
- $17$ ^ $9$ = $10001_2$ ^ $01001_2$ = $11000_2$ = $24$
Все побитовые операции тоже работают за один такт, вне зависимости от типа данных. Для больших не вмещающихся в один регистр битовых последовательностей существует битсет.
#Маски
Бинарные последовательности можно поставить в соответствие подмножествам какого-то фиксированного множества: если на $i$-той позиции стоит единица, то значит $i$-тый элемент входит множество, а иначе не входит.
Битовые операции таким образом часто используются операций над множествами, представляемыми битовыми мазками — например, в задачах на полный перебор или динамическое программирование.
#Выделить i-й бит числа
(x >> i) & 1 или x & (1 << i) . Во втором случае результат будет либо 0, либо $2^i$.
Это часто используется для проверки, принадлежит ли $i$-тый элемент множеству:
Напомним, что нумерация идет с младших бит и начинается с нуля.
#Получить число, состоящее из k единиц
(1 << k) — 1 , также известное как $(2^k-1)$ и соответствующее маске полного множества.
#Инвертировать все биты числа
#Добавить i-й элемент в множество
#Удалить $i$-й элемент из множества
#Удалить i-й элемент из множества, если он есть
Также добавляет этот элемент, если его нет.
#Знаковые числа
Целочисленные переменные делятся на два типа — знаковые (signed) и беззнаковые (unsigned).
Если сложить две unsigned int переменные, сумма которых превосходит $2^<32>$, произойдет переполнение: сумму нельзя будет представить точно, и поэтому вместо неё результатом будут только нижние 32 бит. Все операции с беззнаковыми числами как бы проходят по модулю какой-то степени двойки.
Знаковые же типы нужны для хранения значений, которые могут быть и отрицательными. Для этого нужно выделить один бит для хранение знака — отрицательное ли число или нет — немного пожертвовав верхней границей представимых чисел: теперь самое большое представимое число это $2^<31>-1$, а не $2^<32>-1$.
Инженеры, которые работают над процессорами, ещё более ленивые, чем программисты — это мотивировано не только стремлением к упрощению, но и экономией транзисторов. Поэтому когда в signed типах происходит переполнение, результат в битовом представлении считается так же, как и в случае с unsigned числами. Если мы хотим ничего не менять в плане того, как работают unsigned числа, представление отрицательных чисел должно быть таким, что число $-x$ как бы вычитается из большой степени двойки:
- Все неотрицательные числа записываются в точности как раньше.
- У всех отрицательных чисел самый большой бит будет единичным.
- Если прибавить к $2^<31>-1$ единицу, то результатом будет $-2^<31>$, представляемое как 10000000 (в целях изложения мы будем записывать 8 бит, хотя в int их 32).
- Зная двоичную запись положительного числа x , запись -x можно получить как
Упражнение. Каких чисел больше: положительных или отрицательных?
Осторожно. В стандарте C/C++ прописано, что переполнение знаковых переменных приводит к undefined behavior, поэтому полагаться на описанную логику переполнения нельзя, хотя равно это скорее всего и произойдет.
#128-битные числа
Общих регистров размера больше 64 в процессорах нет, однако умножение и несколько смежных инструкций могут использовать два последовательных регистра как один большой. Это позволяет быстро перемножать два 64-битных числа и получать 128-битный результат, разделенный на нижние биты и верхние.
Это весьма специфичная операция, и поэтому в языках программирования нет полноценной поддержки 128-битных переменных. В C++ однако есть «костыль» — тип __int128_t — который фактически просто оборачивает пару из двух 64-битных регистров и поддерживает арифметические операции с ними.
Базовые арифметические операции с ним чуть медленнее, его нельзя напрямую печатать, и деление и прочие сложные операции будут вызывать отдельную библиотеку и поэтому работать очень долго, однако в некоторых ситуациях он оказывается очень полезен.