1
$\begingroup$

Assume that I have an ordinary number in Decmical base, now what I want to know is determining whether it has an even number of 1's in a binary base or not.and yet again I should emphasize the fact that I do not want the exact number of 1's in the binary base,just knowing if the number of 1's is even or odd.(by the way if you find a way to determine the exact number of 1's that should work as well)

Thanks in advance.

I'm new to English math so I apologize for any mistakes in the typing.(tried to be as clear as possible though :D)

Please feel free to edit the question and the tags if you wish.

$\endgroup$
5
$\begingroup$

We can define a recursive function that will return $0$ for an even number of binary $1$s and $1$ for an odd number of binary $1$s using these facts:

$2k$ has the same number of binary $1$s as $k$ has ($2k$ is obtained from $k$ by appending a $0$ to the binary representation of $k$).

$2k+1$ has one more binary $1$ than $k$ has ($2k+1$ is obtained from $k$ by appending a $1$ to the binary representation of $k$).

Our function can then be $f(0)=0$; $f(2k)=f(k)$; and $f(2k+1)=1-f(k)$. Then $f$ will return $0$ for an even number of binary ones, and $1$ for an odd number of binary $1$s.

$\endgroup$
  • $\begingroup$ pretty nice! thank you $\endgroup$ – FuriousMathematician Sep 18 '14 at 16:00
  • $\begingroup$ You're welcome. By the way, if you wanted to count binary $1$s, you could just change $f(2k+1)=1-f(k)$ in the function to $f(2k+1)=1+f(k)$ $\endgroup$ – paw88789 Sep 18 '14 at 16:02
  • $\begingroup$ your answer was phenomenal,yet since I want to use this way in programming -as you may know- defining and using recursive function is quite time consuming.I'd like a quicker way which is proper to be used in my program.Thanks again! $\endgroup$ – FuriousMathematician Sep 18 '14 at 16:23
  • $\begingroup$ In that case, keep dividing by $2$. Each time you get a remainder of $1$ you are getting another binary $1$. Each time you get a remainder of $0$ you are getting a binary $0$. $\endgroup$ – paw88789 Sep 18 '14 at 16:39
  • $\begingroup$ Thanks for the reply.This is exactly what I've been trying to use in the programming,I was looking for a way faster than that.I couldn't get anywhere with this but my idea was that it is pretty easy to understand how many digits a decimal number has in binary base (using logarithm of course) then if there was a way to separate zeroes from ones I would have my problem solved.Do you happen to have a idea about that? $\endgroup$ – FuriousMathematician Sep 18 '14 at 17:07
0
$\begingroup$

As far as I know there is only one binary base for numeric representation. In this base, it is very easy to count the number of $1$ digits: take the number logically AND'd (&) with $1$, then subtract this result from the number and divide by $2$, then add this result to the total, repeating until the number is $0$.

In pseudocode,

num = 71
Res=0
While (num > 0) {
  current = num & 1
  Res = Res + current
  num = (num - current) / 2
}
Return Res

Supposing that you wish to modify this to look for a specific digit in another base, you would change the above as current = num % mod and Res = Res + (current == chosenDigit ? 1 : 0) and num = (num - current) / mod

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.