Индекс возврата младшего значащего бита в Python

Ответ 1

Он доступен в gmpy оболочке для библиотеки многоточечных GNU. В моей системе это примерно в 4 раза быстрее, чем решение ctypes.

>>> import gmpy
>>> gmpy.scan1(136)
3
>>> bin(136)
'0b10001000'

Ответ 2

Только в Pythons 2.7 и 3.1 и выше:

def ffs(x):
    """Returns the index, counting from 0, of the
    least significant set bit in `x`.
    """
    return (x&-x).bit_length()-1

Пример:

>>> ffs(136)
3

Ответ 3

Можно загружать функции из разделяемых библиотек (DLL для пользователей Windows) с помощью модуля ctypes. Мне удалось загрузить функцию ffs() из стандартной библиотеки C, содержащуюся в libc.so.6 в Ubuntu 10.10:

>>> import ctypes
>>> libc = ctypes.cdll.LoadLibrary('libc.so.6')
>>> libc.ffs(136)
4

(Обратите внимание, что это использует индексирование на основе 1). Очевидно, что это не межплатформенная совместимость как есть; вам нужно будет изменить имя файла библиотеки для загрузки на основе той системы, в которой вы работаете (обнаружено с помощью sys.platform или аналогичного). Я даже не был бы на 100% уверен, что он будет одинаковым в разных дистрибутивах Linux.

Также было бы полезно сделать правильный бенчмаркинг, чтобы увидеть, действительно ли это стоит. Если его часто называют так часто, но если его использовать только время от времени, преимущество в производительности над реализацией Python, вероятно, будет незначительным по сравнению с обслуживанием, чтобы гарантировать, что он продолжает работать на разных платформах.

Альтернативой было бы написать собственную реализацию функции в C и создать оболочку Python. Затем вам придется скомпилировать его для каждой требуемой платформы, но вы потеряете сложность поиска правильного имени библиотеки, сохраняя при этом преимущества скорости.

Ответ 4

Чтобы выразить комментарий S.Lott, если установлен LSB, значение будет нечетным, и если оно будет ясным, значение будет четным. Следовательно, мы можем просто смещать значение прямо до тех пор, пока оно не станет нечетным, отслеживая, сколько сдвигов требуется для этого. Просто не забудьте проверить, что сначала установлен бит, иначе цикл станет бесконечным, когда ему будет задано значение 0...

>>> def ffs(num):
...     # Check there is at least one bit set.
...     if num == 0:
...         return None
...     # Right-shift until we have the first set bit in the LSB position.
...     i = 0
...     while (num % 2) == 0:
...         i += 1
...         num = num >> 1
...     return i
...
>>> num = 136
>>> bin(num)
'0b10001000'
>>> ffs(num)
3
>>> ffs(0) is None
True

Обратите внимание, что это относится к LSB как бит 0; просто инициализируйте i до 1, если вы предпочитаете индексирование на основе 1.

Ответ 5

Действительно все эти ответы с внешними модулями, определяющими функции и т.д. для... побитовой операции.

(1 + (x ^ (x-1))) >> 1

вернет наименьшую значительную мощность 2 в x.

Например, при x = 136 ответ будет 2 ^ 3 = 8.

Trick помнит, что x-1 имеет те же цифры, что и x, за исключением всех наименее значимых 1 и всех следующих нулей; затем выполнение побитового XOR bitwin X и X + 1 извлекает эти цифры.

Затем вы можете извлечь индекс с помощью метода bit_length().

Ответ 6

Вы можете реализовать любой из описанных здесь алгоритмов: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

Я не знаю какого-либо собственного метода для этого. (Вы также можете написать расширение для экспорта функции C на Python, но это, вероятно, не стоило бы проблем: -)

Ответ 7

Немного глупо пытаться и агрессивно оптимизировать код Python, поэтому простой цикл с счетчиком и сменой вправо должен быть прекрасным. Если вы захотите пойти быстрее (что будет иметь больше смысла в C, Java или Assembly), вы можете выполнить двоичный поиск наиболее подходящих 1-битных и даже использовать таблицы поиска, чтобы помочь вам.

Предположим, что x является 64-битным, и вы хотите использовать LSB. Смажьте нижние 32-бит. Предположим, что x отлична от нуля:

if x & 0xffffffff == 0:
  if x & 0xffff00000000 == 0:
    # the LSB is in the highest two bytes
  else:
    # the LSB is in the 5th or 6th byte
else:
  if x & 0xffff0000:
    # the LSB is in the 3rd or 4th byte
  else:
    # the LSB is in the 1st or 2nd byte

Как вы обрабатываете описанный выше раздел, зависит от того, насколько агрессивным вы хотите быть: вы можете выполнить дальнейший двоичный поиск, аналогичный тому, что у нас есть, или вы можете использовать таблицу поиска. Как бы то ни было, у нас есть 16-бит неопределенности, поэтому наша таблица будет 65 536 записей. Я действительно сделал таблицы, подобные этому, для чрезвычайно чувствительного к производительности кода, но это была программа на C, которая играла в Chess (в 64-битной строке было двоичное представление платы).

Ответ 8

Я знаю, что там уже выбран ответ, но у меня была проблема с проблемой, потому что я мог. Решение основано на идее, что если значение равно двум, вы можете взять лог-базу два, чтобы найти свою позицию. Остальная часть реализации вращается вокруг преобразования значения, так что мы можем просто взять журнал.

Я не тестировал его, но преобразование O (1), где n - количество бит (и этот взгляд несколько несправедливо игнорирует сложность, введенную log(), хотя, возможно, она вокруг O (log (n )) [1]?). Реализация проиллюстрирована на основе метода "уменьшения и сравнения" по методу "сила-два" из [2]:

import math

def ffs(value):
    """Find the first set bit in an integer, returning its index (from zero)"""
    if 0 > value:
        raise ValueError("No negative values!")
    if 0 == value:
        # No bits are set in value
        return None
    if (value & (value - 1)) != 0:
        # Multiple bits are set in value. Transform value such that only the
        # lowest bit remains set.
        value &= ~ (value - 1)
    # Only one bit is set in value, find its index from zero
    return int(math.log(value, 2))

[1] http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog

[2] http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/