Lua：将一个数字分解为2的幂的和

2017-5-23 11:46:28
收藏：0
阅读：112
评论：2

这个问题与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，因此希望有人能提供新的眼睛并帮助我修复它。

点赞
用户308010
用户308010

感谢用户 user2357112 的回复，我已经修复了问题，因此在这里发布答案，以便其他人遇到类似问题时可以参考:

function powerfind(n)
  local powers = {}
  i = 1
  while i <= n do
    if bit.band(i, n) ~= 0 then -- 位与检查
      table.insert(powers, i)
    end
    i = bit.shl(i, 1) -- 位左移
  end
  return powers
end
2015-05-25 21:06:25
用户3159048
用户3159048

我看到另一个版本变成了一种速度比赛。这一个应该也易于理解。

i是当前的幂。它不用于计算。
n是数组中当前的位置。
r是x除以2的余数。

如果余数为1，则知道i是在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秒。我将powers表的大小初始化为16。

2015-05-25 21:49:19

作者:

用户308010

用户308010
推荐文章