Setting or Clearing Trailing bits

Here is the method I found on the group called AlogGeeks (on Google Groups).

The question was about verifying the following RegEx:
1+0+1

The following solution was proposed by Dave and it is really elegant.

bool OnesZerosOnes(unsigned int n)
{
if( !(n & 1) || !(n &= n+1) ) return 0;
n |= n-1;
return !(n & (n+1));
}

Here is how it works:

!(n & 1) is true if the number has trailing zeros.

If the number has trailing ones, n &= n+1 replaces the trailing ones with zeros.

!(n &= n+1) is true if there are only trailing ones, i.e., the original number was zeros followed by ones.

n |= n-1 replaces trailing zeros with ones. Thus, if the original number is ones followed by zeros followed by ones, the zeros have been changed to ones.

(n & (n+1)) replaces the trailing ones with zeros. If the number is now zero, the number is valid, otherwise the number is invalid.

Thanks to Dave!!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s