Python - 从数字的位表示中去除尾随零的最快方法
Python - Fastest way to strip the trailing zeros from the bit representation of a number
这是 的 python 版本。
给定一个数字 num，从其二进制表示形式中去除尾随零的最快方法是什么？
例如，设num = 232。我们有 bin(num) 等于 0b11101000，我们想去除尾随零，这将产生 0b11101。这可以通过字符串操作来完成，但通过位操作可能会更快。到目前为止，我已经想到了使用 num & -num
假设 num != 0，num & -num 生成二进制 0b1<trailing zeros>。例如，
num 0b11101000
-num 0b00011000
& 0b1000
如果我们有一个 dict 以 2 的幂为键，以 2 的幂为值，我们可以使用它来知道向右移动多少位 num 以便仅剥离尾随零：
# 0b1 0b10 0b100 0b1000
POW2s = { 1: 0, 2: 1, 4: 2, 8: 3, ... }
def stripTrailingZeros(num):
pow2 = num & -num
pow_ = POW2s[pow2] # equivalent to math.log2(pow2), but hopefully faster
return num >> pow_
使用字典 POW2s 以 space 换取速度 - 替代方法是使用 math.log2(pow2).
有没有更快的方法？
也许另一个有用的花絮是 num ^ (num - 1)，它产生 0b1!<trailing zeros>，其中 !<trailing zeros> 表示取尾随零并将它们翻转为 1。例如，
num 0b11101000
num-1 0b11100111
^ 0b1111
另一种方法是使用 while 循环
def stripTrailingZeros_iterative(num):
while num & 0b1 == 0: # equivalent to `num % 2 == 0`
num >>= 1
return num
最终，我需要在一个大的数字列表上执行这个函数。一旦我这样做了，我就想要最大的。所以如果我有 [64, 38, 22, 20] 开始，我会在执行剥离后有 [1, 19, 11, 5]。然后我想要其中的最大值，即 19.
你说你“最终，[..] 在一个大的数字列表上执行这个函数以获得奇数并找到所述奇数的最大值。”
那么为什么不简单地：
from random import randint
numbers = [randint(0, 10000) for _ in range(5000)]
odd_numbers = [n for n in numbers if n & 1]
max_odd = max(odd_numbers)
print(max_odd)
要最终做到你说的你想做的，执行“右移直到结果为奇数”操作似乎没有什么意义？除非你想要对所有元素执行该操作的结果的最大值，这不是你所说的？
我同意@TimPeters 的回答，但是如果你把 Python 放在它的步调上并实际生成一些数据集并尝试提出的各种解决方案，它们在使用 Python ints，所以你最好的选择是对最多 32 位的数字进行整数除法，然后参见下表：
from pandas import DataFrame
from timeit import timeit
import math
from random import randint
def reduce0(ns):
return [n // (n & -n)
for n in ns]
def reduce1(ns, d):
return [n >> d[n & -n]
for n in ns]
def reduce2(ns):
return [n >> int(math.log2(n & -n))
for n in ns]
def reduce3(ns, t):
return [n >> t.index(n & -n)
for n in ns]
def reduce4(ns):
return [n if n & 1 else n >> ((n & -n).bit_length() - 1)
for n in ns]
def single5(n):
while (n & 0xffffffff) == 0:
n >>= 32
if (n & 0xffff) == 0:
n >>= 16
if (n & 0xff) == 0:
n >>= 8
if (n & 0xf) == 0:
n >>= 4
if (n & 0x3) == 0:
n >>= 2
if (n & 0x1) == 0:
n >>= 1
return n
def reduce5(ns):
return [single5(n)
for n in ns]
numbers = [randint(1, 2 ** 16 - 1) for _ in range(5000)]
d = {2 ** n: n for n in range(16)}
t = tuple(2 ** n for n in range(16))
assert(reduce0(numbers) == reduce1(numbers, d) == reduce2(numbers) == reduce3(numbers, t) == reduce4(numbers) == reduce5(numbers))
df = DataFrame([{}, {}, {}, {}, {}, {}])
for p in range(1, 16):
p = 2 ** p
numbers = [randint(1, 2 ** p - 1) for _ in range(4096)]
d = {2**n: n for n in range(p)}
t = tuple(2 ** n for n in range(p))
df[p] = [
timeit(lambda: reduce0(numbers), number=100),
timeit(lambda: reduce1(numbers, d), number=100),
timeit(lambda: reduce2(numbers), number=100),
timeit(lambda: reduce3(numbers, t), number=100),
timeit(lambda: reduce4(numbers), number=100),
timeit(lambda: reduce5(numbers), number=100)
]
print(f'Complete for {p} bit numbers.')
print(df)
df.to_csv('test_results.csv')
结果（在 Excel 中绘制时）：
注意之前的剧情是错的！虽然没有代码和数据。代码已更新为包含@MarkRansom 的解决方案，因为事实证明它是非常大的数字（超过 4k 位数字）的最佳解决方案。
while (num & 0xffffffff) == 0:
num >>= 32
if (num & 0xffff) == 0:
num >>= 16
if (num & 0xff) == 0:
num >>= 8
if (num & 0xf) == 0:
num >>= 4
if (num & 0x3) == 0:
num >>= 2
if (num & 0x1) == 0:
num >>= 1
这里的想法是执行尽可能少的班次。初始 while 循环处理超过 32 位长的数字，我认为这不太可能，但为了完整性必须提供它。之后每条语句移动一半的位数；如果你不能移动 16，那么你最多可以移动 15，即 (8+4+2+1)。这 5 个 if 语句涵盖了所有可能的情况。
在我的电脑上，简单的整数除法最快：
import timeit
timeit.timeit(setup='num=232', stmt='num // (num & -num)')
0.1088077999993402
timeit.timeit(setup='d = { 1: 0, 2 : 1, 4: 2, 8 : 3, 16 : 4, 32 : 5 }; num=232', stmt='num >> d[num & -num]')
0.13014470000052825
timeit.timeit(setup='import math; num=232', stmt='num >> int(math.log2(num & -num))')
0.2980690999993385
在没有指定输入的预期分布的情况下，这样的问题真的没有答案。例如，如果所有输入都在 range(256) 中，您无法将单个索引查找排除在 256 种可能情况的预计算列表中。
如果输入可以是两个字节，但您不想将 space 用于 2**16 个预计算结果，则很难击败（假设 that_table[i] 给出尾随的计数i 中的零）：
low = i & 0xff
result = that_table[low] if low else 8 + that_table[i >> 8]
以此类推
你不想靠log2()。其准确性完全取决于编译 CPython 的平台上的 C 库。
我实际使用的是，在 int 可以高达数亿位的上下文中：
assert d
if d & 1 == 0:
ntz = (d & -d).bit_length() - 1
d >>= ntz
A while 循环在这种情况下将是一场灾难，所花费的时间是偏移位数的二次方。在这种情况下，即使是一个不必要的移位也会是一笔巨大的开支，这就是为什么上面的代码首先检查是否至少有一位需要移位。但是，如果整数“小得多”，那么该检查的成本可能会超过它节省的成本。 “在没有指定输入的预期分布的情况下没有答案。”
这是
给定一个数字 num，从其二进制表示形式中去除尾随零的最快方法是什么？
例如，设num = 232。我们有 bin(num) 等于 0b11101000，我们想去除尾随零，这将产生 0b11101。这可以通过字符串操作来完成，但通过位操作可能会更快。到目前为止，我已经想到了使用 num & -num
假设 num != 0，num & -num 生成二进制 0b1<trailing zeros>。例如，
num 0b11101000
-num 0b00011000
& 0b1000
如果我们有一个 dict 以 2 的幂为键，以 2 的幂为值，我们可以使用它来知道向右移动多少位 num 以便仅剥离尾随零：
# 0b1 0b10 0b100 0b1000
POW2s = { 1: 0, 2: 1, 4: 2, 8: 3, ... }
def stripTrailingZeros(num):
pow2 = num & -num
pow_ = POW2s[pow2] # equivalent to math.log2(pow2), but hopefully faster
return num >> pow_
使用字典 POW2s 以 space 换取速度 - 替代方法是使用 math.log2(pow2).
有没有更快的方法？
也许另一个有用的花絮是 num ^ (num - 1)，它产生 0b1!<trailing zeros>，其中 !<trailing zeros> 表示取尾随零并将它们翻转为 1。例如，
num 0b11101000
num-1 0b11100111
^ 0b1111
另一种方法是使用 while 循环
def stripTrailingZeros_iterative(num):
while num & 0b1 == 0: # equivalent to `num % 2 == 0`
num >>= 1
return num
最终，我需要在一个大的数字列表上执行这个函数。一旦我这样做了，我就想要最大的。所以如果我有 [64, 38, 22, 20] 开始，我会在执行剥离后有 [1, 19, 11, 5]。然后我想要其中的最大值，即 19.
你说你“最终，[..] 在一个大的数字列表上执行这个函数以获得奇数并找到所述奇数的最大值。”
那么为什么不简单地：
from random import randint
numbers = [randint(0, 10000) for _ in range(5000)]
odd_numbers = [n for n in numbers if n & 1]
max_odd = max(odd_numbers)
print(max_odd)
要最终做到你说的你想做的，执行“右移直到结果为奇数”操作似乎没有什么意义？除非你想要对所有元素执行该操作的结果的最大值，这不是你所说的？
我同意@TimPeters 的回答，但是如果你把 Python 放在它的步调上并实际生成一些数据集并尝试提出的各种解决方案，它们在使用 Python ints，所以你最好的选择是对最多 32 位的数字进行整数除法，然后参见下表：
from pandas import DataFrame
from timeit import timeit
import math
from random import randint
def reduce0(ns):
return [n // (n & -n)
for n in ns]
def reduce1(ns, d):
return [n >> d[n & -n]
for n in ns]
def reduce2(ns):
return [n >> int(math.log2(n & -n))
for n in ns]
def reduce3(ns, t):
return [n >> t.index(n & -n)
for n in ns]
def reduce4(ns):
return [n if n & 1 else n >> ((n & -n).bit_length() - 1)
for n in ns]
def single5(n):
while (n & 0xffffffff) == 0:
n >>= 32
if (n & 0xffff) == 0:
n >>= 16
if (n & 0xff) == 0:
n >>= 8
if (n & 0xf) == 0:
n >>= 4
if (n & 0x3) == 0:
n >>= 2
if (n & 0x1) == 0:
n >>= 1
return n
def reduce5(ns):
return [single5(n)
for n in ns]
numbers = [randint(1, 2 ** 16 - 1) for _ in range(5000)]
d = {2 ** n: n for n in range(16)}
t = tuple(2 ** n for n in range(16))
assert(reduce0(numbers) == reduce1(numbers, d) == reduce2(numbers) == reduce3(numbers, t) == reduce4(numbers) == reduce5(numbers))
df = DataFrame([{}, {}, {}, {}, {}, {}])
for p in range(1, 16):
p = 2 ** p
numbers = [randint(1, 2 ** p - 1) for _ in range(4096)]
d = {2**n: n for n in range(p)}
t = tuple(2 ** n for n in range(p))
df[p] = [
timeit(lambda: reduce0(numbers), number=100),
timeit(lambda: reduce1(numbers, d), number=100),
timeit(lambda: reduce2(numbers), number=100),
timeit(lambda: reduce3(numbers, t), number=100),
timeit(lambda: reduce4(numbers), number=100),
timeit(lambda: reduce5(numbers), number=100)
]
print(f'Complete for {p} bit numbers.')
print(df)
df.to_csv('test_results.csv')
结果（在 Excel 中绘制时）：
注意之前的剧情是错的！虽然没有代码和数据。代码已更新为包含@MarkRansom 的解决方案，因为事实证明它是非常大的数字（超过 4k 位数字）的最佳解决方案。
while (num & 0xffffffff) == 0:
num >>= 32
if (num & 0xffff) == 0:
num >>= 16
if (num & 0xff) == 0:
num >>= 8
if (num & 0xf) == 0:
num >>= 4
if (num & 0x3) == 0:
num >>= 2
if (num & 0x1) == 0:
num >>= 1
这里的想法是执行尽可能少的班次。初始 while 循环处理超过 32 位长的数字，我认为这不太可能，但为了完整性必须提供它。之后每条语句移动一半的位数；如果你不能移动 16，那么你最多可以移动 15，即 (8+4+2+1)。这 5 个 if 语句涵盖了所有可能的情况。
在我的电脑上，简单的整数除法最快：
import timeit
timeit.timeit(setup='num=232', stmt='num // (num & -num)')
0.1088077999993402
timeit.timeit(setup='d = { 1: 0, 2 : 1, 4: 2, 8 : 3, 16 : 4, 32 : 5 }; num=232', stmt='num >> d[num & -num]')
0.13014470000052825
timeit.timeit(setup='import math; num=232', stmt='num >> int(math.log2(num & -num))')
0.2980690999993385
在没有指定输入的预期分布的情况下，这样的问题真的没有答案。例如，如果所有输入都在 range(256) 中，您无法将单个索引查找排除在 256 种可能情况的预计算列表中。
如果输入可以是两个字节，但您不想将 space 用于 2**16 个预计算结果，则很难击败（假设 that_table[i] 给出尾随的计数i 中的零）：
low = i & 0xff
result = that_table[low] if low else 8 + that_table[i >> 8]
以此类推
你不想靠log2()。其准确性完全取决于编译 CPython 的平台上的 C 库。
我实际使用的是，在 int 可以高达数亿位的上下文中：
assert d
if d & 1 == 0:
ntz = (d & -d).bit_length() - 1
d >>= ntz
A while 循环在这种情况下将是一场灾难，所花费的时间是偏移位数的二次方。在这种情况下，即使是一个不必要的移位也会是一笔巨大的开支，这就是为什么上面的代码首先检查是否至少有一位需要移位。但是，如果整数“小得多”，那么该检查的成本可能会超过它节省的成本。 “在没有指定输入的预期分布的情况下没有答案。”