位运算（整数的二进制处理方法）JZ11、12、面试题56-I、64、65
本文共 7196 字，大约阅读时间需要 23 分钟。
文章目录
JZ11二进制中1的个数
题目描述
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。 示例1输入10返回值2
方法一：暴力方法
分析：题目给一个有符号的整数int，求整数转化成二进制数后，1的个数。 直接根据题目的描述来提出方法一。有2个问题： 问题1: 如何从十进制数转化到二进制数？ 问题2:转化为二进制数后，如果判断有1的个数？ 方法1:除2取模法。
int val; // input dataint count = 0;while (val != 0) { int tmp = val % 2; if (tmp == 1) ++count; val /= 2;} 注：当然这种方法，对于大部分数据是对的，但是对于-2147483648,二进制为1000…000，一共有31个0.因为计算机使用补码存储二进制数据的。对于这个数据，我们的方法一输出0，实际上为1.所以这种方法不对。
方法2:二进制移位法
直接将整数看成二进制，然后采用移位的方法。int val; // input dataint count = 0;while (val != 0) { if (val & 1) ++count; val >>= 1;} 代码中val & 1表示val 与 0x000…0001（其中有31个0）进行 & 操作。
注：但是如果val为负数，最高位会补1，所以对于负数还是有点问题。 我们可以转换一下思路，让一个数0x01从右向左与val的每一位进行&操作来判断 int val; // input dataint ans = 0;int mark = 0x01;while (mark != 0) { if (mark & val) ++ans; mark <<= 1;} 这个算法可以解决此题，但是需要运行32次。
时间复杂度：O(32) 空间复杂度：O(1)方法 二：技巧法
对于上一种解法中，无用操作是，如果当前位是0， 还是会做判断，然后一位一位的移动。
如果，给你一种超能力，你一下可以对从右向左的第一位1直接判断，遇到0直接略过，那效率是不是很快。具体的意思是：如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011. 我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000. 也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。 class Solution { public: int NumberOf1(int n) { int count=0; while(n!=0){ ++count; n=n&(n-1);//计算机使用补码存储二进制数据;即，输入的是十进制整数，但计算机存储的是其二进制补码，对其的操作也是对其二进制补码进行的操作； } return count; }}; 时间复杂度：O(n) n为val中1的个数
空间复杂度：O(1)JZ12数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 保证base和exponent不同时为0 示例1输入2,3返回值8.00000
题解
预处理：求pow(b, n)，如果n为负数怎么解决？ 
double Power(double b, int n) { if (n < 0) { b = 1 / b; n = -n; }} 方法一：暴力方法
很显然就是n个b相乘。循环n次。class Solution { public: double Power(double b, int n) { if (n < 0) { b = 1 / b; n = -n; } double ret = 1.0; for (int i=0; i 时间复杂度：O(n)
空间复杂度：O(1)方法二：递归法（快速幂）
class Solution { public: double q_power(double b, int n) { //q_power中的q:quick（快） if (n == 0) return 1.0; double ret = q_power(b, n>>1);//用n>>1代替n/2，因为位运算比算数运算快； if (n&1) { // 奇数，用位与运算代替求余运算（%），位运算效率更高 return ret * ret * b; } else { //偶数 return ret * ret; } } double Power(double b, int n) { if (n < 0) { b = 1 / b; n = -n; } return q_power(b, n); }}; 时间复杂度：O(logn)，每次规模减少一半
空间复杂度：O(logn)，递归栈，因为要记住logn个变量方法三：非递归的快速幂
class Solution { public: double Power(double base, int exponent) { //预处理exponent为负的情况： if(exponent<0){ base=1/base; exponent=-exponent; } double ret=1.0;//注意结果变量类型是double,否则会出错； while(exponent!=0){ if(exponent&1){ //向右移位后exponent的二进制最低位是否为1； ret*=base; } base*=base;//记录base^0,base^1,base^2...,若对应的exponent二进制某一位为1，则将其乘进结果ret; exponent>>=1; } return ret; }}; 上述方法相当于遍历n的二进制位，是1就乘进结果
时间复杂度：O(logn)，因为n的二进制位个数为logn 空间复杂度：O(1)面试题56 - I. 数组只出现一次的两个数字
题目：
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1：输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1]示例 2：输入：nums = [1,2,10,4,1,4,3,3]输出：[2,10] 或 [10,2]
题解：
- 先说（数组中只有
一个数字出现一次）
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
- 思路：直接
全员异或即可，因为异或有以下性质【注：异或针对的是二进制】
代码：
class Solution { public: int singleNumber(vector & nums) { int a=0; for(int val : nums) a^=val; return a; }}; - 有了以上准备，我们想： 如果可以把原数组分成两个子数组，使每个子数组都只包含一个出现一次的数字。那么分别对两个子数组运用上面的
全员异或方法即可。 - 现在的关键点是怎么分出这样的两个数组：
1、全员异或：
设两个只出现一次的数字为 x, y ，全员异或的结果为a=x ⊕ y ，由于 x ！=y，则 x 和 y 二进制至少有一位不同（即分别为 0 和 1 ），设一个变量n，其二进制只有一位是1（对应x 和 y 二进制中找出的值不同的一位）其余为0，这样x、y与n相与一个为0，一个不为0，就可把x、y分成两个数组。其他出现两次的数，分别于n相与，相等的数与n相与结果肯定相同，则自然也分别分入两个数组。 即，根据变量n可以将 nums 拆分为分别包含 x 和 y 的两个子数组。 2、找出变量n: 循环左移计算 n ： 可知对于任意整数 a 有： 若 a & 0001 =1 ，则 a 的第一位为 1 ；
若 a & 0010 =1 ，则 a 的第二位为 11 ； 以此类推…… 因此，初始化一个辅助变量 n = 1，通过与运算从右向左循环判断，可获取整数 x⊕y二进制的首位 1 ，记录于 n 中，代码如下while((a & n) == 0) // m 循环左移一位，直到 z & m ！= 0 n <<= 1;
代码：
class Solution { public: vector singleNumbers(vector & nums) { vector res; int a=0; for(int val : nums) a^=val; int n=1; while((a&n)==0) n<<=1;//注意运算优先级的问题；多加括号即可； int b=0,c=0; for(int val : nums){ if((val&n)==0) b^=val;//注意运算优先级的问题；多加括号即可 else c^=val; } res.push_back(b); res.push_back(c); return res; }}; 时间复杂度 O(N)： 线性遍历 nums使用 O(N) 时间，遍历 x⊕y 二进制位使用 O(32) = O(1)时间。
空间复杂度 O(1) ： 辅助变量 a , b , c , n使用常数大小额外空间。面试题56 - II. 数组中唯一出现一次的数字
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：输入：nums = [3,4,3,3]输出：4示例 2：输入：nums = [9,1,7,9,7,9,7]输出：1
方法一：hashmap。(不推荐)
模式识别：次数--------->哈希表
- 用 hashmap 的键值对的特性，key 储存 nums 中的元素，value 储存该元素出现的次数。
- 找到 value 为 1 的 key，返回 key 即可。
方法二：位运算（优化空间）
由于3个相同的数异或，结果还是该数字，所以不能像56 - I一样用异或来解决。
注：实际上，只需要修改求余数值 m ，即可实现解决 除了一个数字以外，其余数字都出现 m 次 的通用问题。 代码： class Solution { public: int singleNumber(vector & nums) { int res=0; //int变量占4个字节，即32bite（位） vector counts(32); for(int val : nums){ for(int i=0; i<32; i++){ counts[i] += val&1; val>>=1; } } int m = 3; //用加权和来求res for(int i=0; i<32; i++){ if(counts[i]%m) res += pow(2,i); } //或用下面位运算来求res; //for(int i=0; i<32; i++){ // res <<=1; // res |= counts[31-i]%m; //} return res; }}; 时间复杂度 O(N) ： 其中 N 为数组 nums 的长度；遍历数组占用 O(N) ，每轮中的常数个 位运算操作 占用 O(1)。
面试题64. 求1+2+…+n
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：输入: n = 3输出: 6示例 2：输入: n = 9输出: 45
题解：
本题不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 可想到用递归，但递归中需要有递归终止条件，其需要使用 if。 思考： 除了 if和 switch 等判断语句外，是否有其他方法可用来终止递归？-----------利用逻辑运算符的短路效应； 
n=1时左边n > 1 不成立 ，此时右边不执行， “短路” ，终止后续递归n>1 && (n += sumNums(n - 1));
代码：
class Solution { public: int sumNums(int n) { n>1 && (n += sumNums(n - 1)); return n; }}; 
面试题 65. 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:输入: a = 1, b = 1输出: 2
方法：位运算
题解：对数字做运算，除了四则运算外，也就只剩下
位运算了
- 首先分析十进制的加法运算
- 接着分析位运算与十进制加法原理一样，
- 如何用位运算代替加法。
总结： 
Q ： 若数字 a 和 b 中有负数，则变成了减法，如何处理？ A ： 在计算机系统中，数值一律用
注：补码来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。
代码：
class Solution { public: int add(int a, int b) { int sum, carry; do{ sum = a ^ b; //如果左移的数的最高位是符号位，有的编译器会报错。 //所以在计算进位结果的时候，需要把两个数相与的结果强制转换为 unsigned int类型 //（LeetCode中国版的C++好像不支持负值左移） carry = (unsigned int)(a & b)<<1; a = sum; b= carry; } while(b != 0); return sum; }}; 
知识点：
1、
在计算机系统中，数值一律用
补码来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。
转载地址：http://luunz.baihongyu.com/
你可能感兴趣的文章