user1043761 - 7 months ago 59

C++ Question

Given a number 'n', which is a power-of-2, how can I efficiently find the 2 factors which are most equivalent to eachother? In other words, if I have a linear array and want to map it to 2D, how can I find the 2D dimensions that are the most equal (image dimensions most close to a square)?

Gotta be some kind of bitwise operation to make this fast, rather than looping over factors.

Answer

`n`

is representable as `2^k`

(since you say it's a power of 2). If `k`

is even, then `n == 2^(k/2) * 2^(k/2)`

(e.g. `16==4*4`

). If `k`

is odd, then the closest you can get is `n == 2^((k-1)/2) * 2^((k+1)/2)`

(e.g. `8==2*4`

)

Source (Stackoverflow)