算法

二进制的总结

Posted by Liao on 2020-02-25

LeetCode 求二进制数中1的个数

这是一种更高效的思路，把整数减1，再与原来的数做与运算，会把原来的二进制数最右边的1去掉。计算有多少次去掉1的操作，即可知道1的个数。

n = n & (n-1) 

1
2
3
4
5
6
7
8
9
int hammingWeight(uint32_t n) {
       int cnt = 0;
       while(n)
       {
           cnt++;
           n = n & (n-1);
       }
       return cnt;
   }

LeetCode 2的幂

输入一个数，判断是不是2的幂次方

2的幂次方，只要满足n>0 && (n & (n-1)) == 0即可。

1
2
3
4
5
6
bool isPowerOfTwo(int n) {
       if(n > 0 && (n & (n-1)) == 0)
           return true;
       else
           return false;
   }

汉明距离

汉明距离是指两个数字对应二进制位不同的位置的数目。如1 (0 0 0 1)　4 (0 1 0 0)，第1,3位不同

1
2
3
4
5
6
7
8
9
int hammingDistance(int x, int y) {
        int res = 0;
        int n = x ^ y;
        while(n){
            n = n & (n-1);
            res++;
        }
        return res;
    }

字母大小写全排列

1
2
3

char c;
c ^= 1<<5;

ASCII 码中 a为97，A为65，中间差了32，而2^5^=32，因此左移5位可以表示大小写之间的转换。如Leetcode 字母大小写全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<string>ans;
    vector<string> letterCasePermutation(string s) {
        backtracking(s, 0);
        return ans;
    }

    void backtracking(string s, int idx) {
        ans.push_back(s);
        for(int i = idx; i < s.size(); i++) {
            if(s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z') {
                s[i] ^= 1<<5;  // 大小写字母切换的位运算写法
                backtracking(s, i + 1);
                s[i] ^= 1<<5; 
            }
        }

    }
};
FEATURED TAGS
算法
FRIENDS