Lua：通过2的幂次分解一个数字

Question

这个问题与 Python - 如何将数字分解为 2 的幂次方？ 相似。实际上，这是相同的问题，但与使用 Python（或 Javascript、C++，因为它们也存在）不同，我想知道如何使用 Lua 完成此操作。我对 Python 有一些基本的了解，所以我首先尝试将上述网站中列出的代码翻译成 Lua，但没有成功。以下是原始代码和我的翻译：

Python

def myfunc(x):
    powers = []
    i = 1
    while i <= x:
        if i & x:
            powers.append(i)
        i <<= 1
    return powers

Lua

function powerfind(n)
  local powers = {}
  i = 1
  while i <= n do
    if bit.band(i, n) then -- bitwise and check
      table.insert(powers, i)
    end
    i = bit.shl(i, 1) -- bitwise shift to the left
  end
  return powers
end

很遗憾，我的版本锁定并且“内存耗尽”。这是在使用数字12作为测试之后发生的。很有可能是我对Python的基础知识不足，无法正确地将代码从Python翻译成Lua，因此希望有人能提供新的视角并帮助我修复它。

- Josh

---

这行代码bit.shl(n, 1)有两个问题。思考一下这行代码应该做什么，以及它实际上做了什么。 - user2357112

此外，Python 和 Lua 在它们认为什么是真或假方面有所不同。如果你更熟悉 Lua，那么你应该会对 if bit.band(i, n) 看到一些有趣的东西。请注意，Python 认为 0 是假的。 - user2357112

啊，现在把 bit.shl(n,1) 改成了 i = bit.shl(i, 1) ... 但是不确定该怎么处理 if bit.band(i, n) 部分。 - Josh

就这样，我想我通过将它更改为 if bit.band(i, n) ~= 0 找到了答案... 目前看起来是有效的。谢谢！ - Josh

bit不是标准的Lua库。也许你想要使用的是bit32，这种情况下使用lshift代替shl。此外，在Lua 5.3中，您可以使用普通的位运算符＆和<<。 - lhf

对于我正在使用的程序（MUSHclient），它已经将bit32缩短为bit。我不认为它已经整合了5.3，但我会查一下。谢谢！ - Josh

Answer 1

感谢用户user2357112的评论，我已经修复了这个问题，并发布了答案，以便其他遇到此问题的人参考：

function powerfind(n)
  local powers = {}
  i = 1
  while i <= n do
    if bit.band(i, n) ~= 0 then -- bitwise and check
      table.insert(powers, i)
    end
    i = bit.shl(i, 1) -- bitwise shift to the left
  end
  return powers
end

- Josh

Answer 2

我看到在另一个版本中，它变成了一种速度比赛。这个版本应该也很容易理解。

i is the current power. It isn't used for calculations.
n is the current place in the array.
r is the remainder after a division of x by two.

如果余数为1，则可以确定i是2的幂，这个幂在x的二进制表示中被使用。

local function powerfind(x)
    local powers={
        nil,nil,nil,nil,
        nil,nil,nil,nil,
        nil,nil,nil,nil,
        nil,nil,nil,nil,
    }
    local i,n=1,0
    while x~=0 do
        local r=x%2
        if r==1 then
            x,n=x-1,n+1
            powers[n]=i
        end
        x,i=x/2,2*i
    end
end

运行一百万次迭代，x从1到1000000，花费0.29秒。我将幂表的大小初始化为16。

- Trey Reynolds

---

你的表格初始化没有任何作用（除了创建所需的空表）。在表格中，nil 既不能是键也不能是值。当你在表格中设置一个值时，键会自动添加 - 不需要调整表格大小。 - Tom Blodget

无论如何，不要只听我的话，而是请自行测试。当我不初始化表的前几个数字索引时，它运行起来会明显变慢。如果你进行测试，你也会看到同样的结果。 - Trey Reynolds

我相信这是因为垃圾收集器还没有时间来清理垃圾。您可以使用此技巧使表格创建速度显着加快。而不是 local o={} o.x=1 o.y=true，您可以使用 local o={x=1;y=true}。 - Trey Reynolds

我看到了非功能性的影响。当然，这取决于实现方式，但有时为了提高性能就需要这样做。 - Tom Blodget