Integer logarithm base 2 in O (1)

It is often necessary to calculate the whole part of the logarithm base 2 of any integer.



The head-on decision is to make a loop and in this loop constantly divide the number by two until it becomes zero. How many such divisions have occurred, such is the value of the logarithm. Yes, this method works and has the right to life, but I want to show how it can be done without any cycles and complex structures.



So, we want to calculate the following formula:

$\$\$\; display\; \$\$\; y\; =\; [log\_2\; (x)],\; x\; is\; integer,\; positive\; \$\$\; display\; \$\$$

Decision

For those who are not interested in the reasoning, I will immediately give ready-made functions for calculating the logarithm:

uint32_t getHighBit_32(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x - (x >> 1);
}

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

Explanations

First, let's convert the number x to a binary notation of a certain length.



For example, length = 8, but this is not important and the length of the number can be any.



Now remember what the translation of a number to a binary notation is based on. To represent the number as a sum of powers of two. The degree number will determine the position of the bit, which is 1. For example:$\$\; inline\; \$\; 45\; =\; 32\; +\; 8\; +\; 4\; +\; 1\; =\; 2\; ^\; 5\; +\; 2\; ^\; 3\; +\; 2\; ^\; 2\; +\; 2\; ^\; 0\; \$\; inline\; \$$... Those. degree numbers 5, 3, 2 and 0. This means that the 5th, 3rd, 2nd, 0th bits are equal to 1. The rest of the bits between them are equal to zero. Bits start from the right side. It turned out that$\$\; inline\; \$\; 45\_\; \{10\}\; =\; 101101\_2\; \$\; inline\; \$$



It can be noted that the translation into binary notation is closely related to the exponentiation, and the logarithm is the inverse of the exponentiation and is equal to the exponent.

$\$\$\; display\; \$\$\; 2\; ^\; y\; =\; x,\; y\; =\; log\_2\; (x)\; \$\$\; display\; \$\$$

Moreover, the exponent to which you need to raise 2 is the number of a single bit in a binary notation. It turns out that if we find the number of a single bit, then we get the integer part of the value of the logarithm to base two. For example, if 32 = 100000, the one bit is in the 5th place, so the logarithm is 5.



But since there may be several ones, not 1, the question arises of which one bit to take to find the logarithm. The answer is the number of the last one bit, starting from the right side of the number recording, because it is the highest power of two that determines the whole part of the logarithm, the rest make up the fractional part of the logarithm.



Consider another example - a number$\$\; inline\; \$\; 45\_\; \{10\}\; =\; 101101\_2\; \$\; inline\; \$$... The last one bit is in the 5th place, so the integer part of the logarithm of 45 is 5. and indeed$\$\; inline\; \$\; log\_2\; (45)\; =\; 5.4919\; \$\; inline\; \$$... We discard the fractional part and leave 5.



It also works with other numbers.



As a result, we got that the whole part of the logarithm is equal to the number of the last one bit, counting from the right. Question: how to find the number of the last one bit?



For this, there are functions based on bitwise operations, which I found in the book by G. Warren "Algorithmic tricks for programmers".

• Rounding down to a power of two (or highlighting the last one bit in the binary notation of a number). In fact, you can round up, but then the value of the logarithm will also be rounded up.
• Counting the number of single bits in the binary notation of a number

Both functions are well described there, and I gave their code earlier.



Using these two functions, the algorithm for calculating the algorithm is as follows:

1. Select the last one bit in the number. Now the number has become written as 100000
2. Subtract one from the resulting number. Then the number will be like this: 011111
3. Count the number of unit bits and this will be the integer value of the logarithm

Exceptional situation

The logarithm has an exceptional situation when x = 0. In theory, such an algorithm does not exist (or in the limit it is equal to -∞). However, since we deviate a little from the laws of mathematics in programming, the functions still work even when the input of the function is zero. In this case, the value of the logarithm will be 32 (if the number is 32-bit). This is because the function of rounding to the nearest power of two will give 0, then we subtract one from zero and get the number 0xFFFFFFFF, and there are 32 units in this number, so the logarithm will be 32.



Yes, from the point of view of mathematics, this is incorrect, but there are cases, when it's useful from a programming point of view.

Counting the length of a binary code

It is unlikely that such a function will be used to calculate the mathematical logarithm, because logarithms of real numbers are often considered, rather than integers.

However, calculating the length of a binary code is a more common task in practice.



Let a binary code of a certain length be given. This could be, for example, a path in a binary tree. If a single bit is written in front of this code, then it is possible to calculate the length of this code without using auxiliary variables by taking an integer logarithm.



For example, let the code 0001110110 be given. It is written, for example, in a cell of 32 bits and we often need to read the length of this code. To do this, add an additional one bit before the code.



We get: 10001110110. And now we can safely calculate the length of this code through the integer logarithm, without separately storing the length of this code somewhere else.



If we consider the length of the code, where all zeros are, then the function will return the length = 32, which may be incorrect, so this situation must be foreseen. In some situations, it is useful for the function to return 32, and in others, for example, zero.

Sources

1. G. Warren “Algorithmic Tricks for Programmers. Revised edition. ", 2004