Отличный способ перевернуть (двоичные) цифры числа в Python?
Я ищу функцию slick, которая меняет цифры двоичного представления числа. Если бы f была такой функцией, я бы имел int(reversed(s),2) == f(int(s,2)) всякий раз, когда s — строка нулей и единиц, начинающихся с 1. Сейчас я использую lambda x: int(».join(reversed(bin(x)[2:])),2) что касается лаконичности, но это похоже на довольно крутой способ сделать это. Мне было интересно, был ли более приятный (возможно, более быстрый) способ с побитовыми операторами, а что нет.
Почему у вас есть вызов list() там? str.join() займет любую итерацию. Я также не считаю это окольным путем — оно написано почти так, как вы его объясняете.
@Lattyware Lattyware Правильно, это не было нужно. Я просто чувствовал, что это было окольным в том смысле, что я манипулирую строками, когда это действительно похоже на числовую проблему. Хотя, предложения о том, как улучшить метод строки, тоже круто.
@math4tots: math4tots: маловероятно, что какой-либо метод, включающий манипулирование битами, будет быстрее, поскольку он неизбежно будет включать интерпретируемые циклы. Это, конечно, резко контрастирует с такими языками, как C, где естественным путем было бы немного пошатываться.
Есть ли способ сделать это, используя математические операции, которые используют преимущество представления числа в виде дополнения до двух, не обращаясь вообще?
Ну, может быть что-то математически эквивалентно обращению цифр в двоичном формате — но мне ничего не приходит в голову. Насколько я понимаю, это вовсе не численная проблема, вы хотите манипулировать последовательностью элементов — это именно то, что вы делаете.
В большинстве или во всех решениях с битовой перестановкой, которые вы можете найти, предполагается использование целых чисел фиксированной ширины. Например, если вы инвертируете биты целого числа 1 вы хотите получить 1 в качестве результата, но программисты на Си обычно хотят либо 2 ^ 15, либо 2 ^ 31 в зависимости от того, сколько битов есть в unsigned int .
6 ответов
Второй способ кажется более быстрым из двух, однако оба метода намного быстрее, чем ваш текущий метод:
import timeit print timeit.timeit("int(''.format(n)[::-1], 2)", 'n = 123456') print timeit.timeit("int(bin(n)[:1:-1], 2)", 'n = 123456') print timeit.timeit("int(''.join(reversed(bin(n)[2:])),2)", 'n = 123456') 1.13251614571 0.710681915283 2.23476600647
Не работает для отрицательных чисел . >>> int(bin(-128)[:1:-1], 2) ValueError: invalid literal for int() with base 2: ‘00000001b’
Также очень странно, что каждая степень 2 имеет одинаковое обратное значение 1 . >>> int(bin(4)[:1:-1], 2) = 1 , >>> int(bin(8)[:1:-1], 2) = 1 , >>> int(bin(16)[:1:-1], 2) = 1 и т. Д. Это обратное действие определенно не транзитивно в Python.
@AndrewMao Да, поскольку степень два имеет двоичное представление в форме 10000. 00 , поэтому обратное значение всегда равно 1 .
Вы можете сделать это с помощью операторов сдвига, например:
def revbits(x): rev = 0 while x: rev >= 1 return rev Это, кажется, не быстрее, чем ваш метод, хотя (на самом деле, немного медленнее для меня).
In [83]: int(''.join(bin(x)[:1:-1]), 2) Out[83]: 9987 Тот же метод, слегка упрощенный.
Я не вижу, что это лучше. Он просто использует более неясный метод его изменения. Лично я бы предпочел увидеть чуть более многословную, но в значительной степени более читаемую версию.
Я бы сказал, что ваш текущий метод отлично работает, но вы можете потерять вызов list() , поскольку str.join() будет принимать любые итерации:
def binary_reverse(num): return int(''.join(reversed(bin(num)[2:])), 2) Также не рекомендуется использовать lambda для чего угодно, кроме простейшей из функций, где он будет использоваться только один раз и сделает окружающий код более четким, будучи встроенным.
Причина, по которой я чувствую, что это нормально, поскольку она описывает то, что вы хотите сделать, — возьмите двоичное представление числа, отмените его, а затем снова получите число. Это делает этот код очень читаемым, и это должно быть приоритетом.
>>> def bit_rev(n): . return int(bin(n)[:1:-1], 2) . >>> bit_rev(2) 1 >>>bit_rev(10) 5 Существует целая половина главы Hacker Delight, посвященная этой проблеме (раздел 7-1: «Реверсивные биты и байты» ) с использованием двоичных операций, бит сдвигов и других положительных героев. Похоже, все это возможно в Python, и это должно быть намного быстрее, чем методы с двоичным-строковым и обратным.
Книга недоступна публично, но я нашел это сообщение в блоге, которое обсуждает некоторые из них. Метод, показанный в сообщении в блоге, следует следующей цитате из книги:
Реверсирование бит может быть выполнено достаточно эффективно, заменяя смежные одиночные биты, затем заменяя смежные 2-битные поля и т.д., как показано ниже. Эти пять операторов присваивания могут быть выполнены в любом порядок.
Ну, если у вас есть 32-разрядные целые числа, вы делаете 5 операций, а если у вас есть 64-разрядные целые числа, вы делаете 6. Не слишком сложно .
За исключением того, что Python автоматически переводит числа в бесконечно большие представления — в документе указано «Целые числа имеют неограниченную точность». , Вам потребуются бесконечные операции.
Это глупо. Как сделать арифметику с двумя дополнениями, если у вас нет фиксированного числа битов? Не существует единственного обратного числа отрицательного числа дополнения до двух, если количество битов не определено.
Эта ссылка также гласит: «Отрицательные числа рассматриваются как значение дополнения их 2» . Так что же происходит, когда вы меняете отрицательное число?
Естественное расширение арифметики дополнения 2 для целых чисел произвольного размера приводит к 2-адическим целым числам: jonisalonen.com/2013/infinite-integers ( хотя я не знаю, использует ли Python 2-адическое представление или другое).
Ещё вопросы
- 0 проблемы с извлечением простых данных JSON через getJSON
- 0 Я не могу отобразить свой угловой код на моей странице HTML
- 1 Python 3 добавляет элементы в список независимо от ключа, используемого в dict
- 1 Как поставить приложение в фоновом режиме?
- 1 Gradle, как заменить устаревший ‘variableOutput.getPackageLibrary ()’ на ‘variable.getPackageLibraryProvider ()’?
- 0 jQuery не работает в .load ()
- 0 координаты XYZ из reprojectImageTo3D opencv
- 1 Идентификация таблицы в HTML
- 0 mysqldump иногда возвращает пустой файл
- 1 Почему эмулятор не получает FCM Push
- 1 Получить текст XML-узла с заданным текстом соседнего узла с помощью xpath
- 1 Массивы кортежей
- 1 Не удалось выполнить NativeScript для задачи: ошибка при объединении архивов dex
- 0 Вложенное дочернее состояние с помощью ui-router
- 1 Java Rect.intersects () иногда не работает
- 0 c ++: создание вектора из связанных списков
- 1 Разбор XML-файла в Java с использованием DOM
- 1 StreamInsight: CleanseInput отбрасывает события
- 0 читать файл изображения в сервлете из углового JS [дубликата]
- 0 Как найти ближайшие значения как нижних, так и верхних в массиве объектов в PHP?
- 0 используя дублированные переменные JavaScript
- 0 обменивать переменные между страницей виртуальной клавиатуры на другую открытую страницу только в javascript (НЕ Jquery)?
- 1 Привязка Vue переопределяет атрибут элемента
- 0 Angular 1.x, ES5 / ES6 и тестирование с Karma
- 1 заставить браузер перезагрузить страницу (игнорировать кеш)
- 1 Перевод с использованием Google Translate API
- 1 Переменная JavaScript не меняется внутри функции setInterval ()?
- 1 WebView не работает с net :: ERR_CACHE_READ_FAILURE
- 0 Symfony 2.5.6 — исключение UnexpectedTypeException в пользовательском типе формы
- 0 Функции Javascript не загружают данные при загрузке
- 0 Обновление инвентаря Square-Connect cURL Call
- 1 Является ли откладывание проблем безопасности до конца цикла разработки приложений хорошим подходом?
- 0 получить идентификатор из ng-repeat
- 0 как скрыть элемент сообщения при загрузке / добавлении нового сообщения в список каналов?
- 1 C # — Backgroundworker и REST сервис
- 0 Для цикла условие является переменной без сравнения
- 0 Ошибка загрузки JS с использованием Backbone с помощью requireJS
- 1 Выбор имен файлов, начинающихся с «NVH», а не «NVHE» в C #
- 1 AmbiguousMatchException при работе с элементом управления select2 в JavaScript
- 0 Переключить расширяемый фон при нажатии
- 0 Переключение языков не работает
- 1 Как исправить таймер при прокрутке на RecyclerView на Android?
- 0 о removeClass из родительского элемента
- 1 Как отключить макет обновления смахивания, когда RecyclerView не на первом элементе?
- 1 Размещение горизонтального рециркулятора в определенной позиции с помощью ConstraintLayout
- 0 Центрирование растрового текста в прямоугольнике с помощью OpenGL
- 0 Веб-сокет с AngularJS / Asp.net
- 0 Удаление объекта в AngularJS
- 1 Как вытащить данные с сервера sas в hdfs, используя Java?
- 0 Методы событий плагина в Virtuemart для статуса заказа
Перевернуть число
Вводится целое число. Вывести число, обратное введенному по порядку составляющих его цифр. Например, введено 3425, надо вывести 5243.
Решение задачи на языке программирования Python
- Найдем остаток от деления на 10 исходного (первого) числа. Тем самым получим последнюю его цифру. Запомним ее.
- Присвоим эту цифру новому (второму) числу-«перевертышу».
- Разделим нацело на 10 первое число. Тем самым избавимся от последней цифры в нем.
- Снова найдем остаток от деления на 10 того, что осталось от первого числа. Запомним цифру-остаток.
- Разделим нацело на 10 первое число. Избавимся от текущей последней цифры в нем.
- Умножим на 10 второе число. Тем самым увеличим его разрядность до двух и сдвинем первую цифру в более старший разряд.
- Добавим к полученному второму числу запомненную ранее цифру из первого числа.
- Будем повторять действия п. 4-7 пока первое число не уменьшится до нуля, т. е. пока не избавимся от всех его разрядов.
n1 = int(input("Введите целое число: ")) # Последнюю цифру первого числа переносим во второе digit = n1 % 10 n2 = digit # Избавляемся от последней цифры первого числа n1 = n1 // 10 while n1 > 0: # находим остаток - последнюю цифру digit = n1 % 10 # делим нацело - удаляем последнюю цифру n1 = n1 // 10 # увеличиваем разрядность второго числа n2 = n2 * 10 # добавляем очередную цифру n2 = n2 + digit print('"Обратное" ему число:', n2)
Введите целое число: 32809 "Обратное" ему число: 90823
Введите целое число: 78290 "Обратное" ему число: 9287
На самом деле мы можем не добавлять последнюю цифру первого числа во второе до цикла. Если присвоить n2 ноль, то в цикле при выполнении выражения n2 = n2 * 10 не будет происходить сдвига разряда, так как при умножении на 0 получается 0. И первая цифра будет добавляться в разряд единиц.
n1 = int(input("Введите целое число: ")) n2 = 0 while n1 > 0: digit = n1 % 10 n1 = n1 // 10 n2 = n2 * 10 n2 = n2 + digit print('"Обратное" ему число:', n2)
Приведенный алгоритм решения математический и соответствует задаче, если условие, что надо обрабатывать именно число, является строгим.
Однако средства Python позволяют решить подобную задачу более практично. Так у списков есть метод reverse , позволяющий изменять порядок элементов на обратный. Мы можем получить из исходной строки список символов, выполнить его реверс, после чего с помощью строкового метода join опять собрать в единую строку.
n1 = input("Введите целое число: ") n_list = list(n1) n_list.reverse() n2 = "".join(n_list) print('"Обратное" ему число:', n2)
Также можно воспользоваться взятием среза из исходной строки с первого до последнего символа с обратным шагом:
n1 = input("Введите целое число: ") n2 = n1[::-1] print('"Обратное" ему число:', n2)
Два последних варианта решения задачи — это способы переворота строки, а не числа как такового. Если объект, который надо переверуть, изначально имеет числовой тип данных (например, генерируется функцией randint() ), то его придется преобразовывать в строковый тип данных с помощью функции str() . И если на выходе мы должны получить опять же число, то надо будет строку превращать обратно в число с помощью функции int() .
from random import randint print("Исходное число:", end=' ') n1 = randint(5000, 1000000) print(n1) n1 = str(n1) n2 = n1[::-1] n2 = int(n2) print('"Обратное" ему число:', n2)
Исходное число: 970334 "Обратное" ему число: 433079