Efficient way to get MSB position of a double variable

I am currently using the following equation to get the index of the most significant bit (MSB) of an integer value stored in a double variable.

xMsbIdx=ceil(log2(abs(x+1)))

I would like to know if there is a more computationally efficient way of doing it.

• Edit for clarification propose

[John D'Errico]

What is inefficient about this? This seems to be a very computationally efficient formula.

More importantly, why not explain what you mean by MSB position? If you choose some jargon that nobody else will understand, then you need to explain what you are doing.

Answer 1

[Guillaume]

My guess is you're trying to get the index of the most significant bit of an integer, not a floating point double (where a number is divided in two parts, mantissa and exponent, so not sure what you'd call the msb).

To get that value:

xMsb = nextpow2(x);

is simpler but probably not as fast as your algorithm. You can look at the code for nextpow2, it is implemented as m file.

[Jose Marcelo Duarte]

You are right. I'm trying to get the index of the most significant bit of a variable. I will edit the question to clarity this.

You help me realize that my current equation only works with integer numbers. It should be

xMsbIdx=floor(log2(abs(x))+1)

to work with floating point numbers too, but my current problem only requires the MSB index of integer numbers.

I was thinking that a better solution, in therms of computational complexity, could exist using bitget(), or other MatLab native function that I do not know.

[Guillaume]

Again, the question does not make much sense for non-integers. For example, the binary representation of 0.1 as double is 0011111110111001100110011001100110011001100110011001100000000000, where 0 is the sign, 01111111011 is the exponent and the rest the mantissa. Not sure what you'd call the msb of that.

Even for integers, as it is your algorithm only makes sense for positive integers. -1 as a 16 bit integer is 1111111111111111.

If you look at the code of nextpow2 you'll see that for integers stored as double (or single) it uses a variation of your log2(abs(x)) algorithm. For integers actually stored as integers (i.e, of class int8, uint8, int16, etc.) it uses bitshift.

In theory, the most efficient algorithm, for a positive scalar stored as integer would be

msb = 0;
while x > 0
   x = bitshift(x, -1);
   msb = msb + 1;
end

However, if the integer is stored as double as is normally the case in matlab, the above will involve many conversions from double to integer internally and thus will be slow.

Unless you prove with the profiler that finding the msb is a bottleneck for your code, I would highly recommend that you use nextpow2. Unlike your formula, it is immediately clear what its purpose is. Code clarity should by default be more important than speed.

[Jose Marcelo Duarte]

Thank you Guillame! I will follow you advise!

About the use of that equation for non-integer, I was thinking about converting a floating point value in a mantissa value and a exponent, like the code below.

x = .0345;
xMantBitWidth = 8;
xExp = floor(log2(abs(x))+1)-xMantBitWidth;
xMant = round(x*2^-xExp)
err = abs(x-(xMant*2^xExp))/x

[Guillaume]

Not sure I understand what you're doing here. double precision numbers are encoded with 64-bits, 1 bit for sign, 11 bits for exponent, and 52 bits for the mantissa. If you want to get the bits:

x = 0.0345;
bits = dec2bin(typecast(x, 'uint64'), 64);
sign = bits(1)
exponent = bits(2:12)
mantissa = bits(13:end)

[James Tursa]

Realize that for IEEE floating point representations, there is a hidden leading 1 mantissa bit for normalized finite non-zero values. So for numbers in that class you might need to prepend a 1 bit to the mantissa, depending on what you are doing with that mantissa downstream.

[Jose Marcelo Duarte]

Guillaume, Thank you again!! I found your solution more elegant than mine. Although I have to make some modification on it to become useful for me. Since I have to do operations using the mantissa and exponent value with others integer variables, I do not want them as char arrays.

I always do a MatLab model before implement a complex algorithm in RTL. I use the MatLab model as a reference model for the RTL design and I also use it to check its performance in terms of SQNR. Since, I do not have the fixed-point toolbox, I have to add some code to simulate the word-width limitation that I will have in my RTL implementation.

[Stephen23]

Note that mantissa is defined mathematically as being the fractional part of a logarithm (as it always has been), and that the significant digits of a floating point number are more clearly named the significand. Using mantissa for parts of floating point numbers is misleading as the two concepts have quite different properties.

http://mathworld.wolfram.com/Mantissa.html

[Guillaume]

@Stephen,

Noted. My misuse is probably because in French, as far as I know, the only term in use is mantisse.

Even in english, wikipedia says that This digit string is referred to as the significand, mantissa, or coefficient but I'll use significand from now on.

[Jose Marcelo Duarte]

I just found out about MatLab [F, E] = log2(x) function! This function is the perfect tool for design/model the word-width limitation of my RTL model.

Answer 2

[Walter Roberson]

num2hex() of the value will give you the hex representation of the internal value. The first bit is the "separate sign" bit (two's complement is not used). The next 11 bits are the exponent, with a bias of 1023.

The File Exchange Contribution https://www.mathworks.com/matlabcentral/fileexchange/25326-ieee-754-binary-representation returns the breakdown as binary.

If performance is important, use a mex routine. Watch out for the fact that the values will be stored "little endian".