Search code examples
javalogarithminvariantsloop-invariant

Java loop invariant

int logarithmCeiling(int x) {
    int power = 1;
    int count = 0;

    while (power < x) {
        power = 2 *power;
        count = count +1;
    }
    return count;
}

The code above is meant to be a method in Java for computing and returning the lower logarithm of a given positive integer using a while-loop. How would I provide an invariant for the loop above? i.e. that holds before it starts, every time the loop body ends, and the negation of the loop condition.

Solution

  • power always equals 2^count at the beginning and end of the loop. For the negation, when the loop is over, x <= power = 2^count.