Improve company productivity with a Business Account.Sign Up

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

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
Asked:
kevinvw1
2 Solutions
 
Rgonzo1971Commented:
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
{
    Answer = True
}
Else
{
    Answer = False
}

Open in new window

Regards
0
 
ozoCommented:
int fncSpecialBinary(int n){
  int l,r;
  l=n<<1&~n;
  r=n&~n<<1;
  return(r&(l|-l));
}
0
 
Marcos Freitas de MoraisCommented:
All you need is a code to search the pattern: { 1, 0, ..., 1 } with a quantity of zeros varying from 1 to n.
0
What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

 
ozoCommented:
// further simplifying:
int fncSpecialBinary(int n){
   return ~n&-n&n>>1;
}
0
 
kevinvw1Author 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.
But Ozo's answer is definitely Grad School material.
0
 
Marcos Freitas de MoraisCommented:
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

Open in new window

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);
}

Open in new window

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;

Open in new window

0
 
mccarlIT 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
 
Marcos Freitas de MoraisCommented:
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.

I appreciate your attention.

Thanks,
0
 
ozoCommented:
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.

Join & Write a Comment

Featured Post

What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now