# Determine whether a number has an even number of 1's or not in a binary base

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)

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.

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.

• pretty nice! thank you – FuriousMathematician Sep 18 '14 at 16:00
• 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)$ – paw88789 Sep 18 '14 at 16:02
• 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! – FuriousMathematician Sep 18 '14 at 16:23
• 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$. – paw88789 Sep 18 '14 at 16:39
• 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? – FuriousMathematician Sep 18 '14 at 17:07

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