Question

Problem: Write a C/C++ program to implement a function that returns 1 when an integer x contains an odd number
of 1s (in its binary representation) and 0 otherwise. You can consider x as a four byte integer, i.e. w = 32 bits.

Constraint: Your solution can use at most 12 arithmetic, bitwise, and logical operations.

Answer 1

To solve the given problem I created a function in C++ called oddBits() which takes the given no. as argument. Then based on the no. of set bits i.e. no. of 1's in the binary representation of the no. the while loop in the function updates the variable count.

Now after the while loop we check whether the count of 1's in the number is odd or even and based on that it returns 1 or 0 as output.

I have used the conditional operator in the code which is equivalent to 'if-else' block in C++. So if there is any problem understanding that part of the solution feel free to ask in the comments section.

Based on the given constraints I have come up with the following C++ code:

Code:

#include<iostream>
using namespace std;

int oddBits(int num)
{
int count=0; // initialisation of count to '0' is important
while(num!=0)
{
num&=(num-1);
count++;
}

return count%2==1?1:0; // conditional operator
}

int main()
{
int n;
cout<<"Enter no.: "; // taking the number from the user
cin>>n;
int x=oddBits(n);

cout<<x;

}

Some of the outputs based on the above code are:

As the binary representation of '3' contains only 2 1's which are even in no. and hence the output is '0'.

As the binary representation of '14' contains 3 1's which are odd in no. and hence the output is '1'.

For any doubt in code or solution do comment in the comments sections.