位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65

文章目录

JZ11二进制中1的个数

题目描述
输入一个整数,输出该数32位二进制表示中1的个数。其中负数用补码表示

示例1
输入
10
返回值
2

方法一:暴力方法
分析:题目给一个有符号的整数int,求整数转化成二进制数后,1的个数。
直接根据题目的描述来提出方法一。有2个问题:
问题1: 如何从十进制数转化到二进制数?
问题2:转化为二进制数后,如果判断有1的个数?

方法1:除2取模法。

int val; // input data
int 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 data
int count = 0;
while (val != 0) { 
    if (val & 1) ++count;
    val >>= 1;
}

代码中val & 1表示val 与 0x000…0001(其中有31个0)进行 & 操作。
val >>= 1表示,如果val的二进制是110,则操作之后会变成011,也就是舍去最低位,然后最高位补0.
注:但是如果val为负数,最高位会补1,所以对于负数还是有点问题。
我们可以转换一下思路,让一个数0x01从右向左与val的每一位进行&操作来判断

int val; // input data
int 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为负数怎么解决?
《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》

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<n; ++i) ret *= b;
        return ret;
    }
};

时间复杂度:O(n)
空间复杂度:O(1)

方法二:递归法(快速幂)
《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》

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个变量

方法三:非递归的快速幂
《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》

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]

题解:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

  • 思路:直接全员异或即可,因为异或有以下性质【注:异或针对的是二进制
    《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》
    代码:
class Solution { 
public:
    int singleNumber(vector<int>& 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 != 0 ,则 a 的第一位为 1 ;
若 a & 0010 !=0 ,则 a 的第二位为 1;
以此类推……
因此,初始化一个辅助变量 n = 1,通过与运算从右向左循环判断,可获取整数 x⊕y二进制的首位 1 ,记录于 n 中,代码如下

while((a & n) == 0) // m 循环左移一位,直到 z & m != 0
    n <<= 1;

代码:

class Solution { 
public:
    vector<int> singleNumbers(vector<int>& nums) { 
        vector<int> 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一样用异或来解决。
《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》
注:实际上,只需要修改求余数值 m ,即可实现解决 除了一个数字以外,其余数字都出现 m 次 的通用问题。
代码:

class Solution { 
public:
    int singleNumber(vector<int>& nums) { 
        int res=0;
        //int变量占4个字节,即32bite(位)
        vector<int> 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)。
空间复杂度 O(1): 数组 counts 长度恒为 32 ,占用常数大小的额外空间。

面试题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 等判断语句外,是否有其他方法可用来终止递归?———–利用逻辑运算符的短路效应
《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》

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;
    }
};

《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》

面试题 65. 不用加减乘除做加法

写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

方法:位运算
题解:

对数字做运算,除了四则运算外,也就只剩下位运算

  • 首先分析十进制的加法运算
    《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》
  • 接着分析位运算与十进制加法原理一样,
    《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》
  • 如何用位运算代替加法。
    《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》
    总结:
    《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》

注:
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;
    }
};

《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》

知识点:

1、《位运算(整数的二进制处理方法)JZ11、12、面试题56-I、64、65》
2、位运算的效率比乘除法及求余运算的效率要高很多。
3、

在计算机系统中,数值一律用 补码 来表示和存储。补码的优势: 加法、减法可以统一处理(CPU只有加法器)。

    原文作者:萌萌滴太阳
    原文地址: https://blog.csdn.net/qq_42647047/article/details/110097391
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