x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 437

# Formula to identify special binary numbers

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
kevinvw1
2 Solutions

Commented:
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

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

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

Commented:
// further simplifying:
int fncSpecialBinary(int n){
return ~n&-n&n>>1;
}
0

Author Commented:
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

Commented:
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

IT Business Systems Analyst / Software DeveloperCommented:
@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

Commented:
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

Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.