Сколько единиц в двоичной записи числа 195?

Базовый уровень, время – 1 мин)

Тема: Системы счисления и двоичное представление информации в памяти компьютера.

Что нужно знать:

· перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной системами счисления (см. презентацию «Системы счисления»)

Полезно помнить, что в двоичной системе: · четные числа оканчиваются на 0, нечетные – на 1; · числа, которые делятся на 4, оканчиваются на 00, и т.д.; числа, которые делятся на 2^k, оканчиваются на k нулей · если число N принадлежит интервалу 2^k-1£ N < 2^k, в его двоичной записи будет всего k цифр, например, для числа 125: 2⁶ = 64 £ 125 < 128 = 2⁷, 125 = 1111101₂ (7 цифр) · числа вида 2^k записываются в двоичной системе как единица и k нулей, например: 16 = 2⁴ = 10000₂ · числа вида 2^k-1записываются в двоичной системе k единиц, например: 15 = 2⁴-1 = 1111₂ · если известна двоичная запись числа N, то двоичную запись числа 2·N можно легко получить, приписав в конец ноль, например: 15 = 1111₂, 30 = 11110₂, 60 = 111100₂, 120 = 1111000₂

· желательно выучить наизусть таблицу двоичного представления чисел 0-7 в виде триад (групп из 3-х битов):

X ₁₀, X ₈	X₂	X ₁₀, X ₈	X₂
0	000	4	100
1	001	5	101
2	010	6	110
3	011	7	111

и таблицу двоичного представления чисел 0-15 (в шестнадцатеричной системе – 0-F₁₆) в виде тетрад (групп из 4-х битов):

X ₁₀	X₂	X ₁₀	X₁₆	X₂
0	0000	8	8	1 000
1	0001	9	9	1 001
2	0010	10	A	1 010
3	0011	11	B	1 011
4	0100	12	C	1 100
5	0101	13	D	1 101
6	0110	14	E	1 110
7	0111	15	F	1 111

· отрицательные целые числа хранятся в памяти в двоичном дополнительном коде (подробнее см. презентацию «Компьютер изнутри»)

· для перевода отрицательного числа (- a ) в двоичный дополнительный код нужно сделать следующие операции:

o перевести число a-1 в двоичную систему счисления;

o сделать инверсию битов: заменить все нули на единицы и единицы на нули в пределах разрядной сетки (см. пример Р-00 далее).

Пример задания:

Р-06. Сколько единиц в двоичной записи восьмеричного числа 1731₈?

Решение:

1) для решения достаточно знать двоичные коды чисел от 1 до 7, поскольку для перевода восьмеричного числа в двоичную систему можно достаточно каждую цифру отдельно записать в виде тройки двоичных (триады):

2) 1731₈ = 001 111 011 001₂

3) в этой записи 7 единиц

4) Ответ: 7

Ещё пример задания:

Р-05. Укажите наименьшее четырёхзначное восьмеричное число, двоичная запись которого содержит 5 единиц. В ответе запишите только само восьмеричное число, основание системы счисления указывать не нужно.

Решение:

5) вообще, минимальное двоичное число, содержащее 5 единиц – это 11111₂, но в восьмеричной системе оно записывается как 37 – двухзначное число

6) минимальное четырёхзначное восьмеричное число – 1000₈ = 1 000 000 000₂, для решения задачи в конце этого числа нужно заменить четыре нуля на единицы:

1 000 001 111₂ = 1017₈

7) Ответ: 1017

Ещё пример задания:

Р-04. Сколько единиц в двоичной записи десятичного числа 519?

Решение:

8) проще всего представить заданное число в виде суммы степеней числа 2:

519 = 512 + 7 = 2⁹ + 4 + 3 = 2⁹ + 2² + 2 + 1 = 2⁹ + 2² + 2¹ + 2⁰

9) количество единиц в двоичной записи числа равно количеству слагаемых в таком разложении

10) Ответ: 4

Ещё пример задания:

Р-03. Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел то, в двоичной записи которого содержится ровно 6 единиц. Если таких чисел несколько, укажите наибольшее из них.

1) 63₁₀* 4₁₀ 2) F8₁₆+ 1₁₀ 3) 333₈ 4) 11100111₂

Решение:

11) нужно перевести все заданные числа в двоичную систему, подсчитать число единиц и выбрать наибольшее из чисел, в которых ровно 6 единиц;

12) для первого варианта переведем оба сомножителя в двоичную систему:

63₁₀= 111111₂ 4₁₀= 100₂

