位运算相关算法
二叉树相关性质：
计算机中的数在内存中都是以二进制形式进行存储的 ，而位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
需要掌握的内容：
- 运算符的优先级
- 位运算符的运算律’
- 位运算高级操作
- 负数的位运算
题目
数组中只出现一次的两个数字
典型题例：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
示例 ：
输入：[1,2,3,3,4,4] 输出：[1,2]
思路
核心：
代码：
class Solution { public: vector<int> findNumsAppearOnce(vector<int>& nums) { int sum = 0; //x ^ y for (auto x : nums) sum ^= x; int k = 0; while (!(sum >> k & 1)) k ++; //找出第k位x^y=1 int first = 0; //第k位为1的元素异或 for (auto x : nums) if(x >> k & 1) first ^= x; return vector<int>{sum ^ first, first}; //sum^first表示x^y^first } };
数组中唯一只出现一次的数字
典型题例：
在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。
请找出那个只出现一次的数字。
你可以假设满足条件的数字一定存在。
示例 ：
输入：[1,1,1,2,2,2,3,4,4,4] 输出：3
思路
代码：
class Solution { public: int findNumberAppearingOnce(vector<int>& nums) { int ones = 0 , twos = 0; for (auto x : nums){ ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones; } return ones; } };
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
