Checking a binary number is OK

Question

In connection with a problem I'm solving, I need to check if a binary number with $n$ digits is of a certain form. The number is OK if:

1. It is all $0$'s
2. The first digit is $1$ and the rest $0$'s
3. The first 2 digits are $1$'s and the rest $0$'s
4. The first 3 digits are $1$'s and the rest $0$'s
5. Etc

Is there a quick way to determine that a number is of this form? I.e. without having to check each digit, starting from the front?

Answer 1

A nonzero number is of the required form if and only if flipping the bits and adding $1$ results in a number with exactly one $1$ bit. Assuming that you are not using some antique computer, flipping the bits and adding $1$ is the same as negating the number. Now there is a quick way of testing whether a number has exactly one $1$ bit. Subtract $1$ and do a bitwise and with the original number. The result is $0$ if and only if the original number had exactly one one bit.

The above operation (x &= x-1 in python) works because subtracting 1 replaces the rightmost $1$ by a $0$, the $0$s to it right by $1$1, and leaves all bits to the left unchanged. Therefore, the operation zeroes the rightmost $1$ bit.

EDIT Actually, the operation works for $0$ also, so you don't even have to test a special case. In python you just need

if x & (x-1) == 0: whatever

Just to clarify, in the above, $x$ is the negative of the number you started with. In actual code, you'd probably use

if -x & (-x-1) == 0: whatever

Answer 2

Do a binary search. Check if number formed by first $\lfloor \frac{n}{2} \rfloor$ digits is equal to 1s etc. If the number is lesser or greater you split and proceed. Stop if you cannot split any more -- number is not of required form. Complexity should be of the order of log(n).

Answer 3

Your numbers are of the form $2^{n-1}-2^k$ for some $k$ between $0$ and $n-1$. The first is the $k=n-1$ case, the $n^{th}$ is the $k=0$ case. You can just check if your number is equal to any of these. Of course, that is $n$ checks, which is the same number as if you just check the bits.

Answer 4

An OK number is of the form $(2^m-1)2^n$.

Divide the number by two until you get a remainder. You now have $2^m-1$.
Add one. You now have $2^m$.
Divide by two until you get a remainder. You now have $1$.
If the final value is not one, your original number's not OK.

If you precede the original number with a $1$, this will work for the all zeros case as well.

Answer 5

A simpler way of putting it is that it is a string of $k; 0\le k$ ones followed by $m; 0 \le m$ zeros.

A number $x$ followed by $m$ zeros is $x*2^m$.

A number $x=$ a string of $k$ ones is $2^k -1$.

So you want numbers of the form $(2^k - 1)*2^m$.

Divide by two successively until you either get to $0$ or get to a point where you have a remainder. If you get to $0$ it is of the form. If you get a remainder then divide by subtract $1$ and divide by $0$ successively until you either get to $0$ or get to a point where you don't have a remainder. If you get to $0$ it is of the form. If you get to a point where you don't have a remainder it is not of the form.