Bit Magic !

This post contains a set of frequently asked interview/written questions (with their answers) which require some sort of interesting bit manipulations.

1] Is my system Big-Endian or Little-Endian ?
So to answer this question, we’ll first understand what the terms actually mean. Now, Little Endian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address. That is, in a Little-Endian the little end comes first.

Below are a couple of ways to determine if the data representation in your system in Big-Endian or Little-Endian. In both approaches, what we attempt to find out is which end comes first. If the LSB comes first then the representation is Little-Endian else it is Big-Endian.

union nn{
	int a;
	unsigned char b[4];
};
int main()
{
	int n = 1;
	if(*((unsigned char *)(&n)) == 1)
		printf("Little Endian\n");
	else
		printf("Big Endian\n");

	union nn nd;
	nd.a = 1;
	if(nd.b[0] == 1)
		printf("Little Endian\n");
	else
		printf("Big Endian\n");
}

2] How to get the reverse the sign of an integer ?

void reversesign(int &num)
{
  num = ~num+1
}

3] How to get the absolute value of an integer ?

void absolute(int &num)
{
  int mask = num>>31; //If the number is negative, all bits go 1, else all bits go 0
  num = ((num^mask)+mask&1); //If its positive -> Do nothing, else it is equivalent to 2s complement.
}

4] Rotate an integer n by d.

void Rotate(int &n, int d)
{
  #define INT_SIZE 32
  n =  (n>>d)|(n<<INT_SIZE-d);
}

5] Reverse the bits of an integer.

int Reverse(int rev)
{
  int i = 0, ans = 0;
  while(i<32)
  {
	ans <<= 1;
	ans |= ((rev>>i) & 1);
	i++;
  }
  return ans;
}

6] Unset all bits except the rightmost bit.

void UnsetBits(int &Rightmost){
      Rightmost = (Rightmost&-Rightmost);
}

7] Find the smallest power of 2, greater than Num.

int FindNextPowerOf2(int Num)
{
  while((Num&(Num-1))!=0)
	Num &= (Num-1);
  Num <<= 1;
  return Num;
}

8] Write a macro for setting the j^th bit of i equal to k

#define SETJBITK(i, j, k)  i ^= i>>j&1 == k ? 0:1<<j

For greater clarity

#define SETJBITK(i, j, k)  i ^= (i>>j&1 == k ) ? 0:(1<<j) //Is the current bit same as the bit to be set, if it is xor with 0, else flip the bit by xoring with 1<<j.

9] Find the position of MSB

int FindPositionOfMSB(int i)
{
	if(i == 0)
		return 0;
	int left = 31, right = 0, center;
	while(left>right)
	{
		center = (left+right)/2;
		if((i>>left)&1 == 1)
			return left;
		if((i>>center)&1 == 1)
		{
			right = center;
			left -=1;
		}
		else{
			left = center-1;
		}
	}
	return left;
}

10] Find the number of set bits

int FindNumberOfLeadingBits(int i)
{
	int n = 31;
	while(n>=0 && (i>>n)&1!=0)
		n--;
	return 31-n;
}

11] Find the number of Leading bits

int NumberOfSetBits(int i)
{
	int count = 0;
	while(i!=0)
	{
		i&=(i-1);
		count++;
	}
	return count;
}

12] Is the number a power of 2

bool IsPowerOf2(int i)
{
	return (i!=0 && (i=i&(i-1))==0);
}

13] In an array of numbers, each number appear exactly twice except one. Find the non-repeating number.

int FindTheNonRepeatingNumber(vector<int> &Vec)
{
	int a = 0, sz = Vec.size();
	for(int i=0;i<sz;i++)
		a^=Vec[i];
	return a;
}

14] Write a function which returns true if a given number is 1 less than power of 2.

bool IsOneLessThanPowerOf2(int n)
{
   return (n&(n+1)) == 0?true:false;
}

15] Implement x ? y : z as a function: int cond(int x, int y, int z); using only ~, !, ^, &, +, |, <>. The solution must be a single line solution with no extra variables.

int cond(int x, int y, int z)
{
	return (((!(x)<<31)>>31)&z)|((~((!(x)<<31)>>31))&y);
}

Advertisement