Как найти количество единиц в информатике

Самый эффективный метод следующий: пока число (его надо интерпретировать как беззнаковое число, чтобы подсчитать все единицы), допустим n, не равно нулю выполнить следующую операцию

n &= n - 1;

и соответственно увеличить счетчик единиц на единицу.

Принцип следующий. Допустим в числе имеется одна 1

0b00100000

Если из этого числа вычесть 1, то получится

0b00011111

Теперь если применить бинарную операцию И, то получим

0b00100000
&
0b00011111
==========
0b00000000

Число стало равным 0, следовательно оно содержало только одну 1, так как данная операция была проделана только один раз.

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

Привет! Сегодня исследуем 10 Задание из ОГЭ по информатике 2023.

Задание 9 из ОГЭ по информатике Вы можете научиться решать, прочитав статью по 13 заданию из ЕГЭ по информатике. Эту статью Вы можете найти здесь.

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

Задача (Классическая)

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

14₁₆, 26₈, 11000₂.

Решение:

Число 14 находится в шестнадцатеричной системе. Об этом говорит маленький индекс возле числа. Переведём его в нашу родную десятичную систему.

Берём поочередно цифры, начиная с младшего разряда. Первую правую цифру умножаем на 16 в нулевой степени, вторую цифру на 16 в первой степени и т.д. Умножаем на 16, потому что переводим из шестнадцатеричной системы. Степень потихоньку увеличивается на 1.

Необходимо помнить, что любое число в нулевой степени это единица!

Остаётся только посчитать полученный пример. Получается число 20 в десятичной системе.

Переведём число 26₈ из восьмеричной системы в нашу родную десятичную систему. Делаем аналогично предыдущему примеру.

Аналогично переведём число и из двоичной системы.

Наибольшее из трёх чисел это 24.

Ответ: 24

Задача (Классическая, закрепление)

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

1D₁₆, 36₈, 11011₂

Решение:

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

Переведём первое число.

Переведём второе число.

Переведём третье число.

Наибольшее число получается 30.

Ответ: 30

Задача (Из десятичной в двоичную)

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

59₁₀, 71₁₀, 81₁₀

Решение:

Нужно каждое число перевести в двоичную систему счисления.

Переведём число 59₁₀ в двоичную систему.

Получается 59₁₀ = 111011₂. Здесь мы делим уголком на 2 (на основание системы, куда переводим) с остатком. Продолжаем делить, пока не получим 1. Затем остатки записываем задом наперёд. Получается число в двоичной системе счисления. Последнее число 1 (единицу) тоже берём.

Переведём число 71₁₀ в двоичную систему.

Получается 71₁₀ = 1000111₂.

Переведём число 81₁₀ в двоичную систему.

Получается 81₁₀ = 1010001₂.

Найдём количество единиц для каждого числа, записанного в двоичной системе.

111011₂, Кол. ед.: 5
1000111₂, Кол ед.: 4
1010001₂, Кол ед.: 3

Ответ: 3

Задача (Из десятичной в восьмеричную)

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

86₁₀, 99₁₀, 105₁₀

Решение:

Переведём число 86₁₀ в восьмеричную систему.

Делаем аналогично тому, как мы переводили в двоичную систему, только теперь уголком делим на 8. Остатки могут получатся от 0 до 7.

Как только в результате деления получили число меньшее, чем 8, то завершаем процесс перевода.

Остатки опять записываем задом наперёд. Последнее число тоже участвует в формировании результата наравне с остатками.

Получается 86₁₀ = 126₈.

Переведём число 99₁₀ в восьмеричную систему.

Получается 99₁₀ = 143₈.

Переведём число 105₁₀ в восьмеричную систему.

Получается 105₁₀ = 151₈.

Найдём сумму цифр у полученных чисел.

126₈, Сумма цифр: 9
143₈, Сумма цифр: 8
151₈, Сумма цифр: 7

Наименьшая сумма цифр равна 7.

Ответ: 7

Разберём несколько нестандартных тренировочных задач для подготовки к 10 заданию ОГЭ по информатике.

Задача(Неожиданная)

Число 3322_n записано в системе счисления с основанием n (n > 1). Определите наименьшее возможное значение n. Для этого значения n в ответе запишите представление данного числа в десятичной системе счисления. Основание системы счисления указывать не нужно.

Решение:

Наименьшее значение n в этой задаче может быть равно 4, потому что самая большая цифра — это тройка. Мы берём на 1 больше, т.к. в четверичной системе могут применяться только цифры: 0, 1, 2, 3. Тоже самое, как в нашей родной десятичной системе могут применяться 10 цифр: от нуля, до девяти. Самая большая цифра в нашей родной десятичной системе девятка.

Осталось перевести данное число из четверичной системы в десятичную.

Ответ: 250

Задача (Уже знаем)

Число 2023_n записано в системе счисления с основанием n (n > 1). Определите значение n, при котором данное число минимально. Для этого значения n в ответе запишите представление данного числа в десятичной системе счисления. Основание системы счисления указывать не нужно.

Решение:

Здесь нужно, чтобы само число 2023_n было минимальным. Но это число будет минимальным, если мы выберем самое маленькое значение n при данных цифрах.

Самое маленькое основание системы может вновь 4. Переведём наше число 2023₄ из четверичной системы в десятичную.

Получается число 139.

Ответ: 139

Задача (Крепкий орешек)

Число 121_n записано в системе счисления с основанием n (n > 1). Определите наибольшее возможное значение n, для которого 121_n < 108₁₀. Для этого значения n в ответе запишите представления данного числа в десятичной системе счисления. Основание системы счисления указывать не нужно.

Решение:

Мы не знаем в какой системе счисления записано число. Но всё равно начнём переводить его в десятичную систему, оставив переменную n в виде неизвестной.

Попробуем подобрать n.

При n=10

1*10⁰ + 2*10¹ + 1*10² = 121 > 108₁₀

Перебор. Ну это и так было понятно.

Значит, нужно уменьшать n. Возьмём n = 9.

1*9⁰ + 2*9¹ + 1*9² = 100 < 108₁₀

Как раз получилось число, которое меньше числа 108₁₀. Это и есть наибольшее n!

В ответе просили перевести исходное число в десятичную систему. Это и есть число 100, уже всё переведено.

Ответ: 100

Задача (Не все цифры одинаковые)

Десятичное число 511 записано в системе счисления с основанием n (n > 1). Определите минимальное значение n, при котором в полученной записи числа не все цифры одинаковые. В ответе запишите запись числа в системе счисления с найденным основанием n. Основание системы счисления указывать не нужно.

Решение:

Начнём перебирать основание системы n, начиная с наименьшего значения 2. Переведём число 511₁₀ в двоичную систему.

Можно переводить стандартно, через деление уголком на 2. Но в данном случае видно, что число 511 близко к 512. Число 512 = 2⁹.

Существует правило:

2⁴ = 10000₂
2⁶ = 1000000₂

Т.е. степень двойки показывает, сколько после единицы нулей у числа в двоичной системе.

Это касается любой системы счисления.

3² = 100₃
3³ = 1000₃

Наше число

511₁₀ = 512₁₀ — 1 = 2⁹ — 1 = 1000000000₂ — 1

Сделаем вычитание столбиком.

Вычитание или суммирование столбиком в любой системе счисления выполняются так же, как и в нашей системе счисления. Здесь мы вычитаем единицу из нуля. Ноль идёт занимать у более старшего разряда и т.д. В итоге обращаемся к самой старшей единице. Эта единица превращается в младшем разряде в двойку, потому что работаем в двоичной системе. Как и в нашей системе, когда занимаем у старшего разряда единицу, она превращается в десяток. В итоге каждая двойка отдаёт единицу в младший разряд. В самом младшем разряде получается действие 2-1=1. А все разряды, т.к. отдали единицу в младший разряд превратятся в 1.

Получается 511₁₀ = 200221₃.

Видим, что не все цифры у числа одинаковые в троичной системе. И число n = 3 — это минимально возможное число.

Ответ: 200221

Задача(Диапазон чисел)

Сколько существует целых чисел x, для которых выполняется неравенство

2B₁₆ < x < 62₈?

В ответе укажите только количество чисел, сами числа писать не нужно.

Решение:

Нам нужно узнать сколько чисел находятся в диапазоне от 2B₁₆ до 62₈.
Переведём числа 2B₁₆ и 62₈ в нашу родную десятичную систему счисления. Затем, мы уже сможем сообразить, сколько чисел вмещается в этот диапазон.

Чтобы перевести число из любой системы счисления в нашу родную десятичную, необходимо воспользоваться методом «возведения в степень».

Начинаем с младшего разряда. Цифра «B» превращается в 11. 2B₁₆ = 43₁₀. Теперь переведём число
62₈ в десятичную систему.

Таким образом, наше неравенство принимает вид 43 < x < 50. Кажется, что нужно сделать 50 — 43 = 7. Но если мы подставим небольшие числа 4 < x < 6, то мы увидим, что метод 6-4=2 неверен. Число будет только одно: 5 (пять). Поэтому и от нашего числа 7 мы тоже должны отнять единицу. 7 — 1 = 6. И ответ будет 6.

