Задача № 5. Посчитать количество единичных битов числаФормулировка. Дано натуральное число меньше 16. Посчитать количество его единичных битов. Например, если дано число 9, запись которого в двоичной системе счисления равна 10012 (подстрочная цифра 2 справа от числа означает, что оно записано в двоичной системе счисления), то количество его единичных битов равно 2.Решение. Нам необходима переменная для ввода с клавиатуры. Обозначим ее как n. Так как мы должны накапливать количество найденных битов, то возникает потребность в еще одной переменной. Обозначим ее как count («count» в переводе с англ. означает «считать», «подсчет» и т. д.). Переменные возьмем типа byte (они могут принимать значения от 0 до 255), и пусть в данном случае такой объем избыточен, но это не принципиально важно.Как же сосчитать количество битов во введенном числе? Ведь число же вводится в десятич-ной системе счисления, и его нужно переводить в двоичную?На самом деле все гораздо проще. Здесь нам поможет одно интересное правило:Остаток от деления любого десятичного числа x на число p дает нам разряд единиц числа x (его крайний разряд справа) в системе счисления с основанием p.То есть, деля некоторое десятичное число, например, на 10, в остатке мы получаем разряд единиц этого числа в системе счисления с основанием 10. Возьмем, например, число 3468. Оста-ток от деления его на 10 равен 8, то есть разряду единиц этого числа.Понятно, что такие же правила господствуют и в арифметике в других системах счисления, и в том числе в двоичной системе. Предлагаю поэкспериментировать: запишите на бумаге десятичное число, затем, используя любой калькулятор с функцией перевода из одной системы счисления в другую, переведите это число в двоичную систему счисления и также запишите результат. Затем разделите исходное число на 2 и снова переведите в двоичную систему. Как оно изменилось в результате? Вполне очевидно, что у него пропал крайний разряд справа, или, как мы уже говорили ранее, разряд единиц.Но как это использовать для решения задачи? Воспользуемся тем, что в двоичной записи числа нет цифр, кроме 0 и 1. Легко убедиться в том, что сложив все разряды двоичного числа, мы получаем как раз таки количество его единичных битов. Это значит, что вместо проверки значе-ний разрядов двоичного представления числа мы можем прибавлять к счетчику сами эти разряды – если в разряде был 0, значение счетчика не изменится, а если 1, то повысится на единицу.Теперь, резюмируя вышеприведенный итог, можно поэтапно сформировать сам алгоритм:1) Вводим число n;2) Обнуляем счетчик разрядов count. Это делается потому, что значения всех переменных при запуске программы считаются неопределенными, и хотя в большинстве компилято-ров Pascal они обнуляются при запуске, все же считается признаком «хорошего тона» в программировании обнулить значение переменной, которая будет изменяться в процессе работы без предварительного присваивания ей какого-либо значения.3) Прибавляем к count разряд единиц в двоичной записи числа n, то есть остаток от деле-ния n на 2:count := count + n mod 2;Строго говоря, мы могли бы не прибавлять предыдущее значение переменной count к остатку от деления, так как оно все равно было нулевым. Но мы поступили так для того, чтобы сделать код более однородным, далее это будет видно. Учтя разряд единиц в дво-ичной записи n, мы должны отбросить его, чтобы исследовать число далее. Для этого разделим n на 2. На языке Pascal это будет выглядеть так:n := n div 2;4) Теперь нам нужно еще два раза повторить п. 3 , после чего останется единственный дво-ичный разряд числа n, который можно просто прибавить к счетчику без каких-либо до-полнений: count := count + n;5) В результате в переменной count будет храниться количество единичных разрядов в дво-ичной записи исходного числа. Осталось лишь вывести ее на экран.Код: 1. program BinaryUnits;2. 3. var4. n, count: byte;5. 6. begin7. readln(n);8. count := 0;9. count := count + n mod 2;10. n := n div 2;11. count := count + n mod 2;12. n := n div 2;13. count := count + n mod 2;14. n := n div 2;15. count := count + n;16. writeln(count)17. end.Программа работает правильно на всех вариантах правильных исходных данных, в чем не-сложно убедиться с помощью простой проверки.
>>783056 (OP)На ideone забанили?
>>783056 (OP)num = 9num = (( num >>1) & 0x55) + (num & 0x55)num = ((num >> 2) & 0x33) + (num & 0x33)num = ((num >> 4) & 0x0F) + (num & 0x0F)print num>> 2
>>783112num = 9num = (( num >>1) & 0x55) + (num & 0x55)num = ((num >> 2) & 0x33) + (num & 0x33)print num>> 2достаточно, более 4 бит не будет, третий раз сдвигать нет смысла.
>>783056 (OP)Тяжелый изврат.Такое можно сделать простым сдвигом и проверкой наличия бита D0 в цикле.Будет что-то вроде:for i := 1 to 5 dobegin if a and 1 then count := count + 1; n := n shr 1;end;Код не тестил.
Вся суть современных дебилов. Даже Кернигана и Ритчи осилить не могут.
>>783936Вот этого двачую. Решение норм, но есть смысл сделать в цикле.
>>783056 (OP)>>783063>>783068Есть порно с ней?
>>783985Только если фанатский. Dean Yegle, Mandy.
>>783056 (OP)Тебе ещё долго не нужно появляться на олимпиадках, бро.http://ideone.com/jgbwoF
>>783936Можно использовать побитовый and, в паскале он тоже вроде есть, и тогда if не нужен: http://try.haxe.org/#b362e
https://habrahabr.ru/post/276957/не благодари
>>783056 (OP)Не майся херней. Для подсчета битов числа у процессора есть инструкция popcnt.Вот пример на дишке:https://ideone.com/6Z2N1b
>>783056 (OP)>1. program BinaryUnits;>2. >3. var>4. n, count: byte;>5. >6. begin>7. readln(n);>8. count := 0;>9. count := count + n mod 2;>10. n := n div 2;>11. count := count + n mod 2;>12. n := n div 2;>13. count := count + n mod 2;>14. n := n div 2;>15. count := count + n;>16. writeln(count)>17. end.1. num = 132. print [256,128,64,32,16,8,4,2,1].map {|e| (num & e).zero? ? 0 : 1}.join
>>783056 (OP)__builtin_popcount(9);
>>783056 (OP)((((x 0x111) & 0x249) 0x249) >> 9) & 7
>>786531Смирись, твоё байтоёбство (битоёбство?) здесь нахуй не нужно, на всех современных процессорах есть POPCNT.
>>786560Смирюсь если ты охуеешь от того как я могу.
>>786569Извини, я уже охуел от стенфордской ACM тетрадки в своё время и всем советую.
>>786569>>786636Ой, перепутал с их битовой тетрадкой https://graphics.stanford.edu/~seander/bithacks.html.
>>783056 (OP)ОП, ты как раз и переводишь число в двоичную систему счисления, при этом ты:первое - открываешь при этом америку, а ещё нихуя не понимаешь, что делаешь, нашел млять "интересное правило", так и переводят числа в другие системы счисления, тебя этому должны были научить еще в средней школе.второе - вместо do...твоя-хуйня-с-делением...whileчисло-все-ещё-делится-с-ненулевым-частным городишь какую-то парашу, которая будет работать только на твоей разрядности (ну ты выбрал восемь бит я смотрю). Вангую восьмиклассника, который начал учить паскакаль.
>>783056 (OP)>Формулировка. Дано натуральное число меньше #!/bin/pythondef bitcnt(num_less_than_16) a=[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4] return a[num_less_than_16]
>>783056 (OP)Ах да, забыл добавить что ОП-хуй