Programs on Bit Manipulation

Swap adjacent bits of an unsigned integer

unsigned int swap_adjacent_bit(unsigned int num)

{

    unsigned int even_mask = 0xAAAAAAAA;

    unsigned int odd_mask = 0x55555555;

    return (   ((num & even_mask)>>1) | ((num & odd_mask)<<1) );

}
TC = O(1)
SC = O(1)

or

unsigned int swapAdjacent(unsigned int number)
{
return ((0X55555555&number)<<1)||((number&0xaaaaaaaa)>>1);

}
TC = O(1)
SC = O(1)

Add two numbers without using arithmetic operators

int add(int m,int n)

{

int x;

while(n)

{

x=m|n;

n=(m^n)<<1;

m=x;

}

return x;

}
TC = O(log n)
SC = O(1)

 or 

int add(int m,int n)

{

return (m&n)?add((m&n)<<1,m^n):m^n;

}
TC = O(log n)
SC = O(log n)

Counting the number of set bits in a number

int cunt_bits(int n)

{

Int res=0,a[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}

while(n)

{

res=res+a[n%16];

n=n>>4;

}

return res;

}

TC = Θ(n)
SC = O(1)

OR

int count_bits(int n)

{

int count=0;

while(n)

{

n=n&(n-1);// resets the right most set bit to zero 

count++;

}

}

TC = O(log n) or Θ(number of set bits)
SC = O(1)

How to find whether the number is power of two or not

int powof2(int number)

{

return !(number&(number-1))

}

 All the elements in an array of size n are repeated even number of times except one find the number that is repeated odd number of times

int findodd(int a[],int n)

{

int i,j=1,res=0,res1=0,res2=0;

for(i=0;i<n;i++)

{

res=res^a[i];

}

return res;

}

TC = Θ(n)
SC = O(1)

Given a number how to find it is divisible by 3 or not without using the modulo operator (It is good if you doesn't use multiplication & division operator also)

uint divisibleby3(uint number)

{

if(number<3)

return !number;

uint odd=0x55555555,even=0xaaaaaaaa;

odd= count(odd&number);

even= count(even&number);

if(odd>even)

return divisibleby3(odd-even);

return divisibleby3(even-odd);

}

uint count(uint number)

{

if(number==0)

return 0;

return 1+count(number&(number-1));

}