0
n = 2 ^ x

I know the value of n, what is the efficient way to find the value of x ?

Hakkim Ansari
  • 119
  • 3
  • 10
  • 3
    In C, `^` is an bitwise exclusive-or; and are you thinking of integers or of doubles? – Basile Starynkevitch Sep 15 '15 at 08:20
  • 2
    If n is always a power of 2 and int, take a look of [bitwise operators](https://en.wikipedia.org/wiki/Bitwise_operations_in_C), specifically to right shift. – LPs Sep 15 '15 at 08:21
  • 1
    Will `x` always be a positive integer? – Bathsheba Sep 15 '15 at 08:24
  • Efficient way [for an integer. For floating-point values use `log2()` as in the below answers]: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious – phuclv Sep 15 '15 at 09:25
  • Is there a FAQ / best-practices version of this question that we can link all the duplicates to? If there's an idiom that some compilers can compile into `bsr` or `lzcnt` instructions, that'd be useful since AFAIK, C doesn't have a portable way to generate such instructions on architectures which have them. (x86, arm, ppc, at least: https://fgiesen.wordpress.com/2013/10/18/bit-scanning-equivalencies/) – Peter Cordes Sep 15 '15 at 16:30

5 Answers5

6

Assuming you mean n = 2x, then this is called logarithm base 2.

In C you can write:

double n = 512;
// ...
double x = log(n) / log(2);  // 9

That formula works for any base (replace 2 by the base). As pointed out by Kii, since C99 there is in fact a function specifically for base 2:

double x = log2(n);

Note that using <tgmath.h> instead of <math.h> will enable autodetection of which floating point type you are using.

M.M
  • 138,810
  • 21
  • 208
  • 365
2

I guess you are thinking of integer numbers, e.g. long or int (and their unsigned variants) and if you are using a recent GCC compiler, and if you are sure that n is a power of 2, then consider using the __builtin_ffs builtin (or __builtin_ffsll for long long, etc...) function (find first set bit). It is probably the fastest.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • 1
    If `n` isn't a power of 2, you can't use POSIX `ffs()`, but you can use `__builtin_clz` (count leading zeros). See https://en.wikipedia.org/wiki/Find_first_set#CTZ for a list of compilerspecific ways to get the native CPU instruction. (at least arm, x86, powerpc, and alpha have a count leading zeros insn. On x86, `bsr`'s result is undefined for `n==0`, and the `lzcnt` instruction from BMI1 isn't available before Haswell. (And it's encoded as `rep bsr`, so you get wrong results instead of a fault on older CPUs.) – Peter Cordes Sep 16 '15 at 15:16
1

IF it is a positive int or an unsigned int, you can shift right the single 1 bit till you have only zeroes, and count how many times you shifted.

EDIT for the sake of completeness (yeah, I know it is bugged for num = 0 :-p):

#include "stdio.h"

int main(void)
{

unsigned int num = 65536;

int pow = -1;

while (num > 0)
{
    num >>= 1;
    ++pow;
}

printf("%d ", pow);

return 0;
}
rookie coder
  • 141
  • 1
  • 8
  • this is an obvious but inefficient way. – phuclv Sep 15 '15 at 09:31
  • @LưuVĩnhPhúc how would you make it more efficient? – rookie coder Sep 15 '15 at 12:07
  • look at my comment on the question – phuclv Sep 15 '15 at 12:16
  • @LưuVĩnhPhúc I don't see how anything can be faster than a shift (except for manual assembly, but that's not C), which is the very same way is proposed in the site you and Ouah before you proposed. – rookie coder Sep 15 '15 at 12:51
  • You may need 32 shifts on a 32-bit int, and ~32 increments and jumps as well. Did you look at the versions below? They need only a few operations which will be extremely fast. Yours is only fast for small values – phuclv Sep 15 '15 at 12:54
1

The obvious way:

unsigned int v; // 32-bit word to find the log base 2 of
unsigned int r = 0; // r will be lg(v)

while (v >>= 1) // unroll for more speed...
{
  r++;
}

See Stanford Bit Twiddling Hacks page for fast (O(lg(N)) bit hacks to do it.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
ouah
  • 142,963
  • 15
  • 272
  • 331
0

If you can use inline assembly and if the input is integer, the fastest method would be to count the position of the most-significant bit.

int n = 9;
__asm
{
    mov eax, n
    bsr eax, eax
    mov n, eax
}
printf("%d", n);
justyy
  • 5,831
  • 4
  • 40
  • 73
  • 4
    This is x86 specific, and *nasm* assembler syntax specific – Basile Starynkevitch Sep 15 '15 at 08:38
  • Why would you use two `mov` instructions, instead of just `bsr n, n`, and leave it up to the compiler to have `n` in a register for you? IDK about MSVC's 32bit-only inline asm, but gcc inline asm lets you put constraints on variables to be used in inline asm. In any case, it would be far better to use an intrinsic function (which would be no more compiler specific than this). – Peter Cordes Sep 15 '15 at 16:00
  • you can't. bsr does not take two memory locations, it needs to be register. you will get "C2415: improper operand" if you do 'bsr n, n' – justyy Sep 15 '15 at 16:13
  • @DoctorLai: I was saying you should leave it to the compiler to give you `n` in a register, not to run `bsr` with memory operands. So MSVC doesn't have a way to pass operands into inline asm through registers? The compiler has the spill them to memory, and then your inline asm has to load them? That's total crap, no wonder they got rid of that for 64bit code. gcc can do: `int bsr(int in) { int out; asm ("bsr %1, %0": "=r" (out) : "r" (in) : ); return out; }` which compiles to `bsr edi, eax / ret`. https://goo.gl/e6mvFk. No ridiculous loads and stores. – Peter Cordes Sep 16 '15 at 15:06