NextPow2

[Arhowk]

I need a function that will return the next highest power of two and im too lazy to do it. Is there a library that exists to do it?

E/ i need it to return n of 2^n, not n of n.

 

[PurgeandFire]

um, given some number, e.g. 2:

function NextPowerOfTwo takes real input returns real
    return input * 2
endfunction

If you input 2, it will return the next power of 2 (e.g. 4). If you input 64 (2^6), it will return 128 (2^7).

EDIT: n of 2^n would just be ln(result) / ln(2):
http://www.wc3c.net/showthread.php?t=103494

EDIT2: if you explain a bit better, there can be a better solution (if you are just working with powers of 2).

 

[Arhowk]

um, given some number, e.g. 2:

function NextPowerOfTwo takes real input returns real
    return input * 2
endfunction

If you input 2, it will return the next power of 2 (e.g. 4). If you input 64 (2^6), it will return 128 (2^7).

EDIT: n of 2^n would just be ln(result) / ln(2):
http://www.wc3c.net/showthread.php?t=103494

EDIT2: if you explain a bit better, there can be a better solution (if you are just working with powers of 2).

Im saving for a custom inventory i posted a little while ago on the lab using nes's save system in a stack.

What i want to do is this

push(NextPow2(trait.val),31)
push(trait.val,Pow2(NextPow2(trait.val)))

so if the value is 250,

nextPow2 of 250 is 8 (The next highest power of two is 256, 2^8 (Eight is the number im looking for here)) so it ends up executing as

push(8,31)

now it pushes (250, 2^(NextPow2(trait.val))) nextpow2 was already found out before to be 8 so

push(250,2^8) = push(250,256)

E/ i think this works for me

    function NextPow2 takes integer n returns integer
        local integer currentPow = 1
        local integer currentRaw = 2
        loop
            exitwhen currentRaw >= n
            set currentPow = currentPow + 1
            set currentRaw = currentRaw * 2
        endloop
        return currentPow
    endfunction

 

[PurgeandFire]

Well, I was bored so I whipped up an alternate version:

library NextPow2 initializer Init
 
    globals
        private integer array pow

        // pivot point of list (for first comparison)
        private constant integer PIVOT = 15
    endglobals
 
    function NextPow2 takes integer number returns integer
        local integer first = 0
        local integer last  = 31
        local integer middle = PIVOT
                
        if number < 1 then
            return -1
        endif
 
        loop
            exitwhen (last - first) == 1
            if number == pow[middle] then
                return middle
            elseif number > pow[middle] then
                set first = middle
            elseif number < pow[middle] then
                set last = middle
            endif
 
            set middle = (first + last) / 2
        endloop

        return last
    endfunction
 
    private function Init takes nothing returns nothing
        local integer i = 1
 
        set pow[0]  = 1
        set pow[31] = 2147483647
 
        loop
            exitwhen i == 31
            set pow[i] = pow[i - 1] * 2
            set i = i + 1
        endloop
    endfunction
 
endlibrary

It is much longer and far more convoluted than the standard method. That instantly means it is better.

It pretty much has a static complexity of 5 iterations (unless the number input is a power of 2, then it can be lower). If you alter the pivot, you might be able to get different complexities (e.g. if you lower it, you may chip off 1 iteration for some lower powers, but it may increase the complexity for powers above 2^pivot).

Remember the formula for success: sugar + spice + everything nice + unnecessary complications = nanoseconds saved for your life to spend time with your future children