Unsigned to signed without comparison

Question

To convert 32-bit unsigned to signed integer one could use:

function convert(n)
    if n >= 2 ^ 31 then
        return n - 2 ^ 32
    end
    return n
end

Is it possible to do it without that comparison?

PS: This is Lua, hence I cannot "cast" as in C.

Answer 1

Maybe you could do it with bit operations. In Smalltalk that would be:

^self - (2*(self bitAnd: 16r80000000))

Apparently bitops are not native in Lua, but various bit library seem available, see http://lua-users.org/wiki/BitwiseOperators

Once you find appropriate bitand function, that would be something like

return n - bitand(n,MAXINT)*2

Answer 2

Not in plain Lua. You could of course optimize the exponentiation and the if-statement away by writing:

local MAXINT, SUBT = math.pow(2, 31), math.pow(2, 32)
function convert(n)
    -- Like C's ternary operator
    return (n >= MAXINT and n - SUBT) or n
end

I do not know if optimizing the if-statement away will help the interpreter much; not for LuaJIT, I think; but probably for plain Lua?

If you really want to avoid the comparison, go for C, e.g. (untested code!):

int convert(lua_State *L)
{
    lua_pushinteger(L, (int) ((unsigned int) luaL_checklong(L, 1)));
    return 1;
}

However, stack overhead will probably defeat the purpose.

Any specific reason for the micro-optimization?

Edit: I've been thinking about this, and it is actually possible in plain Lua:

local DIV, SUBT = math.pow(2, 31) + 1, math.pow(2, 32)
-- n MUST be an integer!
function convert(n)
    -- the math.floor() evaluates to 0 for integers 0 through 2^31;
    -- else it is 1 and SUBT is subtracted.
    return n - (math.floor(n / DIV) * SUBT)
end

I'm unsure whether it will improve performance; the division would have to be faster than the conditional jump. Technically however, this answers the question and avoids the comparison.