位運算、代碼的完整性

這篇文章主要是介紹劍指offer中的【位運算:二進位中1的個數】，【代碼的完整性:數值的整數次方】，【代碼的完整性:調整數組順序使奇數位於偶數前面】的實現。

1. 位運算:二進位中1的個數，

題目描述

輸入一個整數，輸出該數二進位表示中1的個數。其中負數用補碼表示。

解題思路

把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0。那麼一個整數的二進位表示中有多少個1，就可以進行多少次這樣的操作。很多二進位的處理都可以用這種方法。

代碼實現

        /// <summary>
        /// 新穎解法：
        /// 把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0。
        /// 那麼一個整數的二進位表示中有多少個1，就可以進行多少次這樣的操作。
        /// 很多二進位的處理都可以用這種方法。
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int NumberOf1(int n) {
            int count = 0;
            while (n != 0) {
                count++;
                n = (n - 1) & n;
            }
            return count;
        }

        /// <summary>
        /// 針對正整數(負數不會走)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int SimpleNumberOf1(int n) {
            int count = 0;
            while (n > 0) { //右移的處理，
                if ((n & 1) == 1) {
                    count++;
                }
                n = n >> 1;
            }
            return count;
        }

想入非非：擴展思維，發揮想象

1. 熟悉位運算符：& （與）、 | （或） 、 ^ （異或）、~ （反運算符）、<< 二進位左移運算符、 >> 二進位右移運算符
2. 瞭解二進位（0b），八進位，十進位，十六進位（0x）

2.代碼的完整性:數值的整數次方

題目描述

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。

解題思路

指數冪：a^n,當n是正數是a個n相乘，當n是負數是a個n相乘的倒數。

代碼實現

        public static double Pow(double baseData, int exponent)
        {
            if (baseData == 0)
            {
                return 0;
            }

            bool isPositive = exponent > 0;//是否是正數
            exponent = isPositive ? exponent : -exponent;
            double result = 1;
            for (int i = 0; i < exponent; i++)
            {
                result = result * baseData;
            }
            result = isPositive ? result : (1 / result);
            return result;
        }

3.代碼的完整性:調整數組順序使奇數位於偶數前面

題目描述

輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位於數組的前半部分，所有的偶數位於數組的後半部分，並保證奇數和奇數，偶數和偶數之間的相對位置不變。

解題思路

        public static int[] HandleArray(int[] array) {
            if (array == null) return null;
            int[] temp = new int[array.Length];
            int i = 0;
            //奇數
            foreach (var t in array) {
                if (t % 2 == 1) {
                    temp[i] = t;
                    i++;
                }
            }
            //偶數
            foreach (var t in array)
            {
                if (t % 2 == 0)
                {
                    temp[i] = t;
                    i++;
                }
            }
            return temp;
        }

下麵的是不考略相對位置，只考慮效率，上面的解題效率是2n，下麵的效率是n

        /// <summary>
        /// 不考略相對位置的
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static int[] HandleArray2(int[] array)
        {
            if (array == null) return null;

            int left = 0;
            int right = array.Length - 1;
            while (left < right)
            {
                //奇數
                while (array[left] % 2 == 1)
                {
                    left++;
                }

                //偶數
                while (left < right && array[right] % 2 == 0)
                {
                    right--;
                }

                //交換
                if (left < right)
                {
                    var temp = array[left];
                    array[left] = array[right];
                    array[right] = temp;
                }

            }
            return array;
        }