Transforming a one-dimensional, "flattened" index into the N-dimensional vector index of an N-dimensional array

Question

I have an N-dimensional array, with the same number of items (i.e. the same "length") in each dimension.

Given a one-dimensional index into the array, I want a function that returns the coordinates associated with that index. The way that the array is indexed actually doesn't matter (in the sense that all of the dimensions of the array are equal, with none having precedence in terms of algorithms that will be operating on the array).

So, for example, if I have a 4x4x4 array, index 63 should return [3,3,3], index 0 should return [0,0,0] and index 5 should return [1,1,0].

I have written the following function, where nDim is the number of dimensions, and nBin is the length of each dimension:

def indicesOf(x,nDim,nBin) :
    indices = []
    for i in arange(0,nDim) :   
        index = (x/nBin**(i))%nBin
        indices.append(index)
        x -= index*nBin**i
    return indices

It seems to work -- but is there a more efficient way to make this calculation? To be honest, I have half "asked" this question just to share this solution, as I couldn't find a solution online. But if there is a more efficient way to do this, then great -- please share!

The function above is written in python, but I have just been using this to prototype a C (actually CUDA) function, so none of pythons wonderful libraries are available to me.

Here is a solution from combining JackOLantern and Eric's comments about the power of two sizes below. It seems to work for the handful of test cases I tried.

def indicesPowOf2(x,nDim,nBin) :
    logWidth = math.log(nBin,2)         
    indices = [0]*nDim
    for i in arange(nDim) :
        indices[i] = x & (nBin-1)
        x = x >> int(logWidth)
    return indices

Answer 1

You could avoid using ** (power operator) to reduce the computational cost, especially if you need to add this code to CUDA kernels.

The following way could be more efficient

void indices(int x, int nDim, int nBin, int indices[]) {
    for(int i=0;i<nDim;i++) {
        indices[i] = x % nBin;
        x /= nBin;
    }
}

If your nBin is a power of 2, you could use >> and & to replace the / and %.