suman microsoft bit manipulation

Question 1	Find the given value is power of 2 or not
Solution:	/// <summary>         /// Find if number is in power of two         /// https://www.youtube.com/watch?v=lTxU9O-dzFc&index=4&list=PLTZbNwgO5ebrgkdJoiTU7FFuG8ThiQqmA   /// Power of 2 has a pattern where you will get kth bit from right as 1.  /// for eg: 2 pow 4 = 16 so value is 00010000 here you can see the 4th bit (start from 0th) from        right is 1  /// and When you say (2 pow 4 ) - 1 = 15 so value is 00001111 here you can see all bits are 1 before      kth position /// so When ypu do ANDing between (num) and (num-1), the value will will 0 if its in power of 2.             /// </summary>         /// <param name="num"></param>         /// <returns></returns>         public static bool IsPowerOfTwo(int num)         {             if (num == 0)                 return false;               return ((num & (num - 1)) == 0);         }
Problem 2	/// <summary>         /// count number of sign bits         /// eg : "10010", output : 2         /// </summary>         /// <param name="num"></param>         /// <returns></returns>         public static uint GetCountofSetBits(int num)         {             uint count = 0;             if (num == 0)                 return 0;               while (num != 0)             {                 if (1 == (num & 1))                 {                     count++;                 }                 num = num >> 1;             }               return count;         }
Problem 3	/// <summary>         /// if even number of 1's then True         /// </summary>         /// <param name="num"></param>         /// <returns></returns>         public static bool ComputeParity(int num)         {             // Get count of 1's bits             uint count = GetCountofSetBits(num);                         // if count is divisable by 2 then there is even number of 1's             return 0 == count % 2;         }
Problem 4	/// <summary>         /// Check how many bits has different value         /// eg : A= 1100, B=0101, Answer= 2 because 1st and 4th bit is different         /// Logic : Do the XOR of both number wherever the bit is diff you will Get 1         /// then count the number of 1's         /// </summary>         /// <param name="num1"></param>         /// <param name="num2"></param>         /// <returns></returns>         public static uint CountBitsToFlip(int num1, int num2)         {             return GetCountofSetBits(num1 ^ num2);         }
Problem 5	/// <summary>         /// check if both number has same sign (+ or -)         /// if both numbers has same Sign then Xor will return 0 (+ve number) else 1 (-ve number)         /// </summary>         /// <param name="num1"></param>         /// <param name="num2"></param>         /// <returns></returns>         public static bool HaveSameMagnitude(int num1, int num2)         {             return ((num1 ^ num2) > 0);         }
Problem 6	/// <summary>         /// A magic number is defined as a number which can be expressed as a power of 5 or sum of unique powers of 5.          /// First few magic numbers are 5, 25, 30(5 + 25), 125, 130(125 + 5),          /// eg : Input : 2, output : 25        Input: 5, Output: 130         /// If we notice carefully the magic numbers can be represented as 001, 010, 011, 100, 101, 110 etc,         /// where 001 is 0*pow(5,3) + 0*pow(5,2) + 1*pow(5,1).          /// So basically we need to add powers of 5 for each bit set in given integer n.         /// </summary>         /// <param name="n"></param>         /// <returns></returns>         public static int FindMagicNumber(int n)         {             int pow = 1, ans = 0;             // Go through every bit of n             while(n > 0)             {                 pow = pow * 5;                   // If last bit of n is set                 if((n & 1) == 1)                     ans += pow;                   // proceed to next bit                 n = n >> 1; // n = n/2;             }               return ans;         }
Problem 7	/// <summary>         /// Add two numbers without using arithmetic operators         /// Sum of two bits can be obtained by performing XOR (^) of the two bits.          /// Carry bit can be obtained by performing AND (&) of two bits.         /// </summary>         /// <param name="x"></param>         /// <param name="y"></param>         /// <returns></returns>         public static int Add(int x, int y)         {             while (y != 0)             {                 // carry now contains common set bits of x and y                 int carry = x & y;                                  // Sum of bits of x and y where at least one of the bits is not set                 x = x ^ y;                                  // Carry is shifted by one so that adding it to x gives the required sum                 y = carry << 1;             }               return x;         }
Problem 8	/// <summary>         /// Subtract two numbers without using arithmetic operators         /// https://en.wikipedia.org/wiki/Subtractor          /// </summary>         /// <param name="x"></param>         /// <param name="y"></param>         /// <returns></returns>         public static int Subtract(int x, int y)         {             while (y != 0)             {                 // borrow contains common set bits of y and unset bits of x                 int borrow = (~x) & y;                   // Subtraction of bits of x and y where at least one of the bits is not set                 x = x ^ y;                   // borrow is shifted by one so that subtracting it from x gives the required sum                 y = borrow << 1;             }               return x;         }
Problem 9	/// <summary>  /// Given a number n and a value k, turn of the k’th bit in n.   /// Input:  n = 15, k = 2 : output : 13  /// The idea is to use bitwise <<, & and ~ operators. Using expression "~(1 << (k - 1))“,   /// we get a number which has all bits set, except the k’th bit.   /// If we do bitwise & of this expression with n,   /// we get a number which has all bits same as n except the k’th bit which is 0.          /// </summary>         /// <param name="n"></param>         /// <param name="k"></param>         /// <returns></returns>         public static int TurnOffBit(int n, int k)         {             // k must be greater than 0             if (k <= 0) return n;             // Do & of n with a number with all set bits except             // the k'th bit             return (n & ~(1 << (k - 1)));         }
Problem 10	/// <summary>  /// Check if a number is multiple of 9 using bitwise operators         /// </summary>         /// <param name="n"></param>         /// <returns></returns>         public static bool IsDivideBy9(int n)         {             if (n == 0 || n == 9)                 return true;               if (n < 9)                 return false;      // If n is greater than 9, then recur for [floor(n/9) - n%8]             return IsDivideBy9((n >> 3) - (n & 7));         }
Problem 11	/// <summary> /// How to swap two numbers without using a temporary variable? /// The bitwise XOR operator can be used to swap two variables         /// </summary>         /// <param name="x"></param>         /// <param name="y"></param>         public static void Swap(int x, int y)         {         Console.WriteLine("Before Swap X= {0}, Y = {1}", x, y);               x = x ^ y;             y = x ^ y;             x = x ^ y;           Console.WriteLine("After Swap X= {0}, Y = {1}", x, y);         }
Problem 12	/// <summary>         /// Given a number having only one ‘1’ and all other ’0’s in its binary representation,          /// find position of the only set bit.         /// The idea is to start from rightmost bit and one by one check value of every bit.          /// Following is detailed algorithm.         /// 1) If number is power of two then and then only its binary representation contains only one ‘1’.          ///   That’s why check whether given number is power of 2 or not. If given number is not power of 2,          ///   then print error message and exit.         /// 2) Initialize two variables; i = 1 (for looping) and pos = 1 (to find position of set bit)         /// 3) Inside loop, do bitwise AND of i and number ‘N’. If value of this operation is true,          ///    then “pos” bit is set, so break the loop and return position.          ///    Otherwise, increment “pos” by 1 and left shift i by 1 and repeat the procedure.          /// </summary>         /// <param name="n"></param>         /// <returns></returns>         public static int FindPosition(int n)         {             if (!IsPowerOfTwo(n))                 return -1;               int pos = 1, i = 1;      // Iterate through bits of n till we find a set bit    // i&n will be non-zero only when 'i' and 'n' have a set bit             // at same position             while (i != n)             {              // Unset current bit and set the next bit in 'i'                 i = i << 1;                   pos++;             }               return pos;         }