в первом числе ровно 6 единиц, умножение на второе добавляет в конец два нуля:

63₁₀* 4₁₀= 111111₂* 100₂= 11111100₂

то есть в этом числе 6 единиц

13) для второго варианта воспользуемся связью между шестнадцатеричной и двоичной системами счисления: каждую цифру шестнадцатеричного числа можно переводить отдельно в тетраду (4 двоичных цифры):

F₁₆= 1111₂ 8₁₆= 1000₂ F8₁₆ = 1111 1000₂

после добавления единицы F8₁₆ + 1 = 1111 1001₂ также получаем число, содержащее ровно 6 единиц, но оно меньше, чем число в первом варианте ответа

14) для третьего варианта используем связь между восьмеричной и двоичной системами: каждую цифру восьмеричного числа переводим отдельно в триаду (группу из трёх) двоичных цифр:

333₈ = 011 011 011₂ = 11011011₂

это число тоже содержит 6 единиц, но меньше, чем число в первом варианте ответа

15) последнее число 11100111₂уже записано в двоичной системе, оно тоже содержит ровно 6 единиц, но меньше первого числа

16) таким образом, все 4 числа, указанные в вариантах ответов содержат ровно 6 единиц, но наибольшее из них – первое

17) Ответ: 1.

Ещё пример задания:

Р-02. Сколько единиц в двоичной записи числа 1025?

1) 1 2) 2 3) 10 4) 11

Решение (вариант 1, прямой перевод):

18) переводим число 1025 в двоичную систему: 1025 = 10000000001₂

19) считаем единицы, их две

20) Ответ: 2

Возможные проблемы: легко запутаться при переводе больших чисел.

Решение (вариант 2, разложение на сумму степеней двойки):

1) тут очень полезно знать наизусть таблицу степеней двойки, где 1024 = 2¹⁰ и 1 = 2⁰

2) таким образом, 1025= 1024 + 1 = 2¹⁰ + 2⁰

3) вспоминая, как переводится число из двоичной системы в десятичную (значение каждой цифры умножается на 2 в степени, равной её разряду), понимаем, что в двоичной записи числа ровно столько единиц, сколько в приведенной сумме различных степеней двойки, то есть, 2

4) Ответ: 2

Возможные проблемы: нужно помнить таблицу степеней двойки.

Когда удобно использовать: · когда число чуть больше какой-то степени двойки

Ещё пример задания:

Р-01. Дано: и . Какое из чисел с, записанных в двоичной системе счисления, удовлетворяет неравенству a < c < b?

1) 11011001₂ 2) 11011100₂ 3) 11010111₂ 4) 11011000₂

Общий подход:

перевести все числа (и исходные данные, и ответы) в одну (любую!) систему счисления и сравнить.

Решение (вариант 1, через десятичную систему):

7) переводим в десятичную систему все ответы:

11011001₂ = 217, 11011100 ₂= 220, 11010111₂ = 215, 11011000₂=216

8) очевидно, что между числами 215 и 217 может быть только 216

9) таким образом, верный ответ – 4 .

Возможные проблемы: арифметические ошибки при переводе из других систем в десятичную.

Решение (вариант 2, через двоичную систему):

1) (каждая цифра шестнадцатеричной системы отдельно переводится в четыре двоичных – тетраду);

2) (каждая цифра восьмеричной системы отдельно переводится в три двоичных – триаду, старшие нули можно не писать);

3) теперь нужно сообразить, что между этими числами находится только двоичное число 11011000₂ – это ответ 4.

Возможные проблемы: запись двоичных чисел однородна, содержит много одинаковых символов – нулей и единиц, поэтому легко запутаться и сделать ошибку.

Решение (вариант 3, через восьмеричную систему):

1) (сначала перевели в двоичную систему, потом двоичную запись числа разбили на триады справа налево, каждую триаду перевели отдельно в десятичную систему, так как для чисел от 0 до 7 их восьмеричная запись совпадает с десятичной);

2) , никуда переводить не нужно;

3) переводим в восьмеричную систему все ответы:

11011001₂ = 011 011 001₂ = 331₈(разбили на триады справа налево, каждую триаду перевели отдельно в десятичную систему, как в п. 1)

11011100 ₂= 334₈, 11010111₂ = 327₈, 11011000₂=330₈

4) в восьмеричной системе между числами 327₈ и 331₈ может быть только 330₈

5) таким образом, верный ответ – 4 .

Возможные проблемы: нужно помнить двоичную запись чисел от 0 до 7 (или переводить эти числа в двоичную систему при решении).

Решение (вариант 4, через шестнадцатеричную систему):

1) никуда переводить не нужно;

2) (сначала перевели в двоичную систему, потом двоичную запись числа разбили на тетрады справа налево, каждую тетраду перевели в шестнадцатеричную систему; при этом тетрады можно переводить из двоичной системы в десятичную, а затем заменить все числа, большие 9, на буквы – A, B, C, D, E, F);

3) переводим в шестнадцатеричную систему все ответы:

11011001₂ = 1101 1001₂ = D9₁₆(разбили на тетрады справа налево, каждую тетраду перевели отдельно в десятичную систему, все числа, большие 9, заменили на буквы – A, B, C, D, E, F, как в п. 1)

11011100 ₂= DC₁₆, 11010111₂ = D7₁₆, 11011000₂=D8₁₆

4) в шестнадцатеричной системе между числами D7₁₆ и D9₁₆ может быть только D8₁₆

5) таким образом, верный ответ – 4 .

Возможные проблемы: нужно помнить двоичную запись чисел от 0 до 15 (или переводить эти числа в двоичную систему при решении).

Выводы:

· есть несколько способов решения, «каждый выбирает для себя»;

· наиболее сложные вычисления – при переводе всех чисел в десятичную систему, можно легко ошибиться;

· сравнивать числа в двоичной системе сложно, также легко ошибиться;

· видимо, в этой задаче наиболее простой вариант – использовать восьмеричную систему, нужно просто запомнить двоичные записи чисел от 0 до 7 и аккуратно все сделать;

· в других задачах может быть так, что выгоднее переводить все в десятичную или шестнадцатеричную систему счисления.

Еще пример задания:

Р-00. Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (-78)?

1) 3 2) 4 3) 5 4) 6

Решение (вариант 1, классический):

1) переводим число 78 в двоичную систему счисления:

78 = 64 + 8 + 4 + 2 = 2⁶ + 2³ + 2² + 2¹ = 1001110₂

2) по условию число занимает в памяти 1 байт = 8 бит, поэтому нужно представить число с помощью 8 разрядов

3) чтобы получилось всего 8 разрядов (бит), добавляем впереди один ноль:

78 = 01001110₂

4) делаем инверсию битов (заменяем везде 0 на 1 и 1 на 0):

01001110₂ → 10110001₂

5) добавляем к результату единицу

10110001₂ + 1 = 10110010₂

это и есть число (-78) в двоичном дополнительно коде

6) в записи этого числа 4 единицы

7) таким образом, верный ответ – 2 .

Возможные ловушки и проблемы: · нужно не забыть в конце добавить единицу, причем это может быть не так тривиально, если будут переносы в следующий разряд – тут тоже есть шанс ошибиться из-за невнимательности

Решение (вариант 2, неклассический):

1) переводим число 78 – 1=77 в двоичную систему счисления:

77 = 64 + 8 + 4 + 1 = 2⁶ + 2³ + 2² + 2⁰ = 1001101₂

2) по условию число занимает в памяти 1 байт = 8 бит, поэтому нужно представить число с помощью 8 разрядов

3) чтобы получилось всего 8 разрядов (бит), добавляем впереди один ноль:

77 = 01001101₂

4) делаем инверсию битов (заменяем везде 0 на 1 и 1 на 0):

01001101₂ → 10110010₂

это и есть число (-78) в двоичном дополнительно коде

5) в записи этого числа 4 единицы

6) таким образом, верный ответ – 2 .

Возможные ловушки и проблемы: · нужно помнить, что в этом способе в двоичную систему переводится не число a, а число a-1; именно этот прием позволяет избежать добавления единицы в конце (легче вычесть в десятичной системе, чем добавить в двоичной)

Решение (вариант 3, неклассический):

1) переводим число 78 в двоичную систему счисления:

78 = 64 + 8 + 4 + 2 = 2⁶ + 2³ + 2² + 2¹ = 1001110₂

2) по условию число занимает в памяти 1 байт = 8 бит, поэтому нужно представить число с помощью 8 разрядов

3) чтобы получилось всего 8 разрядов (бит), добавляем впереди один ноль:

78 = 01001110₂

4) для всех битов, которые стоят слева от младшей единицы, делаем инверсию битов (заменяем везде 0 на 1 и 1 на 0):

01001110₂ → 10110010₂

это и есть число (-78) в двоичном дополнительно коде

5) в записи этого числа 4 единицы

6) таким образом, верный ответ – 2 .

Возможные ловушки и проблемы: · нужно помнить, что при инверсии младшая единица и все нули после нее не меняются