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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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!)