Calculate divisions depth

Question

Imagine having a line segment A of size S (ex. 64 units). To calculate this segment depth D it's divided incrementally by 2. No division means depth is 0, divided once means depth is 1 (2x32), dividing the divided again by 2 - D = 2 (4x16), and so on.

Now I have another segment B (ex. 7 units), that I want to fit inside A and calculate it's depth for A.

As I am a programmer, firs comes to mind is an iterator:

let size = 64;
let fit = 7;
let depth = 0;

while(true){
  size = size  / 2;

  if(size <= fit){
    if(size == fit) depth += 1;
    break;
  }else{
    depth += 1;
  }
}

console.log(depth);

But I don't think its efficient. There must me a mathematical formula, that can calculate D given A and B and knowing that depth division happens by factor of 2.

Are we guaranteed that size will be a power of 2? If not, what is the result of dividing an odd number by 2: a decimal/floating point number, or the integer quotient when the remainder is discarded? — Greg Martin, Jan 25 '20 at 09:19
Hint: look at the binary representation of "fit" and the consecutive "size"s. — random, Jan 25 '20 at 13:34

score 1 · Accepted Answer · answered Jan 25 '20 at 18:37

Let's write $S$ for size and $F$ for fit. It seems you want to return the answer $0$ when $S/2 < F \le S$, return the answer $1$ when $S/4 < F \le S/2$, return the answer $2$ when $S/8 < F \le S/4$, and so on.

Mathematically, you are looking for the largest nonnegative integer $n$ such that $S/2^n \ge F$. This inequality is equivalent to $2^n \le S/F$, which in turn is equivalent to $n \le \log_2(S/F)$ (that's the base-$2$ logarithm). The largest such integer is $\lfloor \log_2(S/F) \rfloor$, by definition of the greatest-integer function. Therefore you'll want a formula like depth = floor( log2( size/fit )).

Calculate divisions depth

1 Answers1