Блог

Есть ли какой-нибудь быстрый способ получить количество завершающих нулей во встроенном целом числе Python3?

Например, если я хочу проверить, есть ли 4 завершающих нуля, я могу сделать следующее:

 >>> some_integer amp; 15
  

Или для 8 завершающих нулей:

 >>> some_integer amp; 255
  

Если результата нет 0 , в первых 4 или 8 битах есть единицы.

Есть ли способ, как выполнить эту операцию в общем виде? Моя цель — пропустить любое количество завершающих нулей с помощью >> оператора.

Вы могли бы использовать побитовую арифметику (для положительных и отрицательных значений, но исключая 0 , для которых поведение не определено, так как нет 1 для отслеживания):

 (x amp; -x).bit_length() - 1
  

или:

 (x ^ -x).bit_lenght() - 2
  

или, возможно, с более интересным 0 поведением (благодаря комментарию @TomKarzes):

 (x ^ (x - 1)).bit_length() - 1
  

Чтобы понять, как они работают, давайте рассмотрим это последнее выражение. Когда мы выполняем, x - 1 если x нечетно, переворачивается только этот бит, а затем, когда мы выполняем xor ^ , это единственный бит, который сохраняется после операции. Аналогично, когда x значение не нечетно, каждый завершающий ноль переключается на 1 , а отслеживаемый 1 переключается на 0 , все остальные биты остаются нетронутыми, и затем мы устанавливаем xor все биты до отслеживаемого 1 . Затем int.bit_length() подсчитывается, сколько значимых битов найдено, и -1 это просто постоянное смещение, которое нам нужно, чтобы получить «количество завершающих нулей».

Почему первые методы также работают, связано с представлением отрицательных чисел с двумя дополнениями. Точные детали оставлены в качестве упражнения для читателя.

Чтобы показать, что они работают:

 for i in range(-15, 16): 
     print(
         f'{i:5b}',
         f'{i ^ -i:3d}',
         f'{(i amp; -i).bit_length() - 1:2d}',
         f'{(i ^ -i).bit_length() - 2:2d}',
         f'{(i ^ (i - 1)).bit_length() - 1:2d}') 
  

 -1111  -2  0  0  0
-1110  -4  1  1  1
-1101  -2  0  0  0
-1100  -8  2  2  2
-1011  -2  0  0  0
-1010  -4  1  1  1
-1001  -2  0  0  0
-1000 -16  3  3  3
 -111  -2  0  0  0
 -110  -4  1  1  1
 -101  -2  0  0  0
 -100  -8  2  2  2
  -11  -2  0  0  0
  -10  -4  1  1  1
   -1  -2  0  0  0
    0   0 -1 -2  0
    1  -2  0  0  0
   10  -4  1  1  1
   11  -2  0  0  0
  100  -8  2  2  2
  101  -2  0  0  0
  110  -4  1  1  1
  111  -2  0  0  0
 1000 -16  3  3  3
 1001  -2  0  0  0
 1010  -4  1  1  1
 1011  -2  0  0  0
 1100  -8  2  2  2
 1101  -2  0  0  0
 1110  -4  1  1  1
 1111  -2  0  0  0
  

Обратите внимание на различное поведение двух выражений для 0 ввода.
В частности, (x ^ (x - 1)).bit_length() - 1 может привести к более простым выражениям, если вы хотите, чтобы 0 ввод производил 0 вывод.

С точки зрения скорости это должно быть намного быстрее, чем любое решение на основе цикла, и наравне с решениями на основе поиска (но без ограничения размера и без использования дополнительной памяти):

 def trail_zero_loop(x):
    if x != 0:
        k = -1
        r = 0
        while not r:
            # x, r = divmod(x, 2)  # ~15% slower
            r = x % 2
            x = x // 2
            k  = 1
        return k
    else:
        return -1
  

 def trail_zero_and(x):
    return (x amp; -x).bit_length() - 1
  

 def trail_zero_xor(x):
    if x != 0:
        # return (x ^ -x).bit_length() - 2  # ~1% slower
        return (x ^ (x - 1)).bit_length() - 1
    else:
        return -1
  

 _LOOKUP =[ 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 ]


