LeetCode.231.191.190.136(位运算)

231.2-的幂

class Solution {
  public:
    bool isPowerOfTwo(int n) {
        /*for (; n % 2 == 0 && n != 0; n /= 2) {
        }
        return n == 1 ? true : false;*/
        // 1108/1108 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 71.69 % of cpp submissions (5.8 MB)

        //???位运算???
        // return (n > 0) && (n & -n) == n;
        // 1108/1108 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 75.22 % of cpp submissions (5.7 MB)
        // n为00001000(2)的话，-n(补码)为11111000(2)按位与得00001000

        return (n > 0) && (1 << 31) % n == 0;
        //-2^31 <= n <= 2^31 - 1
        // 1108/1108 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 87.87 % of cpp submissions (5.7 MB)
        //<< 左移>> 右移 (1 << 31)为2^31
    }
};

191.位-1-的个数

class Solution {
  public:
    int hammingWeight(uint32_t n) {
        /*int sum = 0;
        for (int i = 0; i < 32; i++, n /= 2)
            sum += (n % 2);
        return sum;*/
        // 601/601 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 58.09 % of cpp submissions (5.9 MB)
        int sum = 0;
        while (n) {
            sum += n % 2;
            n >>= 1;
        }
        return sum;
        // 601/601 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 98.73 % of cpp submissions (5.7 MB)
        //这个平均更快
    }
};

190.颠倒二进制位

class Solution {
  public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t m = 0;
        for (int i = 0; i < 32; i++) {
            m <<= 1;
            m += n % 2;
            n >>= 1;
        }
        return m;
        // 600/600 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 94.11 % of cpp submissions (5.7 MB)
        // https://blog.csdn.net/Tach1banA/article/details/120166223 Integer.reverse()的源码更加精简
    }
};

136.只出现一次的数字

class Solution {
  public:
    int singleNumber(vector<int> &nums) {
        /*int Max = INT_MIN, Min = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            Max = max(nums[i], Max);
            Min = min(nums[i], Min);
        }
        vector<int> temp(Max - Min + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            temp[nums[i] - Min]++;
        }
        for (int i = 0; i < temp.size(); i++) {
            if (temp[i] == 1)
                return i + Min;
        }
        return 0;*/
        // 61/61 cases passed (16 ms)
        // Your runtime beats 67.63 % of cpp submissions
        // Your memory usage beats 12.22 % of cpp submissions (17.3 MB)
        //哈希暴力解

        //想到了异或，但没想到异或是可以有交换律的==
        // a ^ b ^ c <=> a ^ c ^ b
        //搞了半天就是为了解决这个问题，没想到不用解决 心态崩了
        for (int i = nums.size() - 2; i >= 0; i--) {
            nums[i] ^= nums[i + 1];
        }
        return nums[0];
        // 61/61 cases passed (16 ms)
        // Your runtime beats 67.63 % of cpp submissions
        // Your memory usage beats 99.18 % of cpp submissions (16.3 MB)
    }
};