Ошибка сервера в приложении ‘/’.
Описание: На сервере возникла ошибка приложения. Текущая пользовательская настройка ошибок для этого приложения не позволяет удаленно просматривать сведения об ошибке данного приложения (из соображений безопасности). Однако, сведения можно просматривать в браузерах, запущенных на локальном сервере.
Сведения: Для разрешения просмотра сведений данного сообщения об ошибке на локальном сервере создайте тег <customErrors> в файле конфигурации "web.config", который находится в корневом каталоге текущего веб-приложения. В теге <customErrors> следует задать атрибут "mode" со значением "Off".
Примечания: Отображаемую в данный момент страницу ошибок можно заменить на пользовательскую страницу ошибок, изменив атрибут "defaultRedirect" тега конфигурации <customErrors> приложения таким образом, чтобы он содержал URL-адрес пользовательской страницы ошибок.
дано натуральное число.Определить количество единиц в записи данного числа в двоичной системе счисления
begin
Write(‘Введите натуральное число: ‘); Readln(n);
k := 0;
if n > 1 then
begin
repeat
if n mod 2 = 1 then k := k + 1;
n := n div 2
until n < 2
end;
Writeln(‘Количество единиц в двоичном представлении равно ‘, k + 1)
end.
Тестовое решение:
Введите натуральное число: 152
Количество единиц в двоичном представлении равно 3
Подсчитайте количество единиц в двоичном представлении
эффективный способ подсчета числа 1s в двоичном представлении числа в O (1), Если у вас достаточно памяти для игры. Это вопрос интервью, который я нашел на онлайн-форуме, но у него не было ответа. Может кто-нибудь предложить что-то, я не могу придумать способ сделать это в O(1) Время?
21 ответов:
Это вес Хэмминга проблема, ака подсчет населения. Ссылка упоминает эффективные реализации. Цитирование:
с неограниченной памятью мы могли бы просто создать большую таблицу поиска веса Хэмминга каждого 64-битного целого числа
у меня есть решение, которое подсчитывает биты в O(Number of 1’s) время:
в худшем случае (когда число 2^n — 1, Все 1 в двоичном формате) он будет проверять каждый бит.
изменить: Просто нашел очень хороший алгоритм постоянного времени, постоянной памяти для bitcount. Вот оно, написано на C:
вы можете найти доказательство своей правоты здесь.
обратите внимание на то, что: n&(n-1) всегда устраняет наименее значимый 1.
следовательно, мы можем написать код для вычисления количества 1 следующим образом:
сложность программы будет: число 1 в n (которое постоянно
Я видел следующее решение с другого сайта:
Это будет самый короткий ответ в мою жизнь так: таблица подстановки.
видимо, мне нужно немного объяснить:» если у вас достаточно памяти, чтобы играть » означает, что у нас есть вся необходимая память (неважно, техническая возможность). Теперь вам не нужно хранить таблицу поиска более одного или двух байтов. Хотя технически это будет Ω(log(n)), а не O(1), просто чтение числа, которое вам нужно, — это Ω(log (n)), поэтому, если это проблема, то ответ, невозможно — что еще короче.
какой из двух ответов они ожидают от вас на интервью, никто не знает.
есть еще один трюк: в то время как инженеры могут взять число и говорить о Ω(log(n)), где n-число, компьютерные ученые скажут, что на самом деле мы должны измерять время работы как функцию a длина ввода, поэтому то, что инженеры называют Ω(log(n)), на самом деле Ω(k), где k-количество байтов. Тем не менее, как я уже говорил, просто чтение числа-это Ω(k), поэтому мы не можем сделать лучше этого.
функция принимает 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). Это было бы вполне легко сделать эту основную идею более элегантной с некоторыми основными элементами схемы для получения выхода в любой форме, которую вы хотите (например, двоичный кодированный выход), но основная идея одна и та же, и электронная схема будет производить правильное состояние выхода в фиксированное время.
Я предполагаю, что есть также возможные возможности квантовых вычислений, но если нам позволят это сделать, я бы подумал, что простая электронная схема-это более простое решение.
Я на самом деле сделал это, используя немного ловкости рук: одной таблицы поиска с 16 записями будет достаточно, и все, что вам нужно сделать, это разбить двоичный rep на кусочки (4-битные кортежи). Сложность на самом деле O(1), и я написал шаблон C++, который был специализирован на размере целого числа, которое вы хотели (в # битах). делает его постоянным выражением вместо неопределенного.
fwiw вы можете использовать тот факт, что (i & — i) вернет вам LS один бит и просто цикл, зачистка выключайте lsbit каждый раз, пока целое число не станет нулем — но это старый трюк с четностью.
Я пришел сюда, имея большую веру, что я знаю красивое решение этой проблемы. Код в C:
но после того, как я провел небольшое исследование по этой теме (читайте другие ответы:)) я нашел 5 более эффективных алгоритмов. Люблю так!
есть даже инструкция CPU, разработанная специально для этой задачи: popcnt . (упоминается в ответ)
описание и бенчмаркинг многих алгоритмов вы можете найти здесь.
ниже метод может подсчитать количество 1s в отрицательных числах, а также.
однако число, подобное -1, представлено в двоичном виде как 1111111111111111111111111111111111 и поэтому потребует много сдвига. Если вы не хотите делать так много сдвигов для небольших отрицательных чисел, другой способ может быть следующим:
в python или любом другом преобразовании в строку bin затем разделите ее с помощью «0», чтобы избавиться от 0, затем объедините и получите длину.
С использованием строковых операций в JS можно сделать следующим образом:
или
Я должен был гольф это в Руби и в конечном итоге с
использование :
l[2**32-1] # returns 32
очевидно, не эффективно, но делает трюк 🙂
двумя способами:
где binaryValue-это двоичная строка, например: 1100
Посчитать количество единиц в числе
Вопрос предельно прост: надо посчитать количество единиц в двоичном представлении числа за О(1). Линии и логарифмы даже не предлагайте. Интересует только О(1).
Всего не более CHAR_BIT * sizeof(n) итераций, то есть, ограничено константой.
Вот ещё вам классический Кернигановский способ:
Ограничение сверху то же, но на практике работает быстрее, т. к. использует одну итерацию на единичный бит.
Подборка различных способов подсчёта битов есть тут.
Обратите внимание, что хитрые компиляторы знают Кернигановский метод, и (на некоторых платформах и уровнях оптимизации) сокращают код, выбрасывая циклы, до одной инструкции popcnt .
Создайте lookup-таблицу для 8-битных байтов (и/или 16-битных слов) и затем примените ее для подсчета битов в типе любого размера. Пока размер рассматриваемых типов константен, время подсчета тоже является константным.
Является ли такой подход (как, впрочем, и любой другой) O(1) — это уже у вас надо спрашивать.
P.S. Я обычно не мелочусь и сразу забабахиваю таблицу для 32-битных слов. Солидная таблица для солидных господ.
Ну, я, как обычно, не могу без экспериментов 🙂 Итак, варианты —
Если кому хочется посмотреть весь код — нет вопросов: http://vpaste.net/fD5DV
Далее набиваю вектор из 100000000 значений:
Ну, а все тесты имеют один вид:
Для кэширования один проход делаю без засекания времени.
Вот как выглядят результаты на моей машине:
Понятно, что от раза к разу пляшет, но несильно — для того и показываю два результата.
Выводы делайте сами 🙂 Чистое суммирование
дает примерно 25-27 ms.
Update
Посмотрел ассемблер. popHD сразу по 4 числа работает, с xmm регистрами, так что не знаю даже, радоваться или огорчаться 🙂 Для отдельного значения __popcnt , понятно, быстрее.