def trail_zero_lookup(x):
    if x != 0:
        return _LOOKUP[(x amp; -x) % 37]
    else:
        return -1
  

 n = 2 ** 30
%timeit trail_zero_loop(n)
# 3.15 µs ± 25.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
%timeit trail_zero_and(n)
# 228 ns ± 9.87 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit trail_zero_xor(n)
# 253 ns ± 7.25 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit trail_zero_lookup(n)
# 294 ns ± 1.81 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
  

Возможная дополнительная операция сдвига битов занимает всего несколько наносекунд, поэтому здесь это не имеет значения.

 n = 12 # 0b1100
while n % 2 == 0:
    n //= 2
# out: 3 i.e. 0b11
  

Это делит число на два до неделимости и, таким образом, удаляет завершающие нули.

РЕДАКТИРОВАТЬ: понял, что приведенный выше код бесконечных циклов, если n==0 . Исправляемый:

 n = 12 # 0b1100
if n != 0:
    while n % 2 == 0: n //= 2
# out: 3 i.e. 0b11
  

РЕДАКТИРОВАТЬ: Опирался на предложения от @MisterMiyagi.

 n = 10 # 0b1010
if n != 0:
  while n % 2 == 0: n, r = divmod(n, 2)
# n = 5 i.e. 0b101
  

Для произвольных длинных чисел

 def remove_tailing_zeroes(n):
    return n >> get_number_of_trailing_zeroes(n)

def get_number_of_trailing_zeroes(n):
    c = 0
    while True:
        n, r = divmod(n, 2)
        if 0 != r:
            break
        c =1
    return c
  

Быстрое и эффективное решение без циклов для 32-разрядных чисел

 LOOKUP =[ 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 ]

def remove_tailing_zeroes(n):
    return n >> LOOKUP[(n amp; -n) % 37]

def get_number_of_trailing_zeroes(n):
    return LOOKUP[(n amp; -n) % 37]
  

Адаптация из Bit Twiddling Hacks Шона Эрона Андерсона

Вы можете сдвинуться вправо на это количество завершающих нулей и избавиться от них (обозначено через shifted = n >> r ).

Тест

 for n in range(1, 20):
    r = get_number_of_trailing_zeroes(n)
    shifted = n >> r
    print(f'n: {n} bin: {bin(n)} zeroes: {r} shifted: {bin(shifted)}')
    assert 0 == get_number_of_trailing_zeroes(shifted)
  

Вывод:

 n: 1 bin: 0b1 zeroes: 0 shifted: 0b1
n: 2 bin: 0b10 zeroes: 1 shifted: 0b1
n: 3 bin: 0b11 zeroes: 0 shifted: 0b11
n: 4 bin: 0b100 zeroes: 2 shifted: 0b1
n: 5 bin: 0b101 zeroes: 0 shifted: 0b101
n: 6 bin: 0b110 zeroes: 1 shifted: 0b11
n: 7 bin: 0b111 zeroes: 0 shifted: 0b111
n: 8 bin: 0b1000 zeroes: 3 shifted: 0b1
n: 9 bin: 0b1001 zeroes: 0 shifted: 0b1001
n: 10 bin: 0b1010 zeroes: 1 shifted: 0b101
n: 11 bin: 0b1011 zeroes: 0 shifted: 0b1011
n: 12 bin: 0b1100 zeroes: 2 shifted: 0b11
n: 13 bin: 0b1101 zeroes: 0 shifted: 0b1101
n: 14 bin: 0b1110 zeroes: 1 shifted: 0b111
n: 15 bin: 0b1111 zeroes: 0 shifted: 0b1111
n: 16 bin: 0b10000 zeroes: 4 shifted: 0b1
n: 17 bin: 0b10001 zeroes: 0 shifted: 0b10001
n: 18 bin: 0b10010 zeroes: 1 shifted: 0b1001
n: 19 bin: 0b10011 zeroes: 0 shifted: 0b10011