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

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

Данная задачка судя по всему типовая в ЕГЭ по информатике, алгоритм ее решения в общем случае следующий: перевести число в двоичную форму (например, тут — 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.

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

приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 2 7 – 2 2 – 2 1 :

4 2015 + 8 405 – 2 150 – 122 = (2 2 ) 2015 +(2 3 ) 405 – 2 150 –2 7 + 2 2 + 2 1 =

= 2 4030 +2 1215 – 2 150 –2 7 + 2 2 + 2 1

вспомним, число 2 N –2 K приK<Nзаписывается какN–Kединиц иKнулей:

для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2 N –2 K , причём в этой цепочке степени двойки нужно выстроить по убыванию

в нашем случае вы выражении

2 4030 + 2 1215 – 2 150 – 2 7 + 2 2 + 2 1

стоит два знака «минус» подряд, это не позволяет сразу использовать формулу

используем теперь равенство , так что – 2 150 = – 2 151 + 2 150 ; получаем

2 4030 +2 1215 – 2 151 +2 150 – 2 7 + 2 2 + 2 1

здесь две пары 2 N –2 K , а остальные слагаемые дают по одной единице

общее число единиц равно 1 + (1215 – 151) + (150 – 7) + 1 + 1 = 1210

Решение (С.О. Куров, Москва):

приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 2 7 – 2 2 – 2 1 :

4 2015 + 8 405 – 2 150 – 122 = (2 2 ) 2015 +(2 3 ) 405 – 2 150 –2 7 + 2 2 + 2 1 =

= 2 4030 +2 1215 – 2 150 –2 7 + 2 2 + 2 1

ищем в разностикрайнюю левую степень двойки и крайнюю правую 2 1215 – 2 7 , при этом 2 150 на время «теряем»

определяем количество единиц в разности 2 1215 – 2 7 , получаем 1215 – 7 = 1208 единиц

так как «внутри» этой разности есть еще 2 150 , то просто вычитаем одну единицу: 1208 – 1 = 1207; итого в разности 2 1215 – 2 150 – 2 7 ровно 1207 единиц

осталось прибавить по одной единицы от чисел 2 4030 , 2 2 , 2 1

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

Р-19. Решите уравнение.

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

переведём все числа в десятичную систему счисления:

собирая всё в одно уравнение получаем

это уравнение имеет два решения, 6 и -8; основание системы счисления – натуральное число, поэтому ответ – 6

переводим ответ в троичную систему: 6 = 2∙3 1 = 20₃.

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

Р-18. Сколько единиц в двоичной записи числа 4 2014 + 2 2015 – 8

приведём все числа к степеням двойки:

4 2014 + 2 2015 – 8 = (2 2 ) 2014 + 2 2015 –2 3 =2 4028 + 2 2015 – 2 3

вспомним, что число 2 N -1 в двоичной системе записывается какNединиц:, а число2 N –2 K приK<Nзаписывается какN–Kединиц иKнулей:

согласно п. 2, число 2 2015 – 2 3 запишется как 2012 единиц и 3 нуля

прибавление 2 4028 даст ещё одну единицу, всего получается 2012 + 1 = 2013 единиц

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

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

приведём все числа к степеням двойки, разложив 6 как 2 2 +2 1

4 2016 + 2 2018 – 8 600 + 6 = (2 2 ) 2016 + 2 2018 -(2 3 ) 600 + 2 2 + 2 1 =2 4032 + 2 2018 – 2 1800 + 2 2 + 2 1

вспомним, что число 2 N -1 в двоичной системе записывается какNединиц:, а число2 N –2 K приK<Nзаписывается какN–Kединиц иKнулей:

согласно п. 2, число 2 2018 – 2 1800 запишется как 218 единиц и 1800 нулей

прибавление 2 4032 даст ещё одну единицу, а прибавление 2 2 + 2 1 – ещё две, всего получается 218 + 3 = 221 единица

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

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

приведём все числа к степеням двойки, разложив 80 как 2 6 +2 4

4 2016 – 2 2018 + 8 800 – 80 = (2 2 ) 2016 – 2 2018 +(2 3 ) 800 – 2 2 – 2 1 =2 4032 – 2 2018 + 2 2400 – 2 6 – 2 4

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

2 4032 + 2 2400 – 2 2018 – 2 6 – 2 4

вспомним, что число 2 N -1 в двоичной системе записывается какNединиц:, а число2 N –2 K приK<Nзаписывается какN–Kединиц иKнулей:

согласно п. 2, число 2 2400 – 2 2018 запишется как 382 единицы и 2018 нулей

добавляем старшее слагаемое 2 4032 , получаем число 2 4032 + 2 2400 – 2 2018 , в котором 383 единицы и в конце (после последней единицы) – 2018 нулей:

выделим из этого значения последнюю единицу со следующими 2018 нулями как отдельное слагаемое (число 2 2018 ):

,

где число Kсодержит382 единицы в старших разрядах; таки образом, интересующее нас число равно

согласно п. 2, число 2 2018 – 2 6 запишется как 2012 единиц и 6 нулей; также выделим последнюю единицу с последующими нулями как отдельное слагаемое:

где число Lсодержит2011единиц

теперь остаётся найти, сколько единиц будет в двоичной записи числа 2 6 – 2 4 , согласно п. 2 находим, что оно содержит2единицы

таким образом, общее число единиц равно 382 + 2011 + 2 = 2395

Решение (способ 2, Е.А. Смирнов, Нижегородская область):

приведём все числа к степеням двойки, разложив 80 как 2 6 +2 4

4 2016 – 2 2018 + 8 800 – 80 = (2 2 ) 2016 – 2 2018 +(2 3 ) 800 – 2 2 – 2 1 =2 4032 – 2 2018 + 2 2400 – 2 6 – 2 4

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

2 4032 + 2 2400 – 2 2018 – 2 6 – 2 4

представим – 2 2018 = – 2 2019 + 2 2018 и – 2 6 = – 2 7 + 2 6

2 4032 + 2 2400 – 2 2019 + 2 2018 – 2 7 + 2 6 – 2 4

слагаемое 2 4032 в двоичной записи содержит1единицу

слагаемое 2 2400 – 2 2019 содержит381единицу (число2 N –2 K приK<Nв двоичной системе записывается какN–Kединиц иKнулей:)

слагаемое 2 2018 – 2 7 содержит2011единиц, слагаемое 2 6 – 2 4 содержит2единицы

позиции единиц во всех этих слагаемых не совпадают, поэтому общее количество единиц равно 1 + 381 + 2011 + 2 = 2395

Решение (способ 3, А.И. Козлов, г. Северобайкальск):

приведём все числа к степеням двойки, разложив 80 как 2 6 +2 4

4 2016 – 2 2018 + 8 800 – 80 = (2 2 ) 2016 – 2 2018 +(2 3 ) 800 – 2 2 – 2 1 =2 4032 – 2 2018 + 2 2400 – 2 6 – 2 4

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

2 4032 + 2 2400 – 2 2018 – 2 6 – 2 4

выражение 2 2400 –2 4 дает 2396 единиц и 4 нолика в конце, откуда вычеркиваем (заменяем на ноль) единичку, стоящую на седьмом месте справа (2 6 ) и, соответственно на 2019 месте справа (2 2018 ). Следовательно, остается2394единички.

С учетом того, что 2 4032 дает нам одну единицу, в итоге получаем2395единиц

Сколько единиц в двоичной записи десятичного числа 57, 63, 87, 90, 127

Рабочая тетрадь по Информатике 8 класс Босова
of your page —>
Задание 48. Сколько единиц в двоичной записи десятичного числа 57, 63, 87, 90, 127? Перевод числа 57 в двоичную систему методом разностей

Перевод числа 63 в двоичную систему методом разностей

Перевод числа 87 в двоичную систему методом разностей

Перевод числа 90 в двоичную систему методом разностей

Перевод числа 127 в двоичную систему методом разностей

Эффективнейшие методы для нахождения единиц в двоичном виде числа

Дано число в двоичной системе исчисления, например 10011010.
Какие есть эффективные методы узнать количество битов в этом числе, в которых значение равно TRUE?

Я придумал только два:

1. Число & 1 и если равно 1, то увеличивать счетчик, а потом число сдвигать на один в право.
2. Создать lookup table в котором индех — это числа от 0 до 255, а значение это кол-во едениц в этом числе.

Какие еще есть методы?

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

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

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

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

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

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

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

Ознакомился со статьёй по ссылке от VladD.
Оптимальный метод для 32-разрядного слова содержит 3 строчки суммарно на 12 операций:

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

P.S. (17.11.2017) Если речь идёт о младших 32 разрядах слова большей разрядности, то ранее приведённый алгоритм требует дополнительной очистки верхних разрядов с &= 0x3F .

Стал актуальным алгоритм для 64-битного слова (3 строчки, 12 операций):

Алгоритм собирает сумму по методу двоичного слияния.
При сложении чётных и нечётных битов использовано тождество: g+l = (2g+l)-l.
При слиянии побайтовых сумм значимы только 7 младших разрядов, и верхние разряды обрезаются один раз.

Кстати: при использовании масок можно подсчитать сумму любых битов 64-разрядного слова.