Write a function that takes an unsigned integer and returns the number of 1 bits it contains.
Example:
The 32-bit integer 11 has binary representation 00000000000000000000000000001011, so the output should be 3.
Approach: The efficient method is to use an unsigned number and keep left shifting it 32 times and keeping the ones count if a one is found at the current bit position.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include<iostream> using namespace std; int num1Bits(unsigned int a){ if(a <= 0){ return 0; } int count = 0; while(a != 0){ if(a%2 == 1){ count++; } a = a >> 1; } return count; } int num1BitsEfficient(unsigned int A){ int count = 0; unsigned int bit = 1; for(int i = 0; i <= 32; i++){ if(bit & A){ count++; } bit = bit << 1; } return count; } int main(){ unsigned int a = 11; cout << num1Bits(a) << endl; cout << num1BitsEfficient(a) << endl; return 0; } |
I did have done it like this:
ReplyDelete# include
using namespace std;
int f(int a)
{ int x,y,n=0;
x=a;
y=x;
while (y>0)
{ if((y%2)==1)
{ n++;
y=y/2;
}
else
{ y=y/2;}
}
cout<<"It has "<<n<<" number of '1s' ( High) bits in its binary value<<endl;
}
int main()
{ int I;
cout<<"Enter a unsigned integer ";
f(i);
return 0;
}
I notice that you have implemented the first version of the solution as a right shift(>>) is nothing but division by 2 but at one of the online judges it was not accepted as the solution, may be they were expecting us to use the unsigned property.
Delete