Given a number A(=2^N), how to get the N?

Question

For example,

Input   result
2       N: 1
4       N: 2
8       N: 3

Is there such function that I can directly use in c?

Or is there any quick simple method to get the N?

Mine:

// assume A is not very big

int getN(int A) {
  int i = 0;
  for(i = 0;;i++) {
    if( 1 << i == A ) return i;
  }
}

Use [log2](http://en.cppreference.com/w/c/numeric/math/log2) or [ilogb](http://en.cppreference.com/w/c/numeric/math/ilogb) — BLUEPIXY, Oct 19 '17 at 05:38
Is the input guaranteed to fit in a `long` (i.e. at most 64 bits)? Please **edit your question** — Basile Starynkevitch, Oct 19 '17 at 05:50

Basile Starynkevitch · Answer 1 · 2017-10-19T05:59:59.647

Assuming the input fits in a long, if you don't care much about performance, use log2 to compute the logarithm in base 2 (then cast it to an int) per other answers. BTW your naive getN is practically fast enough (but would loop indefinitely for a 0 input, you could limit that with for(i = 0; i<64; i++) ), and might even be faster than a log2, and you could make it a static inline function (in some header file).

If you are using GCC and if you know that the input is a power of 2 (so has exactly one bit set), you could use the faster __builtin_ffs builtin (find first set bit).

If the number is very large, you want to do arbitrary precision arithmetic. Then use a library like GMPlib.

score 2 · Answer 2 · answered Oct 19 '17 at 06:27

If you like to use a custom recursive function to get N , use this function. Otherwise go for log of input.

int getN(int num){
    if((num/2)==1){
        return 1;
    }
    else if((num%2)!=0){
        return 0;
    }
    else{
        return (1 + getN(num/2));
    }
}

score 1 · Accepted Answer · answered Oct 19 '17 at 05:39

Sure there is - log2 ( double d )

Use like this:

#include <math.h>
#include <stdio.h>
#define N somenumber
int main(){
    int a = 1 << N;                     // == 2 raised to the power of N
    printf("%d", (int)log2((double)a)); // output: N.   can leave out the cast, for double format result
    return 0;
}

Given a number A(=2^N), how to get the N?

3 Answers3