Посчитайте число единиц в битовой записи числа считанного с клавиатуры и выведите на экран scala
Обновлено: 04.07.2024
эффективный способ подсчета числа 1s в двоичном представлении числа в O (1), Если у вас достаточно памяти для игры. Это вопрос интервью, который я нашел на онлайн-форуме, но у него не было ответа. Может кто-нибудь предложить что-то, я не могу придумать способ сделать это в O(1) Время?
Это вес Хэмминга проблема, ака подсчет населения. Ссылка упоминает эффективные реализации. Цитирование:
с неограниченной памятью мы могли бы просто создать большую таблицу поиска веса Хэмминга каждого 64-битного целого числа
у меня есть решение, которое подсчитывает биты в O(Number of 1's) время:
в худшем случае (когда число 2^n - 1, Все 1 в двоичном формате) он будет проверять каждый бит.
изменить: Просто нашел очень хороший алгоритм постоянного времени, постоянной памяти для bitcount. Вот оно, написано на C:
вы можете найти доказательство своей правоты здесь.
обратите внимание на то, что: n&(n-1) всегда устраняет наименее значимый 1.
следовательно, мы можем написать код для вычисления количества 1 следующим образом:
сложность программы будет: число 1 в n (которое постоянно
Я видел следующее решение с другого сайта:
функция принимает int и возвращает количество единиц в двоичном представлении
ниже приводится решение C с использованием битовых операторов:
следующее решение Java с использованием полномочий 2:
мы можем просто подсчитать набор бит (1), используя __строение_popcount().
int numOfOnes(int x)
цикл через все биты в целое число, проверьте, если бит установлен, и если это затем увеличить переменную count.
int hammingDistance(int x)
есть только один способ, который я могу придумать, чтобы выполнить эту задачу в O(1). то есть "обмануть" и использовать физическое устройство (с линейным или даже параллельным программированием я думаю, что предел-O(log(k)), где k представляет количество байтов числа).
однако вы можете очень легко представить себе физическое устройство, которое соединяет каждый бит с выходной линией с напряжением 0/1. Затем вы можете просто прочитать в электронном виде общее напряжение на линии "суммирования" в O(1). Это было бы вполне легко сделать эту основную идею более элегантной с некоторыми основными элементами схемы для получения выхода в любой форме, которую вы хотите (например, двоичный кодированный выход), но основная идея одна и та же, и электронная схема будет производить правильное состояние выхода в фиксированное время.
Я предполагаю, что есть также возможные возможности квантовых вычислений, но если нам позволят это сделать, я бы подумал, что простая электронная схема-это более простое решение.
Я пришел сюда, имея большую веру, что я знаю красивое решение этой проблемы. Код в C:
но после того, как я провел небольшое исследование по этой теме (читайте другие ответы:)) я нашел 5 более эффективных алгоритмов. Люблю так!
есть даже инструкция CPU, разработанная специально для этой задачи: popcnt . (упоминается в ответ)
описание и бенчмаркинг многих алгоритмов вы можете найти здесь.
ниже метод может подсчитать количество 1s в отрицательных числах, а также.
однако число, подобное -1, представлено в двоичном виде как 1111111111111111111111111111111111 и поэтому потребует много сдвига. Если вы не хотите делать так много сдвигов для небольших отрицательных чисел, другой способ может быть следующим:
в python или любом другом преобразовании в строку bin затем разделите ее с помощью "0", чтобы избавиться от 0, затем объедините и получите длину.
С использованием строковых операций в JS можно сделать следующим образом:
или
двумя способами:
где binaryValue-это двоичная строка, например: 1100
Вопрос предельно прост: надо посчитать количество единиц в двоичном представлении числа за О(1). Линии и логарифмы даже не предлагайте. Интересует только О(1).
Всего не более CHAR_BIT * sizeof(n) итераций, то есть, ограничено константой.
Вот ещё вам классический Кернигановский способ:
Ограничение сверху то же, но на практике работает быстрее, т. к. использует одну итерацию на единичный бит.
Подборка различных способов подсчёта битов есть тут.
Обратите внимание, что хитрые компиляторы знают Кернигановский метод, и (на некоторых платформах и уровнях оптимизации) сокращают код, выбрасывая циклы, до одной инструкции popcnt .
Является ли такой подход (как, впрочем, и любой другой) O(1) - это уже у вас надо спрашивать.
P.S. Я обычно не мелочусь и сразу забабахиваю таблицу для 32-битных слов. Солидная таблица для солидных господ.
67.4k 3 3 золотых знака 56 56 серебряных знаков 132 132 бронзовых знака А вы уверены, что несколько гигабайт оперативной памяти нормально под такую таблицу? @pavel: Если эффективность этой операции — единственное требование к коду, то почему бы и нет? Хотя да, кэш процессора и фсё такоэ, имеет смысл попрофилировать.Ну, я, как обычно, не могу без экспериментов :) Итак, варианты -
Далее набиваю вектор из 100000000 значений:
Ну, а все тесты имеют один вид:
Для кэширования один проход делаю без засекания времени.
Вот как выглядят результаты на моей машине:
Понятно, что от раза к разу пляшет, но несильно - для того и показываю два результата.
Выводы делайте сами :) Чистое суммирование
дает примерно 25-27 ms.
Update
Посмотрел ассемблер. popHD сразу по 4 числа работает, с xmm регистрами, так что не знаю даже, радоваться или огорчаться :) Для отдельного значения __popcnt , понятно, быстрее.
Формулировка. Дано натуральное число меньше 16. Посчитать количество его единичных битов. Например, если дано число 9, запись которого в двоичной системе счисления равна 10012 (подстрочная цифра 2 справа от числа означает, что оно записано в двоичной системе счисления), то количество его единичных битов равно 2.
Решение. Нам необходима переменная для ввода с клавиатуры. Обозначим ее как n. Так как мы должны накапливать количество найденных битов, то возникает потребность в еще одной переменной. Обозначим ее как count («count» в переводе с англ. означает «считать», «подсчет» и т. д.). Переменные возьмем типа byte (они могут принимать значения от 0 до 255), и пусть в данном случае такой объем избыточен, но это не принципиально важно.
Как же сосчитать количество битов во введенном числе? Ведь число же вводится в десятичной системе счисления, и его нужно переводить в двоичную?
На самом деле все гораздо проще. Здесь нам поможет одно интересное правило:
Остаток от деления любого числа x в системе счисления с основанием p на само число p дает нам разряд единиц числа x (его крайний разряд справа).
То есть, в десятичной системе счисления мы получаем разряд единиц некоторого числа, взяв остаток от деления этого числа на 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 это будет выглядеть так:
4) Теперь нам нужно еще два раза повторить п. 3 , после чего останется единственный двоичный разряд числа n, который можно просто прибавить к счетчику без каких-либо дополнений:
count := count + n;
5) В результате в переменной count будет храниться количество единичных разрядов в двоичной записи исходного числа. Осталось лишь вывести ее на экран.
Код:
- program BinaryUnits;
- var
- n, count: byte;
- begin
- readln(n);
- count := 0;
- count := count + n mod 2;
- n := n div 2;
- count := count + n mod 2;
- n := n div 2;
- count := count + n mod 2;
- n := n div 2;
- count := count + n;
- writeln(count)
- end.
Программа работает правильно на всех вариантах правильных исходных данных, в чем несложно убедиться с помощью простой проверки.
Данный урок курса можно считать факультативным, т. е. необязательным. Для освоения темы этого урока вам потребуется знание о двоичной системе счисления, навыки перевода чисел из одной системы счисления в другую, а также вы должны иметь представление о том, что такое битовые (они же поразрядные) операции. С последним можно познакомиться по вот этой лекции.
В языке программирования C существуют следующие поразрядные операции: & (И), | (ИЛИ), ^ (исключающее ИЛИ), << (сдвиг влево), >> (сдвиг вправо),
(поразрядное дополнение до единицы). Рассмотрим на примерах, как они работают, но перед этим уделим внимание выводу в языке C чисел в отличных от десятичной системах счисления.
В С можно присваивать целочисленные значения в десятичной, восьмеричной и шестнадцатеричной системах счисления. Для того, чтобы присвоить переменной число в восьмеричной системе счисления, перед ним надо написать 0 (ноль), в шестнадцатеричной — 0x (ноль и икс), например:
Любые целые числа можно выводить на экран в десятичном, восьмеричном и шестнадцатеричном представлении. Пример кода для вывода определенных ранее двух переменных в различных системаъ счисления:
В результате на экране вы увидите:
Восьмеричные и шестнадцатеричные числа используются из-за удобства при работе с двоичной системой счисления. Каждая цифра восьмеричного числа может быть заменена тремя цифрами двоичного. И каждая цифра шестнадцатеричного числа легко заменяет четыре разряда двоичного числа. Вот таблица соответствия цифр восьмеричной системы счисления числам двоичной системы:
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
Теперь допустим, что у нас есть восьмеричное число 037. По таблице легко понять, что в двоичном выражении оно будет выглядеть как 011 111.
- Как будут выглядеть восьмеричные числа 04271 и 03566 в двоичном представлении.
- Составьте на бумаге таблицу соответствия шестнадцатеричный цифр двоичным числам. Переведите числа 7D, FFFF, 2C9 в двоичную систему счисления.
Итак, если бы мы при работе с поразрядными операциями использовали десятичные числа, то чтобы оценить результат нам бы каждый раз приходилось переводить десятичное число в двоичную систему счисления, что относительно трудоемко. Если же человек видит, например, восьмеричное число, то он может представить как оно выглядит в двоичном представлении, помня или держа перед глазами таблицу соответствия чисел. Например, как только мы видим 017, то можем представить в уме, как последние четыре бита ячейки памяти забиты единицами.
Теперь вернемся к поразрядным операциям и протестируем каждую из них. Для этого напишем небольшую программу:
Результат ее работы будет выглядеть так:
Этот результат будет проще понять с помощью рисунка:
В последнем случае получилось такое большое число потому, что под форматы вывода целых чисел ( %d, %o, %X ) выделяется по 4 байта.
- Используя шестнадцатеричные числа, напишите аналогичную приведенной выше программу. Объясните результат.
- Попробуйте составлять сложные битовые операции (в несколько действий) и оценивать их результат.
Теперь рассмотрим пример использования битовых операций. Допустим, у нас есть массив, требуется снять с него "маску", которая бы отражала, в какой позиции стоят отрицательные, а в какой положительные элементы. Пусть единица в бите обозначает соответствующий ей положительный элемент массива, а ноль — отрицательный. Другими словами, если у нас есть массив , то его "битовая маска" будет выглядеть как 101110, или в восьмеричном представлении как 056. Составим алгоритм решения этой задачи:
- Будем считать, что массив состоит не более чем из 32 элементов. Поэтому для хранения его "маски" достаточно переменной типа int . Назовем ее mask и присвоим значение 0.
- Перебрать элементы массива в цикле for . Если встречается положительный элемент, то установить соответствующий ему бит значения mask в 1.
- Вывести значение переменной mask на экран в виде восьмеричного числа.
Вроде бы все просто, но как установить в единицу определенный бит числа? Существует закономерность соответствия степеней двойки и двоичного представления числа:
2 0 = 0000 0001
2 1 = 0000 0010
2 2 = 0000 0100
2 3 = 0000 1000
2 4 = 0001 0000
и т.д. Теперь если применить к mask побитовую операцию | (ИЛИ), а в качестве второго операнда использовать определенную степень двойки, то один бит будет установлен в 1. Например:
(0) 0000 0000 | (2 5 ) 0010 0000 = 0010 0000
(32) 0010 0000 | (2 7 ) 1000 0000 = 1010 0000
При переборе первый элемент массива имеет индекс 0, но соответствующий ему бит в maskдолжен стоять впереди остальных. Если известно общее количество элементов массива (N), то можно определить степень двойки по формуле N - i - 1 . Действительно, имея третий положительный элемент массива из 10 элементов, следует установить в единицу восьмой с конца бит, а это значит надо использовать вторым операндом битового ИЛИ 27, а 7 как раз будет 10(N) - 2(i) - 1.
Другая проблема — как в языке C возвести число в степень. Понятно, что можно написать свой код, но скорее всего в стандартной библиотеке уже есть подобная функция. С помощью заголовочного файла math.h можно подключить библиотеку с математическими функциями. Среди них есть функция pow() , которая принимает два числа и возвращает результат возведения первого числа в степень, выраженную вторым числом. Однако результат возвращается в виде вещественного числа, а нам требуется целое. Как быть? В языке программирования С есть операции приведения типов, которые меняют тип значения с одного на другой. Например, чтобы преобразовать значение вещественной переменной a в целое, следует написать (int) a .
Вот как может выглядеть вышеописанная программа:
Напишите предыдущую программу. Оцените как она работает 1 . Подумайте над тем, как вывести на экран двоичное представление восьмеричного числа. Попробуйте реализовать это.
1 Если у вас не получается скомпилировать программу, добавьте в конце вызова gcc опцию -lm (например, gcc -o bits bits.c -lm ).
1 Потоковый ввод/вывод
Эти объекты называются потоками ввода/вывода. В дальнейших уроках мы узнаем и о других разновидностях таких потоков. Потоковый ввод/вывод осуществляется операциями >> и << соответственно. Использовать их можно следующим образом:
В этой программе создается 3 переменных целого типа данных ( int ), в конце урока приведена более подробная информация об этом и других стандартных типах. Тут, как и в hello world использолся вызов функции std::cin.get() для задержки закрытия окна. На самом деле эта функция ( get ) ожидает ввода символа пользователем.
Объект std::cin является потоком ввода, к нему можно применять оператор >> для получения значений переменных с клавиатуры:
Теперь значения переменных задаются не программистом, а пользователем (в процессе использования программы).
С помощью объекта cin и операции >> можно присвоить значение любой переменной. Например, если переменная x описана как целочисленная, то команда cin>>x; означает, что в переменную x будет записано некое целое число, введенное с клавиатуры. Если необходимо ввести несколько переменных, то можно написать:
cin >> x >> y >> z; .
2 Основные операции над числами
Директива using namespace std; сообщает компилятору, что в этом месте вы используете имена из пространства имен std , за счет нее вы, в частности, можете писать cout или cin вместо std::cout и std::cin . Тему пространств имен мы подробно изучим в следующих уроках.
Теперь рассмотрим изученное на примере более сложной задачи (наконец, заставим наш компьютер посчитать что-нибудь полезное):
Известны плотность p , высота h и радиус основания R цилиндрического слитка.
Найти объем V , массу m и площадь S основания слитка.
Составим текст программы, учитывая что:
$$S = \pi \cdot R \cdot R, \\
V = S \cdot h,\\
m = p \cdot V.$$
Результаты работы программы:
Исследуя эту программу, обратите внимание на:
3 Справочный материал
3.1 Переменные и типы данных
Переменная это область памяти заполненная данными, которые называются значением переменной. У каждой переменной должно быть своё уникальное имя на латинице с учетом регистра. Переменные делятся на целочисленные, дробные, символьные, логические (т.е «да» или «нет»).
Для решения задачи в любой программе выполняется обработка каких-либо данных. К основным типам данных языка C++ относят:
Для формирования других типов данных используют основные и так называемые спецификаторы:
- short — короткий;
- long — длинный;
- signed — знаковый;
- unsigned — беззнаковый.
- const — константа.
В таблице приведена справочная информация о различных комбинациях типов данных с учетом спецификаторов для операционной системы Windows:
| Имя типа | Размер (в байтах) | Диапазон значений |
|---|---|---|
| int (signed int) | 4 | От -2 147 483 648 до 2 147 483 647 |
| unsigned int | 4 | От 0 до 4 294 967 295 |
| bool | 1 | false или true |
| char (unsigned char) | 1 | -128 до 127 знаков по умолчанию |
| signed char | 1 | От -128 до 127 |
| unsigned char | 1 | От 0 до 255 |
| short (signed short) | 2 | От -32 768 до 32 767 |
| unsigned short | 2 | От 0 до 65 535 |
| long (signed long) | 4 | От -2 147 483 648 до 2 147 483 647 |
| unsigned long | 4 | От 0 до 4 294 967 295 |
| long long (signed long long) | 8 | От -9 223 372 036 854 775 808 до 9 223 372 036 854 775 807 |
| unsigned long long | 8 | От 0 до 18 446 744 073 709 551 615 |
| float | 4 | 3,4E +/- 38 (7 знаков) |
| double (long double) | 8 | 1,7E +/- 308 (15 знаков) |
| wchar_t | 2 | От 0 до 65 535 |
Переменная типа bool может принимать только два значения true (истина) или fasle (ложь), тем не менее, в памяти занимает не 1 бит, а 1 байт. Любое значение, не равное нулю, интерпретируется как true .
3.2 Битовые операции
Битовые операции применяются к числам в двоичном коде. При необходимости вы можете узнать больше о двоичном коде и правилах перевода чисел из одной системы счисления в другую из статей:
Ниже показано как выполняется операция логического ИЛИ для такого фрагмента кода:
3.3 Приведение типов
В C++ различают два вида преобразования типов данных: явное и неявное.
Неявное преобразование происходит автоматически. Это выполняется во время сравнения, присваивания или вычисления выражения различных типов. Например, следующая программа выведет на консоль значение типа float .
Наивысший приоритет получает тот тип, при котором произойдет минимальная потеря информации (в результате округления). Не стоит злоупотреблять неявным преобразованием типов, так как могут возникнуть разного рода непредвиденные ситуации.
В этом примере при присваивании выполнится неявное приведение переменной типа float к типу int . В результате работы программы на экран будет выведено число 123 .
Явное преобразование в отличие от неявного осуществляется программистом. Записать это можно следующим образом:
b = (int) a;
или
b = int(a);
Тут мы явно указываем, что переменной b нужно присвоить значение a, приведенное к типу int .
В С++ определены следующие операторы:
-
static_cast<> () — осуществляет преобразование связанных типов данных. Этот оператор приводит типы по обычным правилам, что может потребоваться в случае, когда компилятор не выполняет автоматическое преобразование. Синтаксис будет выглядеть так:
Тип static_cast <Тип> (объект);
С помощью static_cast нельзя убрать константность у переменной, но это по силам следующему оператору.
3.4 Составное присваивание, инкремент/декремент
В ваших программах часто нужно выполнить что-то типа
a = a+b;
вместо такой конструкции можно использовать специальный вид оператора:
a += b;
Еще чаще в программах нужно увеличивать или уменьшать значение переменной ровно на единицу:
Аналогично работает постфиксный и префиксный декремент (оператор -- ).
Здравствуйте!
Интересно, когда нужно использовать целую переменную, часто ли пишут что-то кроме int? Когда на практике это бывает нужно?
В каком-нибудь небольшом цикле, к примеру, от 0 до 9, в учебниках обычно используют тип int.
Хотя, опять же, заморачиваться с этим на ранних этапах разработки не стоит. Лучше пораньше выпустить программу, а потом уже заниматься ее профилированием.
Читайте также: