剑指offer常见题 - 位运算问题（二）

位运算相关算法

二叉树相关性质：
计算机中的数在内存中都是以二进制形式进行存储的 ，而位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
需要掌握的内容：

1. 运算符的优先级
2. 位运算符的运算律’
3. 位运算高级操作
4. 负数的位运算

题目

二进制中1的个数

典型题例：

输入一个 32 位整数，输出该数二进制表示中 1 的个数。

示例 ：

输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。

输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
      一共有31个1。
1
2
3
4
5
6
7
8

思路
核心：

代码：

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        unsigned int un = n; 
        while (un) res += un & 1, un >>= 1;
        return res;
    }
};
1
2
3
4
5
6
7
8
9

不用加减乘除做加法

典型题例：

写一个函数，求两个整数之和，要求在函数体内不得使用 ＋、－、×、÷ 四则运算符号。

示例 ：

输入：num1 = 1 , num2 = 2

输出：3
1
2
3

思路

代码：

class Solution {
public:
    int add(int num1, int num2){

        while(num2){

            int sum = num1^num2;            //不进位加法
            int carry = (num1 & num2) << 1;  //进位
            num1 = sum;                     //更新num1 
            num2 = carry;                   //更新num2
        }

        return num1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习