Сканирование бит вперед и назад в Numpy

Question

Мне нужно посчитать количество конечных и ведущих нулей в переменной ninty uint64, поэтому сейчас я делаю это так:

# n > 0
n = np.uint64(100)
s = np.binary_repr(n)
trail_zeros = len(s) - len(s.rstrip('0'))
lead_zeros = 64 - len(s)

Есть ли лучший способ сделать это, безиспользуя строки?Приоритет - скорость.Спасибо!

Answer 1

Для чисел в [0,2**63) мы можем использовать некоторые арифметические операции, чтобы получить начальные и конечные нули в их двоичных форматах и, следовательно, пропустить манипуляции со строками -

def get_leading_trailing_zeros(n):
    a = (2**np.arange(64) & n)
    lead_zeros = 64-a.argmax()-1
    if n==0:
        trail_zeros = 1
    else:
        trail_zeros = (a==0).argmin()
    return lead_zeros,trail_zeros

Answer 2

Я не уверен в скорости следующего кода.Но вы, безусловно, можете сделать это так, не используя строки.

n = np.uint64(100)
i=1
while((n>>np.uint64(i))%2==0):
    i+=1

trail_zeros=i

Вы сдвигаете значение n вправо, пока не получите нечетное число.Количество сделанных правых сдвигов равно trail_zeros.

Answer 3

lead_zeros = int(64-np.ceil(np.log2(n)))

Потому что len(s) равно ceil(log2(n)). Это чисто арифметическая операция, поэтому она может быть идеально векторизована с помощью numpy и намного быстрее, чем написание собственного цикла.

Performance