2

I need to find log(base2) of any number in Linux kernel programming. Is there any built in function for this operation? If not how to calculate it?

user3721893
  • 185
  • 1
  • 1
  • 7

2 Answers2

1

If it's enough for you an integer result, you can divide multiple times by 2. Something like

int logFunc(unsigned int x) 
{ 
   int log = -1; 
   while(x) { 
    log++; 
    x >>= 1; 
   } 
   return log; 
}

If you need fp ops, you should read this:

[...]if the question was "can I just use FP in the kernel" then the answer is still a resounding NO, since other architectures may not support it AT ALL.

  Linus

Link

Also, you can take a look to: Use of floating point in the Linux kernel

EDIT: If you need a faster version you can read Bit Twiddling Hacks - By Sean Eron Anderson

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
Community
  • 1
  • 1
rpax
  • 4,468
  • 7
  • 33
  • 57
  • a good way of dividing by two quickly here is `>>` do a binary search for the largest bit set to `1` of your unsigned int. – Alexander Oh Jun 09 '14 at 10:44
  • @Alex Thank you for your comment. I've added a resource with good implementations about this. – rpax Jun 09 '14 at 10:58
  • Those solutions work well to find log(base2) of integer numbers. But I also need to find log(base2) of non integers. – user3721893 Jun 09 '14 at 11:35
  • That's problematic. What are you trying to accomplish? – rpax Jun 09 '14 at 11:44
  • I need to find the value corresponding to clock frequency. Your method works if the frequency can be expressed as a power of 2. – user3721893 Jun 10 '14 at 04:35
1

By definition, the logarithm of a number N in any particular base B is equal to log(N)/log(B), where log() can be either the natural logarithm (base e), or any other base (e.g. base 10), as long as both log(N) and log(B) are calculated with respect to the same base.

twalberg
  • 59,951
  • 11
  • 89
  • 84