Если бы у нас было в одном месте знак «больше или равно»: 2B₁₆ ≤ x < 62₈, то мы бы оставили число 7. А если было бы два знака «больше или равно», то даже прибавили единицу.

Ответ: 6

Всего: 47    1–20 | 21–40 | 41–47

Добавить в вариант

Всего: 47    1–20 | 21–40 | 41–47

Решение задач 1 ЕГЭ по информатике 2015 года

Рассмотрим задачу №1 из демоверсии  ФИПИ 2015 года:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110.Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы В – 101
2) это невозможно
3) для буквы В – 010
4) для буквы Б – 10

Давайте проанализируем текст задачи. Итак, нам известно, что используется неравномерный двоичный код. Что это такое? На самом деле все очень просто:

равномерное кодирование — каждый символ кодируется кодами равной длины

неравномерное кодирование — разные символы могут кодироваться кодами разной длины

Например, если у нас есть три символа А, Б, В и закодированы они так:

• А — 010
• Б — 011
• В — 111

, то это равномерное кодирование, так как длина кода одинаковая. Если же эти же символы мы закодируем вот так:

• А — 01
• Б — 110
• В — 1011

, то получим неравномерное кодирование.

Кроме этого, нам необходимо знать и понимать условие Фано

Никакое кодовое слово не может быть началом другого кодового слова

Также существует обратное условие Фано

Никакое кодовое слово не является окончанием другого кодового слова

Чтобы однозначно декодировать сообщение, достаточно того, чтобы условие Фано (или обратное условие) выполнялось.

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

Рассмотрим первый вариант ответа. Если мы для буквы В сократим код до 101, то условие Фано нарушено не будет. Действительно, с кода 101 не начинается ни один из четырех оставшихся кодов для А, Б, Г и Д и все коды различны.

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

Третий вариант не подходит, так как в этом случае код буквы В — 010 будет начинаться с 0, а 0 — это код буквы А. Получается, что это нарушает условие Фано.

Вариант 4 тоже не подходит. В этом случае код буквы Б — 10 будет являться началом для кода буквы В, а это нарушение условия Фано.

Правильный ответ: 1.

Для успешного решения задач типа А1 ЕГЭ по информатике рекомендую ознакомиться со статьями “Системы счисления” и “Перевод чисел из двоичной системы счисления в десятичную”. Для контроля правильности перевода удобно использовать “Скрипт для перевода числа из десятичной системы счисления в любую другую”.

Задачи А1 предполагают проверку знаний  о  системах  счисления  и  двоичном  представлении информации в памяти компьютера.

Рассмотрим решение задачи А1 из демоверсии ЕГЭ 2012.

Сколько единиц в двоичной записи числа 1025?
1)   1
2)   2
3)   10
4)   11

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

Как видно, в полученном двоичном числе содержится 2 единицы.

Второй способ решения данной задачи рассчитан на тех, кто хорошо знает степени числа 2. Если посмотреть на число 1025 внимательно, можно заметить, что 1025=1024+1. Число 1024 – это 2¹⁰. Отсюда следует, что 1025=2¹⁰+1.

Если посмотреть как выглядят степени числа 2 записанные в двоичной системе счисления, то нетрудно представить число 1024 в двоичной системе счисления.

Прибавив к получившемуся числу единицу получим число 10000000001₂, которое содержит 2 единицы.

Третий способ вытекает из предыдущего. Если посмотреть внимательно, то можно увидеть, что любое число, являющееся степенью двойки и записанное в двоичной системе счисления содержит одну единицу. Таким образом узнать количество единиц в двоичной записи любого числа очень просто — достаточно представить его как сумму степеней числа 2 — количество слагаемых и будет указывать число единиц.

Возьмем для примера число 73 и узнаем сколько единиц в его двоичной записи.

73=64+8+1=2⁶+2³+2⁰. Так как слагаемых у нас получилось три, значит и единиц в двоичной записи числа 73 будет тоже 3.

Решение задачи А1 демонстрационной версии ЕГЭ 2013:

Сколько единиц в двоичной записи десятичного числа 255?

1) 1        2) 2        3) 7        4) 8

Первый способ:

Для успешного решения данной задачи необходимо знать, что 256 это 2 в восьмой степени или 10000 0000 в двоичной системе счисления — 256=2⁸=100000000₂. Соответственно, 255 — это 11111111 в двоичной системе счисления — 255₁₀=11111111₂. Правильный ответ — 4 (8 единиц).

Второй способ:

Этот способ заключается в переводе числа 255 из десятичной системы счисления в двоичную и подсчете единиц:

Как видим, количество единиц восемь. Правильный ответ 4.

Автор: