Mathematical alternative to bit manipulation to set all bits to $0$ except the two most significant (highest order) set bits.

The following describes a function which I want to solve mathematically rather than resorting to binary bit manipulation is possible:

$y = f(x)$

where

• $x$ is an arbitrary integer equal to or greater than $zero$. $Zero$ can be omitted if that helps.
• The function $f(x)$ sets all binary bits of $x$ to 0 except the two most significant (high order) bits that are set. Example: $f(10101100)=10100000$ and $f(01111111)=01100000$.
• I already have the $base 2 log$ calculated for $x$.

Using this pre-calculated $log$ or some other method, can we calculate $y$ mathematically without resorting to bit manipulation?

I'm looking for an alternative since bit manipulation for arbitrarily large numbers can be quite inefficient depending on what software platform and language you use.

PS: I'm not even sure what keywords to tag this question with.

-

If you want to maintain the highest two 1 bits in a binary number, the code I gave in your previous question will work:

m=int(log_2(x)): finds the highest 1 bit

y=x-2^m: strips off that 1 bit

n=int(log_2(y)): finds the second highest 1 bit

f(x)=2^m+2^n

This is different from saving the two highest bits as most (including Brian M. Scott) would think the two highest bits of 10001000 were the leftmost 10, not the 2^7 bit and the 2^3 bit.

-
Thank you again. I did not realize your code was already doing that. As for the ambiguity, I have also corrected the question title and contents. – Raheel Khan Aug 20 '12 at 0:12

Let $n=\lg x$, where $\lg x$ is the binary log of $x$; then $2^n\le x<2^{n+1}$, so $x$ has $n+1$ bits. Then

$$f(x)=2^{n-1}\left\lfloor\frac{x}{2^{n-1}}\right\rfloor\;:$$

dividing by $2^{n-1}$ moves the binary point $n-1$ places to the left, taking the floor gets rid of everything to the right of the new binary point, and multiplying by $2^{n-1}$ pads that with $n-1$ zero bits.

-
Thanks. First, I'm assuming that even if the two highest-order set bits are separated by one or more 0s, this will still work. Second, I should have mentioned in my question that division of such large numbers is even slower than calculating Log. Your thoughts? – Raheel Khan Aug 19 '12 at 23:37
@Raheel: No, it will not. The two highest-order bits is not at all the same thing as the two highest-order set bits. If you’re interested in the latter, you need to modify the question. – Brian M. Scott Aug 19 '12 at 23:39
Thank you for pointing that out. I have updated the question. The objective is definitely the latter. – Raheel Khan Aug 20 '12 at 0:07

I'm looking for an alternative since bit manipulation for arbitrarily large numbers can be quite inefficient depending on what software platform and language you use.

I think you're approaching the problem in the wrong way, for two reasons:

• Math library routines are generally much slower than bit twiddling operations.
• Mathematicians will typically not answer these sorts of questions in a way that is well-suited for high performance library implementation.

I think you'll have much better luck asking your question on one of the programming-oriented sites, at least if you give the particular context you're working in. (e.g. specifically what language?)

Assuming you're not going to be writing custom low-level routines, I think it very likely that the best approach for your problem is simply to strip off the high bit, and compute the bit length again. e.g. in python

def f(x, bit_length = None):
if bit_length is None: p1 = x.bit_length()
else p1 = bit_length
hi = 1 << (p1 - 1)
x = x ^ hi
p2 = x.bit_length()
lo = 1 << (p2 - 1)
return hi ^ lo


or maybe use the usual trick to get the high bit: (I hope I'm remembering right)

def f(x):
hi = x & ~x
x ^= hi
lo = x & ~x
return hi ^ lo


(with the appropriate error checking if you need it, of course)

(warning: I've posted the above code without testing. Definitely check my implementation before using it!)

-