- 1,545
- 1,017
Всем привет.
Я бы не сказал, что системы счисления напрямую относятся к программированию, но всё же это достаточно интересная и прикладная тема.
Разные системы счисления используются в программировании (в основном - двоичная, шестнадцатеричная и десятичная), поэтому они достойны обсуждения и объяснения "на пальцах".
Статья рассчитана на тех, кто не знает про системы счисления, всё изложено максимально информативно и подробно, начиная с нуля.
I. Сколько цифр мы используем в числах?
Начать стоит с определения.
1) Число - величина, используемая для счёта (1, 2, 3...). Используется везде: и для подсчёта количества чего-либо, и для указания температуры, давления, скорости, расстояния, объёма, массы и других физических, геометрических, химических величин, и как идентификатор чего-либо и т. д. У чисел очень много применений.
Числа никогда не кончаются, их бесконечно. То есть нельзя назвать "самое большое число", для любого числа можно назвать число, которое больше него.
2) Цифра - символ, используемый для записи неотрицательных целых чисел (потому что минус [для отрицательных] и точка [для нецелых] не являются цифрами). В нашей, десятичной, системе цифр всего десять: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. И всё.
Почему их десять - вопрос не по адресу. Я слышал, что ответ кроется в том, что на руках 10 пальцев. На самом деле, количество цифр совсем необязательно должно быть равно 10, и мы это скоро поймём.
II. Как строится десятичное (и не только) число?
От 0 до 9 всё понятно, просто одна цифра и всё. А дальше у нас цифры закончились, что же делать?
На самом деле идея достаточно простая, но словами объяснить её достаточно трудно. Следующее число после 9 - это десять. И количество этих "десятков" давайте записывать второй цифрой (потому что одной нам уже не хватает) справа. То есть, к примеру, число 26 - это 2 десятка и еще (плюс) 6. Говорят обычно "2 десятка и 6 единиц", типа 6 раз по 1 (т. е. 6 x 1 = 6).
Поэтому следующее число после 9 будет иметь вид "один десяток и ноль единиц" (т. е. просто 1 десяток, больше нам единиц не надо), записывается оно как 10. Дальше мы прибавляем к нему единицы (11, 12, 13...), пока можем - и в какой-то момент мы упрёмся в 19. После 9 идёт десять, а если у нас 19 (1 десяток и 9), то у нас "9" отсюда заменится на еще 1 десяток, будет 2 десятка (т. е. 20). Думаю, логика ясна.
Аналогично, когда закончатся все вариации с двумя цифрами (максимальное количество десятков, что мы можем записать - 9, и с единицами то же самое) - это на числе 99. Следующее число назовём сотня и количество этих сотен будет записывать третьей цифрой справа. Чтобы было ясно, то напишу так:
9 + 1 = 10
99 + 1 = 100
999 + 1 = 1000
9999 + 1 = 10000
99999 + 1 = 100000
и так далее
Понятное дело, что такой принцип применим не только к десятичной системе, а к любой (с любым основанием). Основание системы счисления - это количество цифр, которое в ней используется.
III. Как строить следующее число (+1) - алгоритм
Кратко проговорим алгоритм построения следующего числа, чтобы закрепить знания из предыдущего абзаца.
И так, у нас число 12906. Если мы можем прибавить к единицам еще 1 (в данном случае 6 + 1 = 7) - просто делаем это: получается 12907.
А если мы не можем прибавить, как в числе 1259. Ну тогда после 9 у нас идёт 1 десяток (а количество единиц при этом обнуляется), увеличиваем на 1 предыдущую цифру (5 + 1 = 6). На моём примере будет 1260.
И, пожалуй, самый сложный вариант - число 12399. К последней цифре не прибавить, тогда прибавляем к предпоследней. А к ней тоже не прибавишь. Получается, что и количество единиц, и количество десятков максимальное, в ход идёт третья цифра справа (3 + 1 = 4), а последние две обнуляются. Ответ в данном случае 12400.
Еще один по аналогии: 456999 + 1 будет 457000.
И на последок когда все цифры - 9. Например, 99999 + 1 = 100000 (ну это я и писал во 2м абзаце).
Стоит ли еще раз подчёркивать, что данный алгоритм работает в любой системе счисления? Не только в десятичной!
IV. Нолики в конце и в начале
Число 6 - это, на самом деле, "6 единиц и 0 десятков и 0 сотен и 0 тысяч и так далее" (потому что оно меньше и 1 десятка, и 1 сотни, и 1 тысячи, ...). Соответственно, мы можем спереди записывать много (хоть бесконечно) ноликов, которые не имеют никакого смысла. К примеру, 6 = 000000000006. Эти нули (до первой ненулевой цифры) - "незначащие", потому что от них толку особо то и нет, и ничего они не значат, на число никак не влияют. Другой пример: 451 = 00451 = 0000000000000000000451 - и это верно.
Что касается ноликов в конце - тоже интересная вещь. Вы же понимаете, что "сотня" (100) - это "десять десятков" (10 x 10), а "тысяча" (1000) - это "сто десятков" (100 x 10) и так далее (10000 = 1000 x 10, 100000 = 10000 x 10, ...). К чему же я это. А к тому, что с десятками мы можем работать на самом деле так же, как и с единицами.
Например, мы знаем, что 1345 + 926 = 2271.
А что мы знаем про сумму 13450 + 9260 (1345 десятка + 926 десятков)? Понятно, что это равно 22710 (2271 десятков).
Ну и 1345000 + 926000 = 2271000 тоже очевидно по аналогии.
V. Сложение и вычитание чисел
Принцип "единицы с единицами, десятки с десятками" и так далее. Квадратные скобочки в примере ниже обозначают 1 цифру:
1234 + 5678 = [1 + 5][2 + 6][3 + 7][4 + 8] = [1 + 5][2 + 6][3 + 7][12] =
В единицам мы видим 12 (1 x 10 + 2 x 1), то есть +1 десяток переносим влево, а 2 записываем: = [1 + 5][2 + 6][3 + 7 + 1][2] = [1 + 5][2 + 6][11][2] =
В десятках мы видим 11 (1 x 10 + 1 x 1), то есть +1 сотню переносим влево, а 1 записываем: = [1 + 5][2 + 6 + 1][1][2] = [1 + 5][2 + 6 + 1][1][2] = 6912
Идея при вычитании точно такая же. И да, если количество цифр не равно, то можно уровнять его этими самыми незначащими нулями спереди (12 + 345 = 012 + 345).
Тут тоже квадратные скобки обозначают 1 цифру. При вычислении мы же всегда идём с единиц (если пойдём наоборот, слева направо, то поймём, что если единицы у нас вылезут за десяток, то придётся всё заново пересчитывать... у нас смещение цифры идёт влево, поэтому логично начинать считать справа и налево, т. е. начиная с единиц)
12349 - 5678 = 12349 - 05678 = [1 - 0][2 - 5][3 - 6][4 - 7][9 - 8] = [1 - 0][2 - 5][3 - 6][4 - 7][1] =
С единицами всё ок, но в десятках у нас идёт
Всё то же самое, 3 - 6 - 1 = -4 = -10 + 6, то есть опять вычитаем 1 цифру в разряде слева: = [1 - 0][2 - 5][3 - 6 - 1][7][1] = [1 - 0][2 - 5 - 1][6][7][1] = [1 - 0 - 1][6][6][7][1] = 06671, и убираем этот ненужный нам нолик, остаётся 6671. Я на последнем шаге уже решил не останавливаться: 2 - 5 - 1 = -4 = -10 + 6. Осталось 6, а один разряд слева уменьшили на 1.
Ответ: 6671.
VI. Переход между системами счисления
У нас есть администратор на форуме Евген 1137, поэтому давайте 1137 и переведём в 6-чную систему счисления, в которой у нас будут только цифры 0, 1, 2, 3, 4 и 5.
Числа в 10-чной системе по порядку: 0, 1, 2, 3, 4, 5, 6, 7, 08, 09, 10
Числа в 6-чной системе по порядку: 0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14
То есть 10 в 10чной равно 14 в 6чной.
Число 1137 = 1 x 1000 + 1 x 100 + 3 x 10 + 7 x 1 = 1 x 10 x 10 x 10 + 1 x 10 x 10 + 3 x 10 + 7 x 1
Все эти числа переводим из 10чной в 6чную:
Наш план такой: разбиваем (как показано 2 строками выше) число в сумму единиц, десятков, сотен и т. д. Все эти числа переводим в новую систему, и дальше считаем уже в ней. Поэтому не ошибитесь и не напишите, мол, 4 x 3 = 12. Действия, начиная с этого момента, производятся в НОВОЙ системе!
Итого у нас: 1 x 14 x 14 x 14 + 1 x 14 x 14 + 3 x 14 + 11 x 1
Надеюсь, цветовое выделение помогает понимать что откуда...
Ну считаем:
1) 14 x 14 = 14 x (10 + 4) = 14 x 10 + 14 x 4 = 140 + (10 + 4) x 4 = 140 + 40 + 4 x 4 =
Так... 4 x 4 это сколько?
1, 2, 3, 4,
5, 10, 11, 12,
13, 14, 15, 20,
21, 22, 23, 24
Получается 24...
= 140 + 040 + 024 = [1 + 0 + 0][4 + 4 + 2][0 + 0 + 4] = [1 + 0 + 0][4 + 4 + 2][4] =
= [1 + 0 + 0 + 1][4][4] = 244.
2) 14 x 14 x 14 = 244 x 14 = 244 x (10 + 4) = 2440 + 244 x 4 = 2440 + (200 + 40 + 4) x 4 = 2440 + 200 x 4 + 40 x 4 + 4 x 4 =
Как умножать с ноликами в конце? Да просто...
= 2440 + 1200 + 240 + 24 = 2440 + 1200 + 0240 + 0024 = [2 + 1 + 0 + 0][4 + 2 + 2 + 0][4 + 0 + 4 + 2][0 + 0 + 0 + 4] = [2 + 1 + 0 + 0][4 + 2 + 2 + 0 + 1][4][4] = [2 + 1 + 0 + 0][4 + 2 + 2 + 0 + 1][4][4] = [2 + 1 + 0 + 0 + 1][3][4][4] = [4][3][4][4] = 4344.
3) Начинаем складывать:
1 x 4344 + 1 x 244 + 3 x 14 + 11 x 1 = 4344 + 244 + 3 x 10 + 3 x 4 + 11 = 4344 + 244 + 30 + 20 + 11 = 4344 + 0244 + 0030 + 0020 + 0011 = [4][3 + 2][4 + 4 + 3 + 2 + 1][4 + 4 + 1] = [4][3 + 2][4 + 4 + 3 + 2 + 1 + 1][3] = [4][3 + 2 + 2][3][3] = [4 + 1][1][3][3] = 5133.
При умножении
Ответ: 5133.
VII. Комбинаторика процесса
Сколько у нас n-значных чисел в системе счисления с основанием k (я буду писать цифры не от 0 до k - 1, а буду писать от 1 до k - количество чисел такое же, но воспринимается легче)?
Для простоты возьмём n = 2, тогда имеем варианты:
11, 12, 13, ..., 1k
21, 22, 23, ..., 2k
31, 32, 33, ..., 3k
...
k1, k2, k3, ..., kk
Итого k^2 (k в квадрате). А теперь представьте, что у нас еще добавляется 3 цифра - она тоже может быть любой от 1 до k (на самом деле от 0 до k - 1, но я написал выше почему так легче). Итого для каждого варианта этой 3й цифры у нас k^2 двузначных (из 2х цифр), значит с 3мя цифрами будет k * k^2 = k^3.
Ответ на вопрос напрашивается сам: k^n.
На примере. Сколько у нас трёхзначных чисел (в данном случае имеется ввиду, что 0 спереди тоже стоять может, поэтому правильнее - НЕ более чем трёхзначных)? Ну 10^3 = 1000. Действительно, так и есть! Работает.
IIX. Ближе к программированию
Вопрос номер 2. У нас имеется байт (8 бит, где бит - это у нас либо 0, либо 1). Сколько разных значений может принимать байт?
На самом деле бит - это цифра в двоичной системе (0 или 1). А сколько у нас может быть НЕ более чем 8и значных чисел?
2^8 = 256. Так и есть, обычный байт может принимать 256 разных значений, например, такой:
Также обычно адреса памяти, RGB-цвета и прочее записываются в шестнадцатеричной системе счисления. Вы, естественно, спросите, а откуда ж нам взять еще 6 цифр (у нас то их 10, а как записывать еще те 6)? Их записывают с помощью английских букв A-F (или маленькими a-f, это неважно). Поэтому цифры такой системы (HEX она называется) следующие: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
Чтобы указать, что число записывается в HEX, спереди пишут "0x". Поэтому 0x4ABF398 - это обычное число, и ничего более.
Стоит отметить, что двухзначное число в HEX может принимать 16^2 = 256 значений, ровно как 1 байт. Вообще существует такое понятие как порядок байтов (как число записывается в памяти). Зачастую я встречал little endian (он же применяется в гта и самп), это обратный порядок.
Поэтому если у вас в памяти записано
Что касается отрицательный чисел - там применяется дополнительный код, что немного не входит в тему систем счисления, поэтому просто оставлю ссылку.
IIX. Простой перевод между некоторыми системами счисления
Как вы будете переводить из, например, двоичной 0b0110101101 в восьмеричную? Да, "0b" - это просто запись в двоичной, как и "0x" - ничего страшного и умного нету в этом. Если разбивать 1 x 0b1 + 0 x 0b10 + 1 x 0b100 + 1 x 0b1000 и так далее, а потом это всё переводить и складывать (как показал я выше) - то можно и ночь встретить с этим занятием...
Всё дело в том, что 2^3 = 8, а это означает, что 3 цифры в двоичной системе дают 8 разных значений, ровно как 1 цифра в 8чной системе.
Поэтому наше число можно разбить на тройки, начиная с конца (я спереди дописал 2 нолика, чтобы на тройки разбилось), 0b 000 110 101 101.
Теперь перевести все трёхзначных числа двоичной в восьмеричную:
0b000 = 0
0b001 = 1
0b010 = 2
0b011 = 3
0b100 = 4
0b101 = 5
0b110 = 6
0b111 = 7
Ну и переводите, заменяя старое на новое: 0655 = 655 (ненужный ноль убираем). Вот и перевели... Делов то!
Точно также можно переводить между любыми системами, где основание одной в какой-то степени даёт основание второй (2^4 = 16, поэтому легко из двоичной [binary] в шестнадцатеричную [hexadecimal]). По аналогии можно и наоборот, 1 цифру заменять на несколько.
Поэтому перевести из 8чной в 16чную просто через 2чную (8 = 2^3; 16 = 2^4) по цепочке: 8 -> 2 -> 16. Поупражняйтесь!
Кстати говоря, если есть необходимость перевода из десяточной в двоичную - то считать по показанному мной методу очень долго... Вам же нужно будет каждую цифру переводить в двоичную (1 десятичная цифра может перейти даже в 4значное число двоичной), а потом умножать, суммировать, КОШМАР!
Уж проще перевести в HEX и потом по такой простой цепочке каждое значение (0x0 — 0xF) перевести в четвёрку значений (0b0000 — 0b1111) двоичной.
Я бы не сказал, что системы счисления напрямую относятся к программированию, но всё же это достаточно интересная и прикладная тема.
Разные системы счисления используются в программировании (в основном - двоичная, шестнадцатеричная и десятичная), поэтому они достойны обсуждения и объяснения "на пальцах".
Статья рассчитана на тех, кто не знает про системы счисления, всё изложено максимально информативно и подробно, начиная с нуля.
I. Сколько цифр мы используем в числах?
Начать стоит с определения.
1) Число - величина, используемая для счёта (1, 2, 3...). Используется везде: и для подсчёта количества чего-либо, и для указания температуры, давления, скорости, расстояния, объёма, массы и других физических, геометрических, химических величин, и как идентификатор чего-либо и т. д. У чисел очень много применений.
Числа никогда не кончаются, их бесконечно. То есть нельзя назвать "самое большое число", для любого числа можно назвать число, которое больше него.
2) Цифра - символ, используемый для записи неотрицательных целых чисел (потому что минус [для отрицательных] и точка [для нецелых] не являются цифрами). В нашей, десятичной, системе цифр всего десять: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. И всё.
Почему их десять - вопрос не по адресу. Я слышал, что ответ кроется в том, что на руках 10 пальцев. На самом деле, количество цифр совсем необязательно должно быть равно 10, и мы это скоро поймём.
II. Как строится десятичное (и не только) число?
От 0 до 9 всё понятно, просто одна цифра и всё. А дальше у нас цифры закончились, что же делать?
На самом деле идея достаточно простая, но словами объяснить её достаточно трудно. Следующее число после 9 - это десять. И количество этих "десятков" давайте записывать второй цифрой (потому что одной нам уже не хватает) справа. То есть, к примеру, число 26 - это 2 десятка и еще (плюс) 6. Говорят обычно "2 десятка и 6 единиц", типа 6 раз по 1 (т. е. 6 x 1 = 6).
Поэтому следующее число после 9 будет иметь вид "один десяток и ноль единиц" (т. е. просто 1 десяток, больше нам единиц не надо), записывается оно как 10. Дальше мы прибавляем к нему единицы (11, 12, 13...), пока можем - и в какой-то момент мы упрёмся в 19. После 9 идёт десять, а если у нас 19 (1 десяток и 9), то у нас "9" отсюда заменится на еще 1 десяток, будет 2 десятка (т. е. 20). Думаю, логика ясна.
Аналогично, когда закончатся все вариации с двумя цифрами (максимальное количество десятков, что мы можем записать - 9, и с единицами то же самое) - это на числе 99. Следующее число назовём сотня и количество этих сотен будет записывать третьей цифрой справа. Чтобы было ясно, то напишу так:
9 + 1 = 10
99 + 1 = 100
999 + 1 = 1000
9999 + 1 = 10000
99999 + 1 = 100000
и так далее
Понятное дело, что такой принцип применим не только к десятичной системе, а к любой (с любым основанием). Основание системы счисления - это количество цифр, которое в ней используется.
III. Как строить следующее число (+1) - алгоритм
Кратко проговорим алгоритм построения следующего числа, чтобы закрепить знания из предыдущего абзаца.
И так, у нас число 12906. Если мы можем прибавить к единицам еще 1 (в данном случае 6 + 1 = 7) - просто делаем это: получается 12907.
А если мы не можем прибавить, как в числе 1259. Ну тогда после 9 у нас идёт 1 десяток (а количество единиц при этом обнуляется), увеличиваем на 1 предыдущую цифру (5 + 1 = 6). На моём примере будет 1260.
И, пожалуй, самый сложный вариант - число 12399. К последней цифре не прибавить, тогда прибавляем к предпоследней. А к ней тоже не прибавишь. Получается, что и количество единиц, и количество десятков максимальное, в ход идёт третья цифра справа (3 + 1 = 4), а последние две обнуляются. Ответ в данном случае 12400.
Еще один по аналогии: 456999 + 1 будет 457000.
И на последок когда все цифры - 9. Например, 99999 + 1 = 100000 (ну это я и писал во 2м абзаце).
Стоит ли еще раз подчёркивать, что данный алгоритм работает в любой системе счисления? Не только в десятичной!
IV. Нолики в конце и в начале
Число 6 - это, на самом деле, "6 единиц и 0 десятков и 0 сотен и 0 тысяч и так далее" (потому что оно меньше и 1 десятка, и 1 сотни, и 1 тысячи, ...). Соответственно, мы можем спереди записывать много (хоть бесконечно) ноликов, которые не имеют никакого смысла. К примеру, 6 = 000000000006. Эти нули (до первой ненулевой цифры) - "незначащие", потому что от них толку особо то и нет, и ничего они не значат, на число никак не влияют. Другой пример: 451 = 00451 = 0000000000000000000451 - и это верно.
Можете на математике бесить училку этими нулями, как я делал когда-то, хахахах
Что касается ноликов в конце - тоже интересная вещь. Вы же понимаете, что "сотня" (100) - это "десять десятков" (10 x 10), а "тысяча" (1000) - это "сто десятков" (100 x 10) и так далее (10000 = 1000 x 10, 100000 = 10000 x 10, ...). К чему же я это. А к тому, что с десятками мы можем работать на самом деле так же, как и с единицами.
Например, мы знаем, что 1345 + 926 = 2271.
А что мы знаем про сумму 13450 + 9260 (1345 десятка + 926 десятков)? Понятно, что это равно 22710 (2271 десятков).
Ну и 1345000 + 926000 = 2271000 тоже очевидно по аналогии.
V. Сложение и вычитание чисел
Принцип "единицы с единицами, десятки с десятками" и так далее. Квадратные скобочки в примере ниже обозначают 1 цифру:
1234 + 5678 = [1 + 5][2 + 6][3 + 7][4 + 8] = [1 + 5][2 + 6][3 + 7][12] =
В единицам мы видим 12 (1 x 10 + 2 x 1), то есть +1 десяток переносим влево, а 2 записываем: = [1 + 5][2 + 6][3 + 7 + 1][2] = [1 + 5][2 + 6][11][2] =
В десятках мы видим 11 (1 x 10 + 1 x 1), то есть +1 сотню переносим влево, а 1 записываем: = [1 + 5][2 + 6 + 1][1][2] = [1 + 5][2 + 6 + 1][1][2] = 6912
Идея при вычитании точно такая же. И да, если количество цифр не равно, то можно уровнять его этими самыми незначащими нулями спереди (12 + 345 = 012 + 345).
Тут тоже квадратные скобки обозначают 1 цифру. При вычислении мы же всегда идём с единиц (если пойдём наоборот, слева направо, то поймём, что если единицы у нас вылезут за десяток, то придётся всё заново пересчитывать... у нас смещение цифры идёт влево, поэтому логично начинать считать справа и налево, т. е. начиная с единиц)
12349 - 5678 = 12349 - 05678 = [1 - 0][2 - 5][3 - 6][4 - 7][9 - 8] = [1 - 0][2 - 5][3 - 6][4 - 7][1] =
С единицами всё ок, но в десятках у нас идёт
4 - 7 = -3. Нам не подходит, поэтому вычтем 1 сотню и прибавим сколько нужно десятков: 3 = 10 - 7, поэтому, домножая уравнение на минус единицу, получаем -3 = -10 + 7. Нам надо вычесть 1 сотню, а количество десятков будет равным 7: = [1 - 0][2 - 5][3 - 6 - 1][7][1] =Всё то же самое, 3 - 6 - 1 = -4 = -10 + 6, то есть опять вычитаем 1 цифру в разряде слева: = [1 - 0][2 - 5][3 - 6 - 1][7][1] = [1 - 0][2 - 5 - 1][6][7][1] = [1 - 0 - 1][6][6][7][1] = 06671, и убираем этот ненужный нам нолик, остаётся 6671. Я на последнем шаге уже решил не останавливаться: 2 - 5 - 1 = -4 = -10 + 6. Осталось 6, а один разряд слева уменьшили на 1.
Ответ: 6671.
VI. Переход между системами счисления
У нас есть администратор на форуме Евген 1137, поэтому давайте 1137 и переведём в 6-чную систему счисления, в которой у нас будут только цифры 0, 1, 2, 3, 4 и 5.
Числа в 10-чной системе по порядку: 0, 1, 2, 3, 4, 5, 6, 7, 08, 09, 10
Числа в 6-чной системе по порядку: 0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14
То есть 10 в 10чной равно 14 в 6чной.
Число 1137 = 1 x 1000 + 1 x 100 + 3 x 10 + 7 x 1 = 1 x 10 x 10 x 10 + 1 x 10 x 10 + 3 x 10 + 7 x 1
Все эти числа переводим из 10чной в 6чную:
1 -> 1; 1 -> 1; 3 -> 3; 7 -> 11.Наш план такой: разбиваем (как показано 2 строками выше) число в сумму единиц, десятков, сотен и т. д. Все эти числа переводим в новую систему, и дальше считаем уже в ней. Поэтому не ошибитесь и не напишите, мол, 4 x 3 = 12. Действия, начиная с этого момента, производятся в НОВОЙ системе!
Итого у нас: 1 x 14 x 14 x 14 + 1 x 14 x 14 + 3 x 14 + 11 x 1
Надеюсь, цветовое выделение помогает понимать что откуда...
Ну считаем:
1) 14 x 14 = 14 x (10 + 4) = 14 x 10 + 14 x 4 = 140 + (10 + 4) x 4 = 140 + 40 + 4 x 4 =
Так... 4 x 4 это сколько?
1, 2, 3, 4,
5, 10, 11, 12,
13, 14, 15, 20,
21, 22, 23, 24
Получается 24...
= 140 + 040 + 024 = [1 + 0 + 0][4 + 4 + 2][0 + 0 + 4] = [1 + 0 + 0][4 + 4 + 2][4] =
4 + 4 + 2 = 14 (см. таблицу умножения 4 x 4, оттуда выделяем 4, потом 4, потом еще 2 числа)= [1 + 0 + 0 + 1][4][4] = 244.
2) 14 x 14 x 14 = 244 x 14 = 244 x (10 + 4) = 2440 + 244 x 4 = 2440 + (200 + 40 + 4) x 4 = 2440 + 200 x 4 + 40 x 4 + 4 x 4 =
Как умножать с ноликами в конце? Да просто...
200 x 4 = 2 x 100 x 4 = 2 x 4 x 100 = 12 x 100 = 1200, 2 x 4 смотрим из удобной таблицы, которую мы написали выше.= 2440 + 1200 + 240 + 24 = 2440 + 1200 + 0240 + 0024 = [2 + 1 + 0 + 0][4 + 2 + 2 + 0][4 + 0 + 4 + 2][0 + 0 + 0 + 4] = [2 + 1 + 0 + 0][4 + 2 + 2 + 0 + 1][4][4] = [2 + 1 + 0 + 0][4 + 2 + 2 + 0 + 1][4][4] = [2 + 1 + 0 + 0 + 1][3][4][4] = [4][3][4][4] = 4344.
3) Начинаем складывать:
1 x 4344 + 1 x 244 + 3 x 14 + 11 x 1 = 4344 + 244 + 3 x 10 + 3 x 4 + 11 = 4344 + 244 + 30 + 20 + 11 = 4344 + 0244 + 0030 + 0020 + 0011 = [4][3 + 2][4 + 4 + 3 + 2 + 1][4 + 4 + 1] = [4][3 + 2][4 + 4 + 3 + 2 + 1 + 1][3] = [4][3 + 2 + 2][3][3] = [4 + 1][1][3][3] = 5133.
При умножении
3 x 4 и сложении 4 + 4 + 3 + 2 + 1 и других я смотрел в таблицу сверху, очень удобно...Ответ: 5133.
VII. Комбинаторика процесса
Сколько у нас n-значных чисел в системе счисления с основанием k (я буду писать цифры не от 0 до k - 1, а буду писать от 1 до k - количество чисел такое же, но воспринимается легче)?
Для простоты возьмём n = 2, тогда имеем варианты:
11, 12, 13, ..., 1k
21, 22, 23, ..., 2k
31, 32, 33, ..., 3k
...
k1, k2, k3, ..., kk
Итого k^2 (k в квадрате). А теперь представьте, что у нас еще добавляется 3 цифра - она тоже может быть любой от 1 до k (на самом деле от 0 до k - 1, но я написал выше почему так легче). Итого для каждого варианта этой 3й цифры у нас k^2 двузначных (из 2х цифр), значит с 3мя цифрами будет k * k^2 = k^3.
Ответ на вопрос напрашивается сам: k^n.
На примере. Сколько у нас трёхзначных чисел (в данном случае имеется ввиду, что 0 спереди тоже стоять может, поэтому правильнее - НЕ более чем трёхзначных)? Ну 10^3 = 1000. Действительно, так и есть! Работает.
IIX. Ближе к программированию
Вопрос номер 2. У нас имеется байт (8 бит, где бит - это у нас либо 0, либо 1). Сколько разных значений может принимать байт?
На самом деле бит - это цифра в двоичной системе (0 или 1). А сколько у нас может быть НЕ более чем 8и значных чисел?
2^8 = 256. Так и есть, обычный байт может принимать 256 разных значений, например, такой:
C++:
unsigned char c; // от 0 до 255 (всего 256 значений)Также обычно адреса памяти, RGB-цвета и прочее записываются в шестнадцатеричной системе счисления. Вы, естественно, спросите, а откуда ж нам взять еще 6 цифр (у нас то их 10, а как записывать еще те 6)? Их записывают с помощью английских букв A-F (или маленькими a-f, это неважно). Поэтому цифры такой системы (HEX она называется) следующие: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
Чтобы указать, что число записывается в HEX, спереди пишут "0x". Поэтому 0x4ABF398 - это обычное число, и ничего более.
Стоит отметить, что двухзначное число в HEX может принимать 16^2 = 256 значений, ровно как 1 байт. Вообще существует такое понятие как порядок байтов (как число записывается в памяти). Зачастую я встречал little endian (он же применяется в гта и самп), это обратный порядок.
Поэтому если у вас в памяти записано
unsigned число (это целое неотрицательное) 0x11223344, то в память будут следующие байты: { 0x44, 0x33, 0x22, 0x11 } - просто "задом наперед по парам". То есть число 0x12345678 будет в памяти при таком порядке байтов как little endian выглядеть вот так { 0x78, 0x56, 0x34, 0x12 }. Просто полезная инфа.Что касается отрицательный чисел - там применяется дополнительный код, что немного не входит в тему систем счисления, поэтому просто оставлю ссылку.
IIX. Простой перевод между некоторыми системами счисления
Как вы будете переводить из, например, двоичной 0b0110101101 в восьмеричную? Да, "0b" - это просто запись в двоичной, как и "0x" - ничего страшного и умного нету в этом. Если разбивать 1 x 0b1 + 0 x 0b10 + 1 x 0b100 + 1 x 0b1000 и так далее, а потом это всё переводить и складывать (как показал я выше) - то можно и ночь встретить с этим занятием...
Всё дело в том, что 2^3 = 8, а это означает, что 3 цифры в двоичной системе дают 8 разных значений, ровно как 1 цифра в 8чной системе.
Поэтому наше число можно разбить на тройки, начиная с конца (я спереди дописал 2 нолика, чтобы на тройки разбилось), 0b 000 110 101 101.
Теперь перевести все трёхзначных числа двоичной в восьмеричную:
0b000 = 0
0b001 = 1
0b010 = 2
0b011 = 3
0b100 = 4
0b101 = 5
0b110 = 6
0b111 = 7
Ну и переводите, заменяя старое на новое: 0655 = 655 (ненужный ноль убираем). Вот и перевели... Делов то!
Точно также можно переводить между любыми системами, где основание одной в какой-то степени даёт основание второй (2^4 = 16, поэтому легко из двоичной [binary] в шестнадцатеричную [hexadecimal]). По аналогии можно и наоборот, 1 цифру заменять на несколько.
Поэтому перевести из 8чной в 16чную просто через 2чную (8 = 2^3; 16 = 2^4) по цепочке: 8 -> 2 -> 16. Поупражняйтесь!
Кстати говоря, если есть необходимость перевода из десяточной в двоичную - то считать по показанному мной методу очень долго... Вам же нужно будет каждую цифру переводить в двоичную (1 десятичная цифра может перейти даже в 4значное число двоичной), а потом умножать, суммировать, КОШМАР!
Уж проще перевести в HEX и потом по такой простой цепочке каждое значение (0x0 — 0xF) перевести в четвёрку значений (0b0000 — 0b1111) двоичной.
Последнее редактирование:
