Сколько единиц в двоичной записи
Перейти к содержимому

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

  • автор:

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

Данная задачка судя по всему типовая в ЕГЭ по информатике, алгоритм ее решения в общем случае следующий: перевести число в двоичную форму (например, тут — http://floatingpoint.ru/online/dec2bin.php) и подсчитать количество единиц — калькулятор нулей и единиц в двоичной записи числа

Однако в некоторых простых случаях можно попробовать разложить искомое число на сумму или разность степеней двоек, и проделать вычисления в уме.

Для этого нужно помнить несколько первых степеней двойки и двоичные записи по крайней мере некоторых чисел от 1 до 15:

1024 = 2^10, 512 = 2^9, 256 = 2^8, 128 = 2^7, 64 = 2^6, 32 = 2^5, 16 = 2^4

15 = 1111, 14 = 1110, 13 = 1101, 12 = 1100, 11 = 1011, 10 = 1010, 9 = 1001, 8 = 1000, 7 = 111, 6 = 110, 5 = 101, 4 = 100, 3 = 11, 2 = 10, 1 = 1.

Так же могут оказаться полезны некоторые суммы, например:

Приведем некоторые типовые примеры.

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

1025 = 1024 + 1 1024 = 2^10 это степень двойки, а единица так и будет единицей, следовательно, 
всего в двоичной записи числа 1025 ровно 2 единицы.

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

519 = 512 + 7 512 = 2^9 это степень двойки, а 7 записывается в двоичной системе как 111 и содержит три единицы, 
следовательно, всего в двоичной записи числа 519 содержится ровно 4 единицы.

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

514 = 512 + 2 Слагаемые 512 = 2^9 и 2 = 2^1 - это степени двойки, следовательно, в двоичной записи числа 514 
ровно 2 единицы.

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

127 = 128 - 1 Число 128 представляет собой целую степень двойки и равняется 2^7, требуя таким образом 
для своей записи ровно 8 бит: 10000000 10000000-1 = 1111111 Следовательно, в записи числа 127 содержится 7 единиц.

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

195 = 192 + 3 = 128 + 64 + 3 128 = 2^7 64 = 2^6 3 = 11 в двоичной системе и содержит 2 единицы. Таким образом в двоичной записи числа 195 
содержится 4 единицы.

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

173 = 160 + 13 160 = 128 + 32 = 2^7 + 2^5, а 13 = 1101 в двоичной системе. Тогда всего получим 5 единиц.

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

3458 = 2048 + 1410 1410 = 1024 + 386 386 = 256 + 130 130 = 128 + 2 Таким образом 3458 = 2^11 + 2^10 + 2^8 + 2^7 + 2^1 и всего будет 5 единиц.

Страница учителя информатики Колгановой О.Е.

5. Выполняем вычитание, то, поскольку в конце у обоих чисел есть 4022 нуля, они останутся без изменения, а вот перед ними будут одни единицы. Так же будет и с уменьшаемым. И единиц этих будет 8040 – 4022 = 4018 .

6. Прибавляемое число 2 2012 гораздо меньше, чем первые два, единица у него стоит на 2013 месте справа, а у нас в конце (как мы говорили раньше) 4022 нуля, поэтому после сложения в итоговом числе появится 1 на 2013 месте (среди нулей).

7. Следовательно, всего единиц будет 4018+1=4019

Повторение материала

Перевод чисел из 2-й системы в 10-ю систему счисления

Двоичная система счисления — это позиционная система счисления с основанием 2.

Количество используемых цифр называется основанием позиционной системы счисления.

В позиционных системах счисления величина, обозначаемая цифрой в записи числа, зависит от позиции.

Для записи чисел в двоичной системе используются всего две цифры (0 и 1).

В позиционных системах счислениях вес каждой цифры изменяется в зависимости от положения (позиции) в последовательности цифр, изображающих число.

Место записи цифры в числе называется разрядом числа . Разряды чисел именуются справа налево от разряда единиц к большему числу, каждый разряд имеет свой номер и место в записи числа.

В двоичном числе 10110 – 5 цифр и 5 разрядов (в информатике разряды считаются, начиная с нулевого разряда (разряд единиц), которому соответствует младший бит).

Понятная информатика,

Обозначим через N основание системы счисления.

Тогда наибольшая цифра в системе счисления с основанием N равна N-1.

  • Любое основание N в своей системе счисления выглядит как 10, т.е.

(например: 210=102, 310=103, 810=108, 1610=1016 и так далее).

  • Степень любого основания N в своей системе счисления выглядит как единица и количество нулей, равных степени, т.е.

(например: 4=22=1002, 8=23 =10002, 16=24=100002 и так далее).

  • Число, стоящее перед k-той степенью основания, в своей системе счисления выглядит как последовательность из k самых больших цифр этой системы счисления, т.е.

Тогда 2 k – 1 = 1…12

(например: 3=22-1=112, 7=23 -1=1112, 15=24-1=11112 и так далее).

  • Число N k – N m = N k · (N k-m – 1) записывается в системе счисления с основанием N как k-m старших цифр этой системы счисления, за которыми следует k нулей:

m – k k

m – k k

(например: 103 — 102 = 900, 103 — 101 = 990, 105 — 103 = 99000, 25 – 22 = 111002, 35 – 32 = 222003 и так далее).

Примеры и способы решения задач.

Задача 1.

Сколько единиц в двоичной записи числа 8 1025 + 2 1024 – 3 ?

Приведем все числа в заданном примере к одному виду с основанием 2 и упорядочим их в порядке убывания степеней, с учетом того, что 3 = 4 — 1:

8 1025 + 2 1024 – 3 = 2 3075 + 2 1024 – 2 2 + 2 0

Количество единиц в разности 2 1024 – 2 2 будет 1024-2 = 1022 единицы + 1 единица (число 2 4032 ) + 1 единица от числа 20, то всего получаем 1022+1+1 = 1024 единицы.

Задача 2.

Сколько единиц в двоичной записи числа 8 2014 – 2 614 + 4 5 ?

Приведем все числа в заданном примере к одному виду с основанием 2 и упорядочим их в порядке убывания степеней, с учетом того, что 45 = 32 + 8 + 4 + 1:

8 2014 – 2 614 + 4 5 = 2 6042 — 2 614 + 2 5 + 2 3 + 2 2 + 2 0

Количество единиц в разности 2 6042 — 2 614 будет 6042 – 614 = 5428 единиц + 4 единицы от чисел 2 5 , 2 3 , 2 2 и 2 0 , то всего получаем 5428+4 = 5432 единицы.

Задача 3.

Значение арифметического выражения 4 10 + 2 90 — 16 записали в системе счисления с основанием 2. Сколько цифр «1» содержится в этой записи?

Приведем все числа в заданном примере к одному виду с основанием 2 и упорядочим их в порядке убывания степеней:

2 20 + 2 90 – 2 4 = 2 90 + 2 20 – 2 4

Тогда после перевода в двоичную систему счисления в числе 2 90 будет 1 единица, в разности 2 20 – 2 4 будет

20 — 4 = 16 единиц и 4 нуля. Следовательно, в полученном результате получаем всего 16 + 1 = 17 единиц.

Задача 4.

Значение арифметического выражения 6 410 + 2 60 — 16 записали в системе счисления с основанием 8. Сколько цифр «7» содержится в этой записи?

Приведем все числа в заданном примере к одному виду с основанием 8 и упорядочим их в порядке убывания степеней, учитывая, что 16 = 8 + 8:

4 12 + 2 60 — 16 = 8 20 + 8 30 – 16 = 8 30 + 8 20 – 8 1 – 8 1

Ищем в разности крайнюю левую степень восьмерки и крайнюю правую 8 20 – 8 1 , при этом среднюю 8 1 на время «теряем».

Определяем количество семерок в разности 8 20 – 8 1 , получаем 20 — 1 = 19 семерок.

Так как «внутри» этой разности есть еще 8 1 , то просто вычитаем одну семерку: 19 – 1 = 18.

Задача 5.

Сколько единиц в двоичной записи числа 4 2018 + 8 305 – 2 130 – 120 ?

Приведем все числа в заданном примере к одному виду с основанием 2 и упорядочим их в порядке убывания степеней, с учетом того, что 45 = 32 + 8 + 4 + 1:

4 2018 + 8 305 – 2 130 – 120 = 2 4036 + 2 915 – 2 130 — 2 7 + 2 3

Ищем в разности (2915 – 2130 — 27) крайнюю левую степень двойки и крайнюю правую 2 915– 2 7 , при этом среднюю 2 130 на время «теряем».

Определяем количество семерок в разности 2 915 – 2 7 , получаем 915-7 = 908 единиц.

Так как «внутри» этой разности есть еще 2 130 , то просто вычитаем одну единицу: 908 – 1 = 907.

Прибавляем 2 единицы от чисел 2 4036 и 2 3 , то всего получаем 907 + 2 = 909 единиц.

Задача 6.

Значение арифметического выражения 9 9 – 3 9 + 9 19 – 19 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Приведем все числа в заданном примере к одному виду с основанием 3 и упорядочим их в порядке убывания степеней, учитывая, что 19 = 27 – 8 + 1+1:

9 9 – 3 9 + 9 19 – 27 + 9 — 1 -1 = 3 18 + 3 38 – 3 3 + 3 2 – 3 0 = 3 38 + 3 18 – 3 3 + 3 2 – 3 0 – 3 0

Разбиваем нашу запись на две разности 3 18 – 3 3 и 3 2 – 3 0 и вычисляем их отдельно.

Количество двоек в разности 3 18 – 3 3 будет 18-3 = 15, в разности 3 2 – 3 0 будет равно 2, всего 15 + 2 = 17 двоек. Вычитаем из них еще одну единицу, так как 3 0 = 12. При этом последняя цифра меняется как 2-1=1, в результате получаем 17-1 = 16 двоек.

Задача 7.

Сколько значащих нулей в двоичной записи числа 4 512 + 8 512 – 2 128 – 250 ?

Приведем все числа в заданном примере к одному виду с основанием 2 и упорядочим их в порядке убывания степеней, учитывая, что 250 = 256 – 4 – 2 = 2 8 – 2 2 — 2 1 :

4 512 + 8 512 – 2 128 – 256+ 4 + 2 = 2 1024 + 2 1536 – 2 128 – 2 8 + 2 2 + 2 1 = = 2 1536 + 2 1024 – 2 128 – 2 8 + 2 2 + 2 1

Ищем в разности 2 1024 – 2 128 – 2 8 крайнюю левую степень двойки и крайнюю правую 2 1024 –2 8 , при этом среднюю 2 128 на время «теряем».

В разности 2 1024 –2 8 будет 1024 — 8 = 1016 единиц и 8 нулей.

Так как «внутри» этой разности есть еще 2 128 , то просто заменяем одну единицу (на 128 месте) на ноль и получаем 1015 единиц и 9 нулей.

С этого момента можно решать задачу двумя способами:

1) Между 2 1536 и 2 1024 (до конца числа) есть еще 1536-1024=512 нулей, два из которых заняты единицами (22+21), тогда получаем еще 512-2 = 510 нулей.

Итого в результате вычислений получаем 510+9 = 519 нулей.

Можно показать это вычисление на схеме, где вычисляемая выше разность выделена черным цветом:

Всего 1 ед. + 1534 нуля + 2 ед.в конце _

1 ед.+1022 нуля + 2 ед.в конце

2 1536 _ + _ 2 1024 – 2 128 – 2 8 + 2 2 + 2 1

1 ед.+510 нулей + 1015 ед. + 9 нулей + 2 ед.

2) Посчитать общее число единиц после выполнения вычислений и вычесть их общей длины исходного двоичного числа.

2 1536 + 2 1024 – 2 128 – 2 8 + 2 2 + 2 1

1 ед. + 1015 ед. + 2 ед . = 1018 ед.

Так как 2 1536 = 10…0 2 равна 1537 знаков, то в нем будет 1537-1018 = 519 нулей.

Задача 8.

Сколько единиц в двоичной записи числа 4 2016 + 2 2018 – 8 600 + 6 ?

Приведем все числа в заданном примере к одному виду с основанием 2 и упорядочим их в порядке убывания степеней, учитывая, что 6 = 4 + 2:

4 2016 + 2 2018 – 8 600 + 6 = 2 4032 + 2 2018 – 2 1800 + 2 2 + 2 1

После перевода числа 2 4032 в двоичную систему оно будет состоять из 1 единицы и 4032 нулей.

Количество единиц в разности 2 2018 – 2 1800 будет 2018-1800 = 218 единиц + 1 единица (число 24032) + 2 единицы от чисел 2 2 и 2 1 , то всего получаем 218+3 = 221 единицу.

Задача 9.

Сколько единиц в двоичной записи числа 4 2016 – 2 2018 + 8 800 – 80?

Приведем все числа в заданном примере к одному виду с основанием 2 и упорядочим их в порядке убывания степеней, учитывая, что 80 = 64 + 16:

4 2016 – 2 2018 + 8 800 – 80= 2 4032 — 2 2018 + 2 2400 – 2 6 — 2 4 = 2 4032 + 2 2400 — 2 2018 – 2 6 — 2 4

Далее рассмотрим два способа решения задачи.

1). После перевода числа 2 4032 в двоичную систему оно будет состоять из 1 единицы и 4032 нулей.

Из записи 2 2400 — 2 2018 – 2 6 — 2 4 возьмем разность первого и последнего чисел 2 2400 — 2 4 и получаем 2396 единиц. Вычитаем из них 2 единицы, которые дают числа 2 6 и 2 4 , остается 2394 единицы.

Тогда всего получаем 1 + 2394 = 2395 единиц.

2). Будем решать данную задачу путем последовательных вычитаний.

После перевода числа 2 4032 в двоичную систему оно будет состоять из 1 единицы и 4032 нулей.

Количество единиц в разности 2 4000 – 2 2018 будет 4000-2018 = 382 и 2018 нулей.

Оставляем 381 единицу, используя далее 1 единицу и 2018 нулей, что равно числу 2 2018 .

Далее, в разности 22018 — 26 будет 2012 единиц и 6 нулей.

Оставляем 2011 единиц, остается число 2 6 . Тогда разность 2 6 – 2 4 получаем 2 единицы.

Складываем все единицы и получаем 1 + 381 + 2011 + 2 = 2395 единиц.

Подсчитать количество единиц в двоичной записи огромного числа

Задача: Сколько единиц содержится в двоичной записи значения выражения: 4^2020 + 2^2017 – 15? Так как число превышает допустимое значение типа double, моя программа выводит неправильный ответ: vr = infinity, count = 1. (count должен равняться 2015)

 double vr = Math.Pow(4, 2020) + Math.Pow(2, 2017) - 15; // наше выражение string b = Convert.ToString((int)vr, 2); int count = 0; //счётчик единиц for (int i = 0; i < b.Length; i++) < if (b[i] == '1') < count++; >> Console.WriteLine(count); 

Отслеживать
задан 1 мая 2023 в 9:42
71 5 5 бронзовых знаков
Воспользуйтесь BigInteger.Pow, а не Math.Pow
1 мая 2023 в 9:53
Считать большие числа не надо, это задача на логику, решается в уме
1 мая 2023 в 10:03
@Kalmankantaja, спасибо, ответ получился правильный!
1 мая 2023 в 10:46
добавь ожидаемый результат в вопрос
1 мая 2023 в 10:47
Остаётся понять, является ли эта задача хорошей учебной задачей по программированию.
1 мая 2023 в 11:45

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

@MBo! В двоичной записи числа 4 одна единица (100), и в какую целую степень его не возводи, так одна единица и останется. Например: 4^2=16 (10000). Тоже самое касается и двойки. Сразу преобразуем 4^2020 в 2^4040.

Далее, в двоичной системе. Если к одному числу вида 1 с нулями добавить меньшее такого же вида, то получится 2 единицы, например: 10000+100=10100. Теперь найдём разность большого числа и 15, например: 1000 0000 0000-1111=111 1111 0001, то есть такое вычитание добавляет Z-4 единиц, где Z — степень наименьшей единицы в числе, которая равна степени меньшего числа. Итого ответ равен 2+Z-4=Z-2

Вот и ответ: 2015.

И вправду ошибка была, даже две.

Отслеживать
ответ дан 1 мая 2023 в 11:10
3,994 2 2 золотых знака 3 3 серебряных знака 18 18 бронзовых знаков
Где-то просчитались, т. к. правильный ответ — 2015.
1 мая 2023 в 11:14
Там не разность, а сумма двух больших степеней, бОльшая просто добавит одну единицу
1 мая 2023 в 11:39
@MBo так и есть. Как говорится, смотришь в книгу — видишь (фи)совсем другое.
1 мая 2023 в 11:42
В десятичной записи числа 4 — в десятичной записи в числе 4 — нет единиц
1 мая 2023 в 14:39

Решение с использованием класса BigInteger:

 BigInteger vr = BigInteger.Pow(4, 2020) + BigInteger.Pow(2, 2017) -15; Console.WriteLine(BigInteger.PopCount(vr)); 

Отслеживать
ответ дан 1 мая 2023 в 10:55
71 5 5 бронзовых знаков
1 мая 2023 в 12:47

  • c#
  • консоль
  • числа
  • системы-счисления
    Важное на Мете
Похожие

Подписаться на ленту

Лента вопроса

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

Дизайн сайта / логотип © 2024 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2024.2.14.4854

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *