旅游网站开发费用,简历模板免费下载可编辑,wordpress导航主图,未备案个人网站 如何挣钱关卡名 位运算的高频算法题 我会了✔️ 内容 1.理解位运算如何统计1的个数的 ✔️ 2.理解位运算如何实现加法 ✔️ 3.理解递归乘法是如何实现的 ✔️
1 位移的妙用
位移操作是一个很重要的问题#xff0c;可以统计数字中1的个数#xff0c;在很多高性能软件中也大量应… 关卡名 位运算的高频算法题 我会了✔️ 内容 1.理解位运算如何统计1的个数的 ✔️ 2.理解位运算如何实现加法 ✔️ 3.理解递归乘法是如何实现的 ✔️
1 位移的妙用
位移操作是一个很重要的问题可以统计数字中1的个数在很多高性能软件中也大量应用我们看几个高频题目。
1.1 位1的个数
LeetCode191 编写一个函数输入是一个无符号整数以二进制串的形式返回其二进制表达式中数字位数为 1 的个数。 拓展问题16进制时怎么统计0000 00de
示例1
输入00000000000000000000000000001011
输出3
解释输入的二进制串 00000000000000000000000000001011 中共有三位为 1。示例2
输入00000000000000000000000010000000
输出1
解释输入的二进制串 00000000000000000000000010000000 中共有一位为 1。 首先我们可以根据题目要求直接计算题目给定的 n 是 32 位二进制表示下的一个整数计算位 1 的个数的最简单的方法是遍历 n 的二进制表示的每一位判断每一位是否为 1同时进行计数。 那问题就是如何通过位运算来识别到1例如00001001001000100001100010001001首先我们注意到要识别到最低位的1可以这么做 00001001001000100001100010001001 00000000000000000000000000000001 00000000000000000000000000000001 也就说将原始数字和1进行运算就能知道最低位是不是1了那其他位置怎么算呢 我们可以有两种思路让1不断左移或者将原始数据不断右移。例如将原始数据右移就是 00000100100100010000110001000100 00000000000000000000000000000001 00000000000000000000000000000000 很明显此时就可以判断出第二位是0然后继续将原始数据右移就可以依次判断出每个位置是不是1了。因此是不是1计算一下(ni) 1就可以了所以代码顺理成章
public int hammingWeight(int n) {int count 0;for (int i 0; i 32; i) {count (n i) 1;}return count;
}
这个题也可以通过将1左移来实现的该问题作为一个作业题请你改造上面的代码来实现。 上面的代码写出来这个题基本就达标了但这还不是最经典的解法我们继续分析 按位与运算有一个性质对于整数 n计算n (n−1) 的结果为将 n 的二进制表示的最后一个 1 变成 0。利用这条性质令 nn (n−1)则 n 的二进制表示中的 1 的数量减少一个。重复该操作直到 n 的二进制表示中的全部数位都变成 0则操作次数即为 n 的位 1 的个数。什么意思呢我们继续看上面的例子 n: 00000100100100010000110001000100 n-1: 00000100100100010000110001000011 n(n-1) 00000100100100010000110001000000 可以看到此时n(n-1)的结果比n少了一个1此时我们令nn(n-1)继续执行上述操作 n: 00000100100100010000110001000000 n-1: 00000100100100010000110000111111 n(n-1) 00000100100100010000110000000000 可以看到此时n(n-1)的结果比上一个n又少了一个1所以我们令nn(n-1)循环执行上述操作我们统计一下循环执行的次数就能得到结果了。 那循环该什么时候停下呢很显然当n变成0的时候否则说明数据里面还有1可以继续循环。所以当且仅当 n0 时n 的二进制表示中的全部数位都是 0代码也很好写了
public int hammingWeight(int n) {int count0;while(n!0){nn(n-1);count;}return count;
}
上面两种解法第一种的循环次数取决于原始数字的位数而第二种的取决于1的个数效率自然要高出不少使用n n (n - 1)计算是位运算的一个经典技巧该结论可以完美用到下面的题目中
1.2 比特位计数
LeetCode338.给你一个整数 n 对于 0 i n 中的每个 i 计算其二进制表示中 1 的个数 返回一个长度为 n 1 的数组 ans 作为答案。 示例1 输入n 2 输出[0,1,1] 解释0到n有 0 1 2 三个数字每个数字含有1的个数分别为0 1 1 个如下 0 -- 0 1 -- 1 2 -- 10 示例2 输入n 5 0 1 2 3 4 5 101 输出[0,1,1,2,1,2] 解释0到n有 0 1 2 3 4 5 六个数字每个数字含有1的个数分别为0,1,1,2,1,2个如下 0 -- 0 1 -- 1 2 -- 10 3 -- 11 4 -- 100 5 -- 101 最直观的方法是对从 0 到 num 的每个数直接计算一比特数。每个int 型的数都可以用 32 位二进制数表示只要遍历其二进制表示的每一位即可得到1 的数目。
public int[] countBits(int num) {int bitsnew int[num1];for(int i0;inum;i){for(int j0;j32;j){bits[i](ij)1;}}return bits;
}
利用位运算的技巧可以提升计算速度。按位与运算的一个性质是对于任意整数 x令 xx(x−1)该运算将 x 的二进制表示的最后一个 1 变成 0。因此对 x 重复该操作直到 x 变成0则操作次数即为 x 的「一比特数」。
public int[] countBits(int num) {int[] bits new int[num 1];for (int i 0; i num; i) {bits[i] countOnes(i);}return bits;}public int countOnes(int x) {int ones 0;while (x 0) {x (x - 1);ones;}return ones;
} 有没有发现比特位计数和位1的个数计算规则完全一样 这就是为什么我们说研究清楚一道题可以干掉一大票的题目。
1.3 颠倒无符号整数
LeetCode190 .颠倒给定的 32 位无符号整数的二进制位。 提示输入是一个长度为32的二进制字符串。 示例1 输入n 00000010100101000001111010011100 输出964176192 (00111001011110000010100101000000) 解释输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596 因此返回 964176192其二进制表示形式为 00111001011110000010100101000000。 示例2 输入n 11111111111111111111111111111101 输出3221225471 (10111111111111111111111111111111) 解释输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。 首先这里说是无符号位那不必考虑正负的问题最高位的1也不表示符号位这就省掉很多麻烦。 我们注意到对于 n 的二进制表示的从低到高第 i 位在颠倒之后变成第 31-i 位( 0≤i32)所以可以从低到高遍历 n 的二进制表示的每一位将其放到其在颠倒之后的位置最后相加即可。 看个例子为了方便我们使用比较短的16位演示 原始数据1001 1111 0000 0110(低位) 第一步获得n的最低位0然后将其右移16-115位得到 reversed 0*** **** **** **** n右移一位 0100 1111 1000 0011 第二步继续获得上面n的最低位1然后将其右移15-114位并与reversed相加得到 reversed01** **** **** **** n右移一位0010 0111 1100 0001 继续一直到n全部变成0 理解之后实现就比较容易了。由于 Java不存在无符号类型所有的表示整数的类型都是有符号类型因此需要区分算术右移和逻辑右移在Java 中算术右移的符号是 逻辑右移的符号是 。
public int reverseBits(int n) {int reversed 0, power 31;while (n ! 0) {reversed (n 1) power;n 1;power--;}return reversed;
} 本题的解法还有很多例如还有一种分块的思想 n 的二进制表示有 32 位可以将 n 的二进制表示分成较小的块然后将每个块的二进制位分别颠倒最后将每个块的结果合并得到最终结果。这分治的策略将 n 的 32 位二进制表示分成两个 16 位的块并将这两个块颠倒然后对每个 16 位的块重复上述操作直到达到 1 位的块。为了方便看清楚我们用字母代替01如下图所示。 具体做法是 下面的代码中每一行分别将 n 分成16 位、8 位、4 位、2 位、1 位的块即把每个块分成两个较小的块并将分成的两个较小的块颠倒。同样需要注意使用 Java 实现时右移运算必须使用逻辑右移。由于是固定的32位我们不必写循环或者递归直接写 reverseBits(int n) {n (n 16) | (n 16);n ((n 0xff00ff00) 8) | ((n 0x00ff00ff) 8);n ((n 0xf0f0f0f0) 4) | ((n 0x0f0f0f0f) 4);n ((n 0xcccccccc) 2) | ((n 0x33333333) 2);n ((n 0xaaaaaaaa) 1) | ((n 0x55555555) 1);return n;} 这种方法在JDK、Dubbo等源码中都能见到特别是涉及协议解析的场景几乎都少不了位操作。积累相关的技巧可以方便面试也有利于阅读源码。
面试算法和工程算法
2 位实现加减乘除专题
在计算机中位运算的效率比加减乘数效率更高因此在高性能软件的源码中大量应用而且计算机里各种运算本质上都是位运算。本专题我们就研究几个相关问题。
2.1 位运算实现加法
LeetCode371 给你两个整数 a 和 b 不使用 运算符 和 - 计算并返回两整数之和。 示例1 输入a 1, b 2 输出3 既然不能使用和-那只能使用位运算了。我们看一下两个二进制位相加的情况 [1] 0 0 0 [2] 0 1 1 [3] 1 0 1 [4] 1 1 0 发生了进位应该是10的 两个位加的时候我们无非就考虑两个问题进位部分是什么不进位部分是什么。从上面的结果可以看到对于a和b两个数不进位部分的情况是相同为0不同为1这不就是a⊕b吗 而对于进位我们发现只有a和b都是1的时候才会进位而且进位只能是1这不就是ab1吗然后位数由1位变成了两位也就是上面的[4]的样子那怎么将1向前挪一下呢手动移位一下就好了也就是(a b) 1。所以我们得到两条结论
不进位部分用a⊕b计算就可以了。是否进位以及进位值使用(a b) 1计算就可以了。
于是我们可以将整数 a 和 b 的和拆分为 a 和 b 的无进位加法结果与进位结果的和代码就是
public int getSum(int a, int b) {while (b ! 0) {int sign (a b) 1;a a ^ b;b sign;}return a;
}
2.2 递归乘法
LeetCode里面试08.05递归乘法。 写一个递归函数不使用 * 运算符 实现两个正整数的相乘。可以使用加号、减号、位移但要吝啬一些。 示例1 输入A 1, B 10 输出10 如果不让用*来计算一种是将一个作为循环的参数对另一个进行累加但是这样效率太低所以我们还是要考虑位运算。 首先求得A和B的最小值和最大值对其中的最小值当做乘数为什么选最小值因为选最小值当乘数可以算的少将其拆分成2的幂的和即min a_0 * 2^0 a_1 * 2^1 ... a_i * 2^i ...其中a_i取0或者1。其实就是用二进制的视角去看待min比如12用二进制表示就是1100即10000100。例如 13 * 12 13 * (8 4) 13 * 8 13 * 4 (13 3) (13 2); 上面仍然需要左移5次存在重复计算可以进一步简化 假设我们需要的结果是ans 定义临时变量tmp132 52计算之后可以先让ans52 然后tmp继续左移一次tmp521104此时再让ansanstmp 这样只要执行三次移位和一次加法实现代码
public int multiply(int A, int B) {int min Math.min(A,B);int max Math.max(A,B);int ans 0;for(int i0; min!0; i){if((min1)1){ans max;}min 1;max max;}
}
