备赛蓝桥杯--算法题目(3)
1. 2的幂
231. 2 的幂 - 力扣（LeetCode）
class Solution {
public:bool isPowerOfTwo(int n) {return n>0&&n==(n&(-n));}
};2. 3的幂
326. 3 的幂 - 力扣（LeetCode）
class Solution {
public:bool isPowerOfThree(int n) {return n>0&&1162261467%n==0;}
};3. 数字范围按位与
201. 数字范围按位与 - 力扣（LeetCode）
class Solution {
public:int rangeBitwiseAnd(int left, int right) {while(left<right){right-=right&(-right);}return right;}
};4. 颠倒二进制位
190. 颠倒二进制位 - 力扣（LeetCode）
class Solution {
public:uint32_t reverseBits(uint32_t n) {n=(n&0xaaaaaaaa)>>1|(n&0x55555555)<<1;n=(n&0xcccccccc)>>2|(n&0x33333333)<<2;n=(n&0xf0f0f0f0)>>4|(n&0x0f0f0f0f)<<4;n=(n&0xff00ff00)>>8|(n&0x00ff00ff)<<8;n=n>>16|n<<16;return n;}
};5. 汉明距离
461. 汉明距离 - 力扣（LeetCode）
class Solution {
public:int hammingDistance(int x, int y) {int n=x^y;n = (n & 0x55555555) + ((n >> 1) & 0x55555555);n = (n & 0x33333333) + ((n >> 2) & 0x33333333);n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);return n;}
};6. 设计位集
2166. 设计位集 - 力扣（LeetCode）
class Bitset {
private:std::vector<int> set;const int size;int zeros;int ones;bool reverse;public:Bitset(int n) : size(n), zeros(n), ones(0), reverse(false) {set.resize((n + 31) / 32, 0);}void fix(int i) {int index = i / 32;int bit = i % 32;if (!reverse) {if ((set[index] & (1 << bit)) == 0) {zeros--;ones++;set[index] |= (1 << bit);}} else {if ((set[index] & (1 << bit)) != 0) {zeros--;ones++;set[index] ^= (1 << bit);}}}void unfix(int i) {int index = i / 32;int bit = i % 32;if (!reverse) {if ((set[index] & (1 << bit)) != 0) {ones--;zeros++;set[index] ^= (1 << bit);}} else {if ((set[index] & (1 << bit)) == 0) {ones--;zeros++;set[index] |= (1 << bit);}}}void flip() {reverse = !reverse;std::swap(zeros, ones);}bool all() const {return ones == size;}bool one() const {return ones > 0;}int count() const {return ones;}std::string toString() const {std::string result;for (int k = 0, i = 0; i < size; k++) {int number = set[k];for (int j = 0; j < 32 && i < size; j++, i++) {int status = (number >> j) & 1;status ^= reverse ? 1 : 0;result += std::to_string(status);}}return result;}
};7. 两数相除
29. 两数相除 - 力扣（LeetCode）
class Solution {
public:
static const int MIN =INT_MIN;int divide(int a, int b) {if(a==MIN&&b==MIN){return 1;}if(a!=MIN&&b!=MIN){return div(a,b);}if(b==MIN){return 0;}if(b==neg(1)){return INT_MAX;}a=add(a,b<0?neg(b):b);int ans=div(a,b);int offset=b<0?1:-1;return add(ans,offset);}int div(int a, int b) {int x = a < 0 ? neg(a) : a;int y = b < 0 ? neg(b) : b;int ans = 0;for (int i = 30; i >= 0; i = minus(i, 1)) {if ((x >> i) >= y) {ans |= (1 << i);x = minus(x, y << i);}}return a < 0 ^ b < 0 ? neg(ans) : ans;}int add(int a,int b){int ans=a;while(b!=0){ans=a^b;b=(a&b)<<1;a=ans;}return ans;}int minus(int a,int b){return add(a,neg(b));}int neg(int n){return add(~n,1);}int multiply(int a, int b) {int ans = 0;while (b != 0) {if ((b & 1) != 0) {ans = add(ans, a);}a <<= 1;b >>= 1;}return ans;}
};