CODEWITHSUNDEEP
pythonluacode-translation
Josh
Josh

Reputation: 3265

Lua: Decompose a number by powers of 2

This question is a parallel to python - How do I decompose a number into powers of 2?. Indeed, it is the same question, but rather than using Python (or Javascript, or C++, as these also seem to exist), I'm wondering how it can be done using Lua. I have a very basic understanding of Python, so I took the code first listed in the site above and attempted to translate it to Lua, with no success. Here's the original, and following, my translation:

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

Unfortunately, my version locks and "runs out of memory". This was after using the number 12 as a test. It's more than likely that my primitive knowledge of Python is failing me, and I'm not able to translate the code from Python to Lua correctly, so hopefully someone can offer a fresh set of eyes and help me fix it.

Upvotes: 3

Views: 574

Answers (2)

Trey Reynolds
Trey Reynolds

Reputation: 763

I saw that in the other one, it became a sort of speed contest. This one should also be easy to understand.

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.

If the remainder is 1 then you know that i is a power of two which is used in the binary representation of 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

Running a million iterations, x from 1 to 1000000, takes me 0.29 seconds. I initialize the size of the powers table to 16.

Upvotes: 4

Josh
Josh

Reputation: 3265

Thanks to the comments from user2357112, I've got it fixed, so I'm posting the answer in case anyone else comes across this issue:

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

Upvotes: 4

Related Questions