0

Consider an arbitrary binary vector of dimension n. For n=4, an example vector might be 1100.

For such a vector, I'd like to know the top-most position whose bit has the value of 1. For the 1100 example above, I'd like to get the answer 4 (counting from the right).

A recursive O(log(n)) solution (more or less binary search) for the example case above is

  1. Start with 1100
  2. Split down the middle into two 2-bit vectors 11 and 00
  3. Is the first of these greater than zero? Yes it is, so we focus now only on the first 2-bit vector (i.e. we know that our position answer can't be 1 or 2...it must be 3 or 4)
  4. Split 11 into two 1-bit vectors 1 and 1
  5. Is the first of these greater than zero? Yes, and it's also 1-bit long. We know that this is our position, so we return it.

My question: Assuming in a practical setting that 1) n is not greater than the word size on a general-purpse computer (i.e. n<=64), and 2) that we're given the "common" general-purpose instruction set, is there any way to do this in O(1) operations (worst case) with respect to the size of the vector instead of O(log(n))? I'm quietly hoping that there might be some combination of bitwise instructions that one could exploit, although my hopes are not high :(.

Note: using some kind of static structure which maps each possible vector to a result is not practical (would require too much memory for e.g. the n=64 case).

sammy34
  • 5,312
  • 5
  • 29
  • 42
  • 1
    For a real computer, this would be a [dupe of this question, I guess](http://stackoverflow.com/questions/2589096/find-most-significant-bit-left-most-that-is-set-in-a-bit-array). :) – unwind Jul 09 '14 at 09:19
  • Nice! I wasn't aware of BSF and BSR! Do these instructions actually execute in one clock cycle though (i.e. are they actually implemented in hardware or are they just a macro for a different technique)? – sammy34 Jul 09 '14 at 09:36
  • 1
    It varies (a lot, it seems) with the exact processor model. – unwind Jul 09 '14 at 09:40
  • Thanks! I guess if this is a duplicate it's not worth going through the entire answering process right? I'll just upvote your helpful comments and flag this as a dupe. – sammy34 Jul 09 '14 at 09:44
  • 1
    If you're also interested in more theoretical answers, there is an O(1) algorithm for this (but it includes multiplications) and a multiplication-free O(log log n) algorithm (for them, as in this question, it is assumed that n-bit operations take constant time). Both are covered in The Art of Computer Programming V4. Neither are, in practice, anywhere near as good as `bsr` or various other hardware specific tricks – harold Jul 09 '14 at 11:22
  • Thanks for your comment and reference Harold :). Although the problem that motivated my question is more practical in nature, I'm always fascinated by the theoretical side too. I'll check it out :). – sammy34 Jul 09 '14 at 11:47

0 Answers0