Efficient way to get MSB position of a double variable

Question

Jose Marcelo Duarte 2017-11-10

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/366284-efficient-way-to-get-msb-position-of-a-double-variable

评论： Jose Marcelo Duarte 2017-11-16

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

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

John D'Errico 2017-11-10

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 2017-11-10

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/366284-efficient-way-to-get-msb-position-of-a-double-variable#answer_290410

编辑：Guillaume 2017-11-10

在 MATLAB Online 中打开

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.

9 个评论
显示 7更早的评论隐藏 7更早的评论

Guillaume 2017-11-10

在 MATLAB Online 中打开

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.

Guillaume 2017-11-13

@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 2017-11-16

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 2017-11-10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/366284-efficient-way-to-get-msb-position-of-a-double-variable#answer_290452

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".