Styjun

In our algorithms class, we've got an extra question in the lab session by the professor. Find the floor(log2(x)) for an int of n bits in log2(n) steps (e.g. when T = uint64_t, then n = 64).

We've found that we should be able to solve this with binary search, but we get an off by 1 result or an endless loop in certain edge cases. We're scratching our heads for some time, but cannot seem to get this right. How do we best deal with this? We've tried to reason with the invariant trick as discussed here, but it seems to be a little more complex than. E.g. for a decimal number, when choosing between bit 7 or 6 is difficult as 128 is larger than 100, but 64 is smaller. Unfortunately, when mitigating this, we break some edge cases.

EDIT: As noted below, this is purely an academic question with low to none usability in real-life scenario's.

Here is our code so far:

//
// h l
// 76543210
// 0b01000001 = 65
//

using T = unsigned char;

int lgfloor(T value)

 assert(value > 0);

 int high = ((sizeof(value) * 8) - 1);
 int low = 0;
 int mid = 0;
 T guess = 0;

 while (high > low)
 
 mid = (low + ((high - low) / 2));
 guess = static_cast<T>(1) << mid;

 printf("high: %d, mid: %d, low: %dn", high, mid, low);

 if (value < guess)
 
 high = mid - 1;
 
 else
 
 low = mid;
 
 

 return low;

We have created the following unit tests (using GoogleTest):

TEST(LgFloor, lgfloor)

 ASSERT_DEATH(lgfloor(-1), "Assertion `value > 0' failed.");
 ASSERT_DEATH(lgfloor(0), "Assertion `value > 0' failed.");

 ASSERT_EQ(lgfloor(1), 0);
 ASSERT_EQ(lgfloor(2), 1);
 ASSERT_EQ(lgfloor(64), 6);
 ASSERT_EQ(lgfloor(100), 6);

Thanks in advance,
with kind regards,

Marten

You need a proper exit condition. Let's say y = floor(lg2(x)). You should exit the loop when 2^low <= x and x < 2^(low+1). But if high == low+1 then this is fulfilled, yet you do not currently exit. Just do:

while (high > low+1)
{

It is good to look at invariants in your loop. For example, we could try to maintain x < 2^high (that would require starting at sizeof(T)*8, not sizeof(T)*8 - 1). Then all you need to do is bisecting until low == high-1 and you are done.

We can maintain this invariant by only changing high to mid if x < 2^mid, i.e. if value < guess. That's the first case:

if (value < guess)
 high = mid;

We further must maintain 2^low <= x = value. So, in the else branch (which requires 2^mid == guess < value, we can safely set low = mid.

else
 low = mid;

All that is left is to prove that the loop always progresses. Since high > low+1, we have high - low >= 2 and thus mid != low and mid != high. Clearly, we are reducing the interval (by half) each iteration.

So there you go:

int lgfloor(T value)

 assert(value > 0);

 int high = (sizeof(value) * 8);
 int low = 0;

 while (high > low+1)
 
 int mid = (low + ((high - low) / 2));
 T guess = static_cast<T>(1) << mid;

 printf("high: %d, mid: %d, low: %dn", high, mid, low);

 if (value < guess)
 high = mid;
 else
 low = mid;
 

 return low;

I should of course note that there are dedicated intrinsics for this exact purpose in modern hardware. For example, search Intel's intrinsics guide for _BitScanReverse which will complete in a fraction of the cycles the above code would take.

One way or another, asymptotic runtimes that depend on bit-width are pretty meaningless when dealing with fixed-width types such as C++' integral ones (although the question has educational value still).

Endless loop is due to this line:

 mid = (low + ((high - low) / 2));

if high and low is differ by 1, the result could be mid == low and then at the condition that cause low = mid inside the while loop, you resulted in checking the same condition forever. My suggestion would be, if you have low = mid in the loop, you have to make sure your mid != low in that case. So just check this before the assignment and do low = mid+1 instead if that happens.

The solution must be found in lg(n) steps, which means that an initialisation such as low= 0, high= 32 won't work, because it would take 5 steps in every case and wouldn't work for x larger than 2^32. A correct solution must combine a first geometric search where you double the exponent, then a standard dichotomic search.

# Geometric search
low= 0
high= 1
while (1 << high) <= x:
 low= high
 high+= high

# Dichotomic search
while high - low > 1:
 mid= (high + low) >> 1
 if x < mid:
 high= mid
 else:
 low= mid

Seems like you just have to shift if to the right 'log' times, until you have a '1'.

using T = unsigned char;

int lgfloor(T value)

 assert(value > 0);

 int log = 0;
 while(value != 1) 
 value >> 1;
 log++;
 
 return log;