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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

Approach:

From a starting state of 0 (an even number of 1s) and a number, iterate through the sequence of bits in the number's binary form. The order is inconsequential (whether from the least significant bit or the reverse). For each bit compute the next state by XOR'g the current bit with the current state. The final value of state is the result (0 for even and 1 for odd).

|state |next bit in sequence|XOR gives new state|
|------|--------------------|-------------------|
|0     |0                   |0                  |
|0     |1                   |1                  |
|1     |0                   |1                  |
|1     |1                   |0                  |

Worked examples:

Example 1

The number 5 has binary form 101. Starting state is 0. Three XOR operations are performed (one for each bit in 101):

|step|current state|current bit|new state|
|----|-------------|-----------|---------|
|1   |0            |1          |1        |
|2   |1            |0          |1        |
|3   |1            |1          |0(result)|

Result = 0 (even)

Example 2

The number 7 has binary form 111. Starting state is 0. Three XOR operations are performed (one for each bit in 111):

|step|current state|current bit|new state|
|----|-------------|-----------|---------|
|1   |0            |1          |1        |
|2   |1            |1          |0        |
|3   |0            |1          |1(result)|

Result = 1 (odd)