关于位运算的题目

关于位运算的题目

Tans 1,220 2022-03-28

1. 剑指 Offer 65. 不用加减乘除做加法

写个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
输入: a = 1, b = 1
输出: 2

思路

显然,这道题是想让我们用位运算进行实现。注意到两数相加就是进位和本位相加,用carry表示进位,用curb表示本位,那么有:

carry=(a \\& b)<<1

curb=(ab)curb=(a\wedge b)

然后就有两种方式进行计算了:

  1. 递归
class Solution {
public:
   int add(int a, int b) {
     if(b==0) return a;
     return add((a ^ b), (unsigned int)(a & b) << 1);
   }
};
  1. 非递归
class Solution {
public:
    int add(int a, int b) {
      while(b != 0){
        int c = (unsigned int)(a & b) << 1;
        a = (a ^ b);
        b = c;
      }
      return a;
    }
};

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

给定一个非负整数 n ,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组。

思路

很容易想到O(nlogn)O(n*logn)的做法,这里需要O(n)O(n)的算法

class Solution {
public:
    vector<int> countBits(int n) {
      // int ans = 0;
      vector<int> ans(n+1);
      for(int i= 1; i <= n; i++){
      	//ans[i] = ans[i&(i-1)] + 1; //最低设置有效位
        ans[i] = ans[i >> 1] + (i & 1); //最低位
      }
      return ans;

    }
};