Подсчёт количества едениц в строке
Сколько единиц содержится в двоичной записи значения выражения: 4^255 + 2^255 − 255?
Что не так? И пожалуйста объясните.
Способ 1.
Приводим к строке, вызываем строковый метод подсчета символа.
Способ 2.
Считаем количество единиц, так как функция bin переводит к строковому типу вида ‘0bxxx’, где xxx — цифры числа в двоичном представлении.
Способ 3.
Также существует несложный алгоритм.
4^255 = 2^(255 * 2) степень двойки, будет обозначать единица в двоичном представлении данной суммы.
С вычитанием интереснее, можно проследить следующую закономерность:
2^n — 2^m — будет содержать n — m единиц (проверьте это и докажите самостоятельно).
Отсюда сделаем следующий финт: -255 = -256 + 1 = -2^8 + 2^0
В итоге наше выражение: 2^(255 * 2) + 2^255 — 2^8 + 1 будет иметь 1 + (255 — 8) + 1 единицу, так как 2^255 — 2^8 четное число и значит нулевой бит у него будет нулевой и прибавление единицы добавит только единицу.
Есть ли в python встроенная функция для подсчета количества единиц в числе? [закрыто]
Предложите эффективный алгоритм, если такой библиотечной функции не существует.
задан 24 сен ’12, 11:09
Математически в любом «числе» есть «число» единиц. — Preet Sangha
Я предполагаю, что вы говорите о количестве единиц в представлении числа в определенной системе счисления. Десятичный наверное? Или бинарный? Оба являются общими, и другие возможны. — user395760
Правильным термином будет «цифры». «Считай 1 цифры в числе» будет более четким способом выразить ваш вопрос. — Martijn Pieters
Если вы имеете в виду подсчет единиц в двоичном представлении числа, взгляните на это вопрос. — Lauritz V. Thaulow
3 ответы
что-то вроде str(number).count(«1») ?
Конечно, это при условии, что OP говорит о десятичной системе (вес Хэмминга, относящийся к двоичной системе, довольно распространен). — пользователь395760
Действительно, но я предполагаю, что это то, чего хочет ОП, поскольку нет информации, чтобы утверждать это — это может быть неправильно, если ОП когда-либо прояснит вопрос. — джсбуэно
Или мы могли бы просто отказаться отвечать на плохие вопросы вместо того, чтобы гадать. — Вубл
Получите количество нулей и единиц двоичного числа в Python
Я пытаюсь решить двоичную головоломку, моя стратегия — преобразовать сетку в нули и единицы, и я хочу убедиться, что каждая строка имеет такое же количество 0 и 1.
Есть ли какой-либо способ подсчета количества 1 и 0 числа, не прошедшего через номер?
То, что я сейчас делаю, это:
Есть ли более эффективный вычислительный (или математический способ) этого?
Если length умеренная (например, менее 20), вы можете использовать список в качестве справочной таблицы.
Стоит только генерировать список, если вы делаете много поисков, но, похоже, вы можете в этом случае.
например. Для 16-разрядной таблицы из 0 используйте этот
20 бит по-прежнему занимает менее секунды, чтобы сгенерировать на этом компьютере
Подсчитайте количество единиц в двоичном представлении
эффективный способ подсчета числа 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