Help with an algorithm

[Vaughan McAlley <vaughan@...>]

Greetings,

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?

Thank you,

Vaughan