Solved

Formula to identify special binary numbers

Posted on 2013-02-06
9
425 Views
Last Modified: 2013-02-09
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
Comment
Question by:kevinvw1
9 Comments
 
LVL 48

Assisted Solution

by:Rgonzo1971
Rgonzo1971 earned 100 total points
Comment Utility
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
 
LVL 84

Expert Comment

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

Expert Comment

by:Marcos Freitas de Morais
Comment Utility
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

by:
ozo earned 400 total points
Comment Utility
// further simplifying:
int fncSpecialBinary(int n){
   return ~n&-n&n>>1;
}
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:kevinvw1
Comment Utility
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
 

Expert Comment

by:Marcos Freitas de Morais
Comment Utility
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
 
LVL 35

Expert Comment

by:mccarl
Comment Utility
@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

by:Marcos Freitas de Morais
Comment Utility
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
 
LVL 84

Expert Comment

by:ozo
Comment Utility
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

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now