1

I wanted to see if there is a method for finding the binary log of a number. Say you have the number 4 then the power to which you raise two to get four is 2.

I know this is possible with shifting and counting but that uses O(N) operations. Is there some way to get O(1) for any n where x = 2^n?

I want to find n here knowing x in one operation or O(1).

pandoragami
  • 5,387
  • 15
  • 68
  • 116

1 Answers1

2

As you've specified x86, it sounds like you want the BSR (bit-scan reverse) opcode, which reports the position of the most-significant set bit.

[FYI: big-O notation refers to asymptotic complexity (i.e. as N -> infinity); it doesn't make much sense if N has a finite limit (32 or 64 in this case).]

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • `BSR` is an x86 instruction. I'll have to look it up, thanks for the `FYI`. I hardly ever use this stuff, only when I get creative. – pandoragami Jul 15 '13 at 00:01
  • Depending on what compiler you are using there will most likely be an intrinsic you can use for this to save you writing asm - certainly both gcc and MSVC have such intrinsics (albeit with different names). – Paul R Jul 15 '13 at 06:38
  • @Paul R I'm using GCC, I looked all over the intrinsics for this and I can't find anything that would work similar to `BSR`. Let me know if you think of something. – pandoragami Jul 15 '13 at 06:47
  • 2
    For gcc it's `__builtin_clz` (where `clz` stands for Count Leading Zeroes). See [this question](http://stackoverflow.com/questions/13476983/find-first-1-in-binary-number/13477081#13477081) for more details for gcc and MSVC. – Paul R Jul 15 '13 at 07:03
  • 2
    @PaulR good ref, "Count leading zeroes" is what gets you this on a lot of architectures other than x86. See the table on http://en.wikipedia.org/wiki/Find_first_set for other instruction sets. – FrankH. Jul 15 '13 at 09:59
  • @FrankH: yes, unfortunately it goes by several different names: CLZ, FFS, BSR, etc, but I tend to think of it as CLZ. – Paul R Jul 15 '13 at 10:02
  • On a slightly different angle ... newer (post-Nehalem Intel / post-Barcelona AMD) x86 CPUs actually have `lzcnt` to _shortcut_ the need to post-process `bsr` results (subtract from number of bits in operand and do zero detection). – FrankH. Jul 15 '13 at 11:50