Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Formula to identify special binary numbers

Posted on 2013-02-06
Medium Priority
433 Views
I need a formula that will tell me if a number, when converted to binary, has 1's with 0's between them.

Example -

00 = 00000000
01 = 00000001
02 = 00000010
03 = 00000011
04 = 00000100
05 = 00000101  *
06 = 00000110
07 = 00000111
08 = 00001000
09 = 00001001  *
10 = 00001010  *
11 = 00001011  *
12 = 00001100
13 = 00001101  *

in the above binary representations, 5, 9, 10, 11, and 13 have 1's with one or more 0's between them so I would want a formula that returns true -

Example -
fncSpecialBinary(4) returns false
fncSpecialBinary(5) returns true

Thanks,

Kevin.
0
Question by:kevinvw1
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 52

Assisted Solution

Rgonzo1971 earned 400 total points
ID: 38863126
Hi,

Basically, you should do your homework alone

Here is my pseudo-code
``````Diff = 0
Str = Dec2Bin(11)
for (int counter = 1; counter <= strlen(Str)-1; counter++)
{
if Mid(Str, counter, 1) <> Mid(Str, counter + 1, 1)
{
Diff++
}
}
If Diff >= 2
{
}
Else
{
}
``````
Regards
0

LVL 84

Expert Comment

ID: 38863204
int fncSpecialBinary(int n){
int l,r;
l=n<<1&~n;
r=n&~n<<1;
return(r&(l|-l));
}
0

Expert Comment

ID: 38863257
All you need is a code to search the pattern: { 1, 0, ..., 1 } with a quantity of zeros varying from 1 to n.
0

LVL 84

Accepted Solution

ozo earned 1600 total points
ID: 38863534
// further simplifying:
int fncSpecialBinary(int n){
return ~n&-n&n>>1;
}
0

Author Comment

ID: 38864635
Rgonzo1971... nope, not my homework.  If your username is any indication of your age, I am older than you and have not been in school since the 80s.  :)
But since you went there...
Your answer works good for an Introduction to Programming 101 Junior college course.
0

Expert Comment

ID: 38865419
I thought about signed signed numbers, precisely ones' complement and I wanna post some comments about accepted solution.

If we use this algorithm by ones' complement for number 4, we have something like:
``````(~4 & 11 & 4>>1) // 11 is negative value to 4 and this sentece return true
``````
To have a generic code, I wrote:
``````template<typename T>
int inline fncSpecialBinary(T n)
{
int lsb = (sizeof(n)*8)-1;
int rsb = lsb -1;

while (-1 < rsb && ( /* 1st */ !(n&(1<<lsb)) ||
/* 2nd */ ((n&(1<<lsb)) && !(n&(1<<rsb))) ||
/* 3rd */ ((n&(1<<lsb)) && (n&(1<<rsb)) && 1 == (lsb - rsb))))
{
if ( !(n&(1<<lsb)) || ((n&(1<<lsb)) && (n&(1<<lsb-1))))
lsb--;

rsb = !(n&(1<<lsb)) ? lsb - 1 : rsb - 1;
}
return (-1 != rsb ? 1 : 0);
}
``````
To call it,use:
``````std::wcout << (fncSpecialBinary<unsigned int>(num) ? L"TRUE" : L"FALSE") << std::endl;
// or
std::wcout << (fncSpecialBinary<unsigned short int>(short_number) ? L"TRUE" : L"FALSE") << std::endl;
``````
0

LVL 36

Expert Comment

ID: 38866966
@DiSalomao,

I think you are confusing your 'ones' and 'twos' complements. -n gives you the *twos* complement of n, ie. if n is 4 (and if we are talking 4-bit numbers as in your example) then -n is 12 (not 11)... and the result evaluates to false which is correct!
0

Expert Comment

ID: 38867321
Mccarl,

There is no mistakes. I have a x86 machine and for me the accepted solution works fine, too. Why ? My computer donÂ´t use ones' complement to represent negative numbers.

But, if you get the code {... return ~n&-n&n>>1;...} and compile on computers that use ones' complement to represent their negative numbers, you'll get a bug. By the way, on that kind of machines -4 (decimal) == 1011 (binay) == 11 (unsigned decimal).

I just propose my code, because it's more portable one and to justify my comments.

Thanks,
0

LVL 84

Expert Comment

ID: 38870725
The C language standard does allow for ones complement or sign/magnitude representation, although I'm not familiar with any computer architecture that's used them since the 1960's
If you are running  on such a computer, you can use
unsigned int fncSpecialBinary(unsigned int n){
return ~n&(~n+1)&n>>1;
}
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
If you are a mobile app developer and especially develop hybrid mobile apps then these 4 mistakes you must avoid for hybrid app development to be the more genuine app developer.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Starting up a Project
###### Suggested Courses
Course of the Month7 days, 22 hours left to enroll