相城建设监理有限公司网站,网站外部链接如何建设,福州网站seo优化公司,宜昌市建设信息网站文章目录 一. 位运算符脑图二. 相关题目1. 统计二进制数中0的个数2. 数组中只出现一次的数字3. 数组中只出现一次的数字 II4. 不用加减乘除做加法 一. 位运算符脑图 二. 相关题目
1. 统计二进制数中0的个数
解题思路#xff1a;x (x-1)#xff1b;它的作用是每次循环… 文章目录 一. 位运算符脑图二. 相关题目1. 统计二进制数中0的个数2. 数组中只出现一次的数字3. 数组中只出现一次的数字 II4. 不用加减乘除做加法 一. 位运算符脑图 二. 相关题目
1. 统计二进制数中0的个数
解题思路x (x-1)它的作用是每次循环把 x 的二进制中从右往左数的最后一位1变成0直道变成全0为止循环结束。
性能分析
时间复杂度O(1)一般输入的数字都有固定的二进制位数。空间复杂度O(1)没有开辟额外的空间。
完整代码
size_t CountOne(int num)
{size_t count 0;while(x){count;// 通过这个迭代// 每次可以消除x二进制位中的一个1// 直到x最终为0x x(x-1);}return count;
}2. 数组中只出现一次的数字
题目连接
解题思路
首先利用异或运算的规律0异或任何数得到任何数相同的数异或得0用0去异或数组中的每一个元素得到两个只出现一次的数字我们假设是AB异或在一起的结果。这个结果的二进制中的1表现的是A和B在这个比特位上的数字是不同的。我们就取从左往右第一个1所在的位数假设是第3位接着把原数组分成两组分组标准是第3位是否为1。如此**出现两次的数依然会被分到同一个组**因为相同数字所有位都相同而不同的数肯定不在一组。然后把这两个组按照最开始的思路拿数字0去依次异或剩余的两个结果就是这两个只出现一次的数字。
性能分析
时间复杂度O(n)。n为数组的长度。空间复杂度O(1)。
完整代码
class Solution
{
public:void FindNumsAppearOnce(vectorint data,int* num1,int *num2) {// 数组元素为0或输出型参数为空直接结束if(data.size() 0 || num1 nullptr || num2 nullptr){return;}// 1、算出两个只出现一次的数字异或在一起的结果int ret 0;for(const auto e : data){ret ^ e;}// 2、计算得到两个只出现一次的数字异或后最高比特位为1的位置int bit 0;for(int i 0; i 32; i){if((reti) 1){bit i;}}// 3、分成两组分别求出两个只出现一次的数字*num1 0;*num2 0;for(const auto e : data){if(e (1bit)){*num1 ^ e;}else {*num2 ^ e;}}}
};3. 数组中只出现一次的数字 II
题目连接
解题思路 首先如果我们不考虑这个只出现一次的数字那么这个数组中的每一个数字都出现了三次。我们创建一个数组int count[32]去统计所有数的每一位比特位上一共有多少个1统计结果 count 的每一个元素的值一定是 3n如果把这个只出现一次的数字也给统计进去那么 count 的每一个元素的值一定是3n 或 3n1根据 count 的每一个元素的值去模3来还原出只那个出现一次的那个数字。
性能分析
时间复杂度O(n)。n为数组的长度。空间复杂度O(1)。具体应该是数字的二进制位数但一般输入的数字都有固定的二进制位数。
完整代码
class Solution {
public:int singleNumber(vectorint nums) {// 1、统计所有数的每一位比特位上一共有多少个1// 要么3n要么3n1vectorint count(32);for(auto e : nums){for(int i0; i32; i)// 遍历每一个元素的每一位比特位{if(e (1i)){count[i];}}}// 2、根据count的结果还原出只出现一次的那个数字int ret0;for(int i0; i32; i){if(count[i]%3){ret | (1i);}}return ret;}
};4. 不用加减乘除做加法
题目连接
解题思路 二进制位异或运算相当于对应位相加不考虑进位 比如 1 ^ 1 0 — 1 1 0 (当前位值为0进一位) 1 ^ 0 1 — 1 0 1 (当前位值为1) 0 ^ 0 0 — 0 0 0 (当前位值为0) 二进制位与运算相当于对应位相加之后的进位 比如 1 1 1 — 1 1 0 (当前位的值进一位) 1 0 0 — 1 0 1 (当前位的值不进位) 0 0 0 — 0 0 0 (当前位的值不进位) 两个数相加对应二进制位相加的结果 进位的结果 比如 3 2 -- 0011 0010 -- 0011 ^ 0010 ((0011 0010) 1) — (0011 ^ 0010) ^ ((0011 0010) 1) 当进位之后的结果为0时相加结束
完整代码
class Solution {
public:int add(int a, int b) {// 进位数为0时结束循环while(b){// 得到二者和的无进位的结果int notCarrya^b;// 得到进位数*10的结果b((unsigned int)(ab))*2;anotCarry;}return a;}
};
