Sunday, 19 June 2016
INTRODUCTION
Set bits means the bits that are high i.e. the bits which are set to '1'.
For example:Suppose we enter '10',its binary representation is '1010',so no. of set bits in '10' are '2'.
Here we'll be discussing following two approaches -:
1.Simple Approach
If applying & operation results 0 =>LSB is 0.
If applying & operation results 1 =>LSB is 1.
For example:Let us suppose we enter 10,its binary representation is 1010(Let us take 4 bits for understanding,computer usually represents a number as 32-bit binary in memory).
Let us help you-:
1.Mark the first rightmost set bit.
2.Toggle each bit including the rightmost set bit while moving from right to left direction(from LSB to MSB) until you reach the marked point.
3.The resulting bits are the binary representation of number-1.
FOR EXAMPLE....
For example:Let us suppose we enter 10,its binary representation is 1010(Let us take 4 bits for understanding,computer usually represents a number as 32-bit binary in memory).
1.Applying '&' operation, 1 0 1 0 & 0 0 0 1=0 0 0 0 (Bit wise operation ),since we get 0=>count=0.
2.Right shift number by one,1 0 1 0 >> 1 = 0 1 0 1.
3.Applying '&' operation, 0 1 0 1 & 0 0 0 1 = 0 0 0 1(Bit wise operation),since we get 1=>count=0+1=1.
4.Right shift number by one,0 1 0 1 >> 1 = 0 0 1 0.
5.Applying '&' operation, 0 0 1 0 & 0 0 0 1 = 0 0 0 0(Bit wise operation ),since we get 0=>count=1+0=1.
6. Right shift number by one, 0 0 1 0 >> 1 = 0 0 0 1.
7.Applying '&' operation, 0 0 0 1 & 0 0 0 1 = 0 0 0 1(Bit wise operation ),since we get 1=>count=1+1=2.
8.Right shift number by one, 0 0 0 1 >> 1 = 0 0 0 0.
9.Applying '&' operation, 0 0 0 0 & 0 0 0 1 = 0 0 0 0(Bit wise operation ),since we get 0=>count=2+0=2.
10.Since number is reduced to 0,we'll exit from loop.
2.Brian Kernighans Approach
The idea is to subtract '1' from the number and performing bit wise '&' operation thereby.Now the question is what would subtraction get us,the answer is really simple.Observe the resulting pattern of bits and compare the same with original number.Let us help you-:
1.Mark the first rightmost set bit.
2.Toggle each bit including the rightmost set bit while moving from right to left direction(from LSB to MSB) until you reach the marked point.
3.The resulting bits are the binary representation of number-1.
FOR EXAMPLE....
![]() |
Example |
Let us suppose we enter 15,its binary representation => 1 1 1 1
1.Now 15-1=14,its binary representation=>1 1 1 0.
2.Now 15&14 i.e. 1 1 1 1 & 1 1 1 0 = 1 1 1 0(14),count=0+1=1.
3.Now 14-1=13,its binary representation=>1 1 0 1.
4.Now 14&13 i.e. 1 1 1 0 & 1 1 0 1 = 1 1 0 0(12),count=1+1=2.
5.Now 12-1=11,its binary representation=>1011.
6.Now 12&11 i.e. 1 1 0 0 & 1 0 1 1 =1 0 0 0(8),count=2+1=3.
7.Now 8-1=7,its binary representation=>0 1 1 1.
8.Now 8&7 i.e. 1 0 0 0 & 0 1 1 1=0 0 0 0,count=3+1=4.
9.Now since the number is 0,end the iteration.
10.Return.
SOURCE CODE
#include<stdio.h>
unsigned int SimpleApproach(unsigned int cs) // Complexity Theta(log(n))
{
unsigned int count=0;
while(cs)
{
count+=cs&1;
cs>>=1;
}
return count;
}
unsigned int BrianKernighans(unsigned int cs) // Complexity O(log(n))
{
unsigned int count=0;
while(cs)
{
cs&=(cs-1);
count++;
}
return count;
}
void main()
{
unsigned int cs,passion,choice;
while(1)
{
printf("\nEnter 1 for execution through simple approach\n");
printf("Enter 2 for execution through Brian Kernighan's approach\n");
printf("Enter 3 for exiting the execution\n");
printf("Enter your choice: ");
scanf("%u",&choice);
switch(choice)
{
case 1:
cs,passion=0;
printf("Enter the number of which you want to calculate set bits for: ");
scanf("%d",&cs);
passion=SimpleApproach(cs);
printf("\nNo. of set bits are %d",passion);
break;
case 2:
cs,passion=0;
printf("Enter the number of which you want to calculate set bits for: ");
scanf("%d",&cs);
passion=BrianKernighans(cs);
printf("\nNo. of set bits are %d",passion);
break;
case 3:
exit(1);
default:
printf("Wrong Choice");
}
}
}
Output:
![]() |
OUTPUT |
Subscribe to:
Post Comments (Atom)
Search
Popular Posts
-
Troubleshooting Cisco VPN client Before starting troubleshooting, Let us see what VPN is and what it requires to perform its intended f...
-
Evolution-Mobile Phones With the development of portable technology,wireless communication has so evolved that (According to the announce...
-
File Versioning C# File versioning, saving file with unique file name in c# File versioning allows a user to have several versions of ...
-
Text Box Hint in c# Windows Form Application Text Box Hint in c# Windows Form Application While developing a windows form applicat...
-
Unable to set the Freeze Panes property of Window Class C# It is generally easy to resolve the compile time errors because the reason fo...
0 comments:
Post a Comment