n >> k & 1 求数字n二进制表示下，第k位是几

lowbit操作 返回x的最后一位1
1010100就返回100，1011100000就返回100000
x & (-x)可以得到以上 等价于 x & (~x + 1)

231. 2的幂

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

注意小于0的数不是2的幂就行了

  1. class Solution {
  2. public:
  3.     bool isPowerOfTwo(int n) {
  4.         int count = 0;
  5.         if(n < 0) return false;
  6.         while(n){
  7.             n &= n - 1;
  8.             count ++;
  9.         }
  10.         return count == 1 ? true : false;
  11.     }
  12. };

剑指 Offer 15. 二进制中1的个数

难度简单85
请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

这里有两种巧妙方法： 一个是利用lowbit，不过可能会出现越界int的现象，所以要用long long进行转化 还有就是利用n =(n - 1) & n 可以把一个数的末尾1变为0 都是计算可以进行多少次这样的操作

  1. class Solution {
  2. public:
  3.     int lowbit(int x){
  4.         return x & ((long long)~x + 1);
  5.     }
  6.     int hammingWeight(uint32_t n) {
  7.         int count = 0;
  8.         while(n){
  9.             //n -= lowbit(n);
  10.             n = (n - 1) & n;
  11.             count ++;
  12.         }
  13.         return count;
  14.     }
  15. };

338. 比特位计数

难度中等592
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]

一种方法就是用lowbit的方法进行计算，不过可以使用dp的方法进行优化，效率更高一些。 为什么是+1呢，因为这是个计数

  1. class Solution {
  2. public:
  3.     int lowbit(int x){
  4.         return x & (~x + 1);
  5.     }
  6.     vector<int> countBits(int num) {
  7.         vector<int> ans = {0};
  8.         for(int i = 1; i <= num; ++ i){
  9.             ans.push_back(ans[i - lowbit(i)] + 1);
  10.         }
  11.         return ans;
  12.     }
  13. };

89. 格雷编码

难度中等266
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。

示例 1:
输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。

00 - 0
10 - 2
11 - 3
01 - 1
示例 2:
输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
给定编码总位数为_n_ 的格雷编码序列，其长度为 2。当 _n_ = 0 时，长度为 2 = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。

  1. class Solution {
  2. public:
  3.     vector<int> grayCode(int n) {
  4.         vector<int> res = {0};
  5.         int head = 1;
  6.         for(int i = 0; i < n; ++ i){
  7.             for(int j = res.size() - 1; j >= 0; -- j){
  8.                 res.push_back(head + res[j]);
  9.             }
  10.             head <<= 1;
  11.         }
  12.         return res;
  13.     }
  14. };