网络彩票的网站怎么做,网络平台建设管理制度,苏州网站建设官网,郑州做网站的大公司有哪些大家好#xff0c;我是怒码少年小码。
今天讲讲几个位运算的经典算法。
位移的妙用
1. 位1的个数
LeetCode 191#xff1a;编写一个函数#xff0c;输入是一个无符号整数#xff08;以二进制串的形式#xff09;#xff0c;返回其二进制表达式中数字位数为 ‘1’ 的个…大家好我是怒码少年小码。
今天讲讲几个位运算的经典算法。
位移的妙用
1. 位1的个数
LeetCode 191编写一个函数输入是一个无符号整数以二进制串的形式返回其二进制表达式中数字位数为 ‘1’ 的个数。 输入n 00000000000000000000000000001011输出3解释输入的二进制串 00000000000000000000000000001011 中共有三位为 ‘1’。 方法一
还记得我们上一篇最后写的位运算代码套路的获取吗与运算的特点是只有两边都为1结果才为1否则结果为零。利用这个特点我们可以解决这个问题例如数字3和数字1的二进制串进行与运算
000000000000000000000000000010110000000000000000000000000000000100000000000000000000000000000001只用我们把1左移或者把原始数字右移然后进行与运算结果为1说明这一位上是1就记录“1”的数量加1知道把32为都比较完后有多少个记录就可以了。原始数字右移的代码如下
int hammingWeight(int n) {int count 0;for (int i 0; i 32; i) {count (n i) 1;}return count;
}方法二
按位与运算有个性质对于整数n计算n (n-1)的结果为将n的二进制表示的最后一个1变成0。利用这条性质令n n (n-1)则n最后的二进制表示中的1数量减少一个。例如 重复该操作直到n的二进制表示中的全部数位都变成0则操作次数即为n的位1的个数。代码如下
int hammingWeight01(int n) {int count 0;while (n ! 0) {n n (n - 1);count;}return count;
}这两种方法第一种的循环次数取决于原始数字的位数第二种取决于原始数字种1的个数效率自然高不少。
###2. 比特位计数
LeetCode 338给你一个整数 n 对于 0 i n 中的每个 i 计算其二进制表示中 1 的个数 返回一个长度为 n 1 的数组 ans 作为答案。 输入n 2输出[0,1,1]解释 0 -- 0 1 -- 1 2 -- 10 自己先思考一下这题真的很简单
分析遍历0 i n中的每一个数字获取它们二进制串中的“1”的个数可以单独设置一个函数然后把个数保存到数组对应的位置上。 int helper(int n){int count 0;while(n ! 0){n n (n-1);count;}return count;}vectorint countBits(int n) {vectorint ans(n1);for(int i 0; i n1; i){int count helper(i);ans[i] count;}return ans;}这就是一通百通吧。
3. 颠倒无符号整数
LeetCode 190颠倒给定的 32 位无符号整数的二进制位。 分析肯定是先要获取某一位然后再把它放到应该的位置上去。获取就用原始数字与1进行与运算然后原始数字右移这样我们就能得到低位置上的二进制数然后通过左移power个来放到高位 int reverseBits(int n) {int reversed 0, power 31;while (n ! 0) {reversed (n 1) power;n 1;power--;}return reversed;
}n 1是一个右移操作符它将变量n的值向右移动一位。类似于n1是把n的值加一。
位实现加减乘除专题
在计算机中位运算的效率比单纯加减乘除的效率更高因此在高性能软件的源码中大量应用。
1. 位运算实现加法
LeetCode 371给你两个整数 a 和 b 不使用 运算符 和 - 计算并返回两整数之和。
两个位加的时候需要考虑两个问题进位部分是什么不进位部分是什么
对于不进位部分001001的情况是相同为0不同为1其实是a⊕b对于进位部分11a和b的这一位都是1的时候才会进位而且进位只能是1其实是ab1,然后位数由1位变成两位需要手动移位(a b) 1
所以
不进位部分用a⊕b计算就可以是否进位以及进位值使用(a b) 1计算即可
int getSum(int a, int b) {while (b ! 0) {int sign (a b) 1;//计算出哪些位同时为1这些需要进位a a ^ b; //无进位和b sign;}return a;}从低位开始处理每一位考虑进位并逐步向高位移动。
2. 递归乘法
LeetCode 08.05递归乘法。 写一个递归函数不使用 * 运算符 实现两个正整数的相乘。可以使用加号、减号、位移但要吝啬一些。 示例 输入 a1b10输出10 不用*计算一种方法是将一个作为循环的参数对另一个进行累加但是这样效率太低所以还要考虑位运算。
首先需要求得a和b的最小值和最大值把其中的最小值当做乘数选最小值当乘数后续计算算的少将其拆分成2的幂的和方便左移 即min a0 * 2^0 a12^1 a2 2^2 … ai2i…其中ai取0或者1相当于用二进制的视角去看待min比如12用二进制来表示就是1100即10000100 13 * 12 13 * 84 138 13*4 133(132);
上面仍然需要左移5次存在重复计算可以进一步简化 假设我们需要的结果是ans 定义临时变量 tmp 132 52计算后可以先让ans 52 然后tmp继续左移一次tmp 521 104此时再让ans ans tmp 此时只要执行三次移位和一次加法 int multiply(int a, int b) {int min a b ? a : b;int max a b ? a : b;int ans 0;for (int i 0; min ! 0; i) {if ((min 1) 1) {ans max;}min 1;max max;}return ans;}END
本文的主要内容来自算法通关村。
