位運算和數(shù)學(xué)

pow(x,n)

double myPow(double x, int n) {
        int res=1;
        int i = n; //不能用abs
        for(; i != 0; i /= 2){
            if(i % 2 != 0){
                res *= x;
            }
            x *= x;
        }
        return n<0? 1/res :res;
    }

二進制中1的個數(shù)

n = 5（0101）時持灰，返回2盔夜，n = 15（1111）時，返回4

int BitCount2(unsigned int n)
{
    unsigned int c =0 ;
    for (c =0; n; ++c)
    {
        n &= (n -1) ; // 清除最低位的1
    }
    return c ;
}

1-n中1的次數(shù)

輸入13堤魁，輸出6
1,10,11,12,13
兩種方法喂链，一種是從1到n遍歷，每次通過對10求余數(shù)判斷整數(shù)的個位數(shù)字是不是1妥泉，大于10的除以10之后再判斷椭微。我們對每個數(shù)字都要做除法和求余運算以求出該數(shù)字中1出現(xiàn)的次數(shù)。如果輸入數(shù)字n盲链，n有O(logn)位蝇率，我們需要判斷每一位是不是1，那么時間復(fù)雜度為O(n*logn)刽沾。
第二種方法是數(shù)學(xué)之美上面提出的方法本慕，設(shè)定整數(shù)點（如1、10侧漓、100等等）作為位置點i（對應(yīng)n的各位锅尘、十位、百位等等）布蔗，分別對每個數(shù)位上有多少包含1的點進行分析藤违。

根據(jù)設(shè)定的整數(shù)位置忙菠，對n進行分割，分為兩部分纺弊，高位n/i牛欢，低位n%i
當(dāng)i表示百位，且百位對應(yīng)的數(shù)>=2,如n=31456,i=100淆游，則a=314,b=56傍睹，此時百位為1的次數(shù)有a/10+1=32（最高兩位0~31），每一次都包含100個連續(xù)的點犹菱，即共有(a/10+1)*100個點的百位為1
當(dāng)i表示百位拾稳，且百位對應(yīng)的數(shù)為1，如n=31156,i=100腊脱，則a=311,b=56访得，此時百位對應(yīng)的就是1，則共有a/10(最高兩位0-30)次是包含100個連續(xù)點陕凹，當(dāng)最高兩位為31（即a=311）悍抑，本次只對應(yīng)局部點00~56，共b+1次杜耙，所有點加起來共有（a/10*100）+(b+1)搜骡，這些點百位對應(yīng)為1
當(dāng)i表示百位记靡，且百位對應(yīng)的數(shù)為0,如n=31056,i=100团驱，則a=310,b=56，此時百位為1的次數(shù)有a/10=31（最高兩位0~30）
綜合以上三種情況寸痢，當(dāng)百位對應(yīng)0或>=2時贩幻，有(a+8)/10次包含所有100個點，還有當(dāng)百位為1(a%10==1)族壳，需要增加局部點b+1
之所以補8趣些，是因為當(dāng)百位為0，則a/10==(a+8)/10拢操，當(dāng)百位>=2，補8會產(chǎn)生進位位令境，效果等同于(a/10+1)

  int NumberOf1Between1AndN_Solution(int n)
    {
    int count = 0;
    long long i = 1;
    for(i = 1; i <= n; i *= 10)
    {
        //i表示當(dāng)前分析的是哪一個數(shù)位
        int a = n / i, b = n % i;
        count = count + (a + 8) / 10 * i + (a % 10 == 1) * (b + 1);
    }
    return count;
    }

丑數(shù)

質(zhì)因子只包含2舔庶，3，5的稱為丑數(shù);
判斷丑數(shù)的方法：除以2除到不能除為止瞧甩，然后除以3肚逸，除到不能除為止，然后除以5朦促，除到不能除為止苍鲜，最后結(jié)果玷犹，商是1歹颓，余數(shù)是0，即為丑數(shù)巍扛。

int GetUglyNumber_Solution(int index) {         
    if (index<0) return 0;        
    if (index==1) return 1;        
    vector<int>k(index);        
    k[0]=1;        
    int num2=0,num3=0,num5=0;        
    for(int i=1;i<index;++i)  {    
        k[i]=min(k[num2]*2,min(k[num3]*3,k[num5]*5));
        if(k[i]==k[num2]*2) num2++;            
        if(k[i]==k[num3]*3) num3++;
        if(k[i]==k[num5]*5) num5++;        
    }        
    return k[index-1];    
}

不用加減乘除的加法

首先看十進制是如何做的： 5+7=12撤奸，三步走
相加各位的值，不算進位矢棚，得到5 + 7 = 2（不算進位）
計算進位值府喳，得到10. 如果這一步的進位值為0，那么第一步得到的值就是最終結(jié)果兜粘。
重復(fù)上述兩步，只是相加的值變成上述兩步的得到的結(jié)果2和10剃法，得到12

相加各位的值，不算進位玄窝，得到010悍引，二進制每位相加就相當(dāng)于各位做異或操作，101^111=010
計算進位值趣斤，得到1010，相當(dāng)于各位做與操作得到101玉凯，再向左移一位得到1010联贩，(101&111)<<1。

int Add(int left, int right)
   {
       int temp;
       while(right != 0)
       {
           temp = left ^ right;                //  計算不帶進位的情況
           right = (left & right) <<1;         //  計算帶進位的情況
           left = temp;
           //  now left = 不帶進位的情況, right = 帶進位的情況
       }
       return left;
   }

構(gòu)建乘積數(shù)組

給定一個數(shù)組A[0,1,...,n-1],請構(gòu)建一個數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]盲厌。不能使用除法
思路：分兩步算吗浩，先算B[i]=A[0]A[1]...A[i-1]没隘，再算B[i]=B[i]A[i+1]...A[n-1]

public int[] multiply(int[] A) {
        if (A == null) {
            return null;
        }
        int[] B = new int[A.length];
        if (B.length == 0) {
            return B;
        }
        B[0] = 1;
        //先計算了 B[i] = A[0]*A[1]*A[2]*...*A[i-1]
        for (int i = 1; i < A.length; i++) {
            B[i] = A[i - 1] * B[i - 1];
        }
        //后部分:
        int tmp = 1;
       for (int i = A.length - 1; i >= 0; i--) {
            B[i] = tmp * B[i];
            tmp *= A[i];
        }
        return B;
    }

不用乘除右蒲，if else，for while瑰妄，計算1+2...+n

int Sum(int n)
{
  int ret = 0;
  n == 0 || (ret = Sum(n-1));
  return n + ret;
}