二进制相关

258. 各位相加
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
10 1
11 2
12 3
13 4
14 5
15 6
17 8 
18 9 0
19 1
20 2
21 3
22 4
23 5
24 6

class Solution {
public:
    int addDigits(int num) {
        return (num-1)%9+1;
    }
};

讨论里面的dalao:
For base b (decimal case b = 10), the digit root of an integer is:
dr(n) = 0 if n == 0
dr(n) = (b-1) if n != 0 and n % (b-1) == 0
dr(n) = n mod (b-1) if n % (b-1) != 0
or
dr(n) = 1 + (n - 1) % 9
Note here, when n = 0, since (n - 1) % 9 = -1, the return value is zero (correct).
From the formula, we can find that the result of this problem is immanently periodic, with period (b-1).
so,一般化之后就是 1+(n-1)%(base-1) 对base进制的数n，把各个数位上的数字相加，最后得到一个一位数是多少 

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0) return false;
        bool flag=false;
        if((n&(n-1))==0)
            flag = true;
        return flag;
    }
};

判断一个数 n 是否是 3的幂 
假设存在一个N>n ，若 N 是 3的幂，且 N%n=0 , 那么n肯定是3的幂，因为 N分解因子后除了 3没有别的因子，若有的话也就不再是 3的幂了
若 把 3 换成一个非素数 k ，那么上面的结论就不成立了，因为这时候 N可以被分解为多个素因子(p1^a1*p2^a2*p3^a3...)，n也可以被分解为多个素因子(b1^c1*b2^c2...)再有 N % n =0 那么有可能是 N的部分因子把n的整除 ，自然不能说明，n是k的幂，也不能说N是k的幂
 结论： 若 N>n, 存在一个素数k 使得 N=k^p(p=0,1,3...),且 N % n = 0 ，那么 n= k^p(p=0,1,2,3..)
 反之不成立，只是一个充分不必要条件 
   3^k = MAX;
   k=log3(MAX);
   k=log(MAX)/log(3);
   3^k % n == 0

class Solution {
public:
    long long pqw(long long t,int x){
        long long ans=1;
        while(x){
            if(x&1) ans*=t;
            x>>=1;
            t =t*t;
        }
        return ans;
    }
    bool isPowerOfThree(int n) {
        if(n<=0) return false;
        int MAX = 0x7fffffff;
        int k = log(MAX)/log(3);
        long long N =pqw(3,k);
        return N % n == 0;
    }
};

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。 

class Solution {
public:
    bool isPowerOfFour(int num) {
        if(num<=0) return false;
        return (num&(num-1))==0 && num&(0x55555555);
    }
};

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数
输入：00000000000000000000000000001011
输出：3

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n){
            ++cnt;
            n&=n-1;
        }
        return cnt;
    }
};
//除K取余法
int hammingWeight(uint32_t n) {
        int ans=0;
        while(n)
        {
            ans+=n%2;
            n>>=1;
        }
        return ans;
}
//直接判断二进制最低为的数是不是1
int hammingWeight(uint32_t n) {
        int ans=0;
        while(n)
        {
            ans+=n&1;
            n>>=1;
        }
        return ans;
}

颠倒给定的 32 位无符号整数的二进制位。
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
      因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans=0;
        int i=31;
        while(i--)
        {
            ans+=n&1;  //ans |= n&1;
            ans<<=1;
            n>>=1;
        }
        return ans;
    }
};

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans=0;
        int i=32;
        while(i--)
        {
            ans<<=1;
            ans+=n&1;  //ans |= n&1;
            n>>=1;
        }
        return ans;
    }
};