lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On 5/24/2013 1:29 PM, Vaughan McAlley wrote:
Sorry if this is more suited to a general programming forum—I hope
the solution will be in Lua, and there are some pretty switched on
people here...

I’d like to iterate through all 40-bit binary numbers that have a
Hamming weight of 25 (ie. 25 of the bits are set to 1). My naive
solution of testing the Hamming weight of all 40-bit numbers looks
like it will take half a year :-) , even with a fairly quick
calculation of Hamming weight using 14-bit lookup tables...

An alternative could use something like this:

num = {}

for i = 1, 15 do num[i] = "0" end
for i = 16, 40 do num[i] = "1" end

n = tonumber(table.concat(num), 2)  -- test n

Is there an efficient way of iterating through all combinations of
"0" and "1" in num?

Maybe chop the number into two, giving two 20-bit segments. Each segment will have 5-20 set bits. Build tables for each number of set bits, then match two segments, e.g. 8 set bit in segment A will give 17 set bits in segment B. With tables precalculated, get the final number by putting A and B together. Not sure about the memory requirements, though...

Kein-Hong Man (esq.)
Kuala Lumpur, Malaysia