小型网站建设价格,什么网站可以找试卷做,在线ppt制作网站有哪些,烟台电子商务网站一.位运算的概念什么是位运算#xff1f;程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。位运算就是直接操作二进制数#xff0c;那么有哪些种类的位运算呢#xff1f;常见的运算符有与()、或(|)、异或(^)、…一.位运算的概念什么是位运算程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。位运算就是直接操作二进制数那么有哪些种类的位运算呢常见的运算符有与()、或(|)、异或(^)、取反(~)、左移()、右移(是带符号右移 无符号右移动)。下面来细看看每一种位运算的规则。操作符运算规则将两个数字的二进制位进行按位与操作即当两个数字的某位二进制数中同时为1结果才为1否则是0 000, 010, 111例子位运算 | (或)规则二进制对应位两两进行逻辑或运算(对应位中有一 个为1则为1) 即0|00,0|11,1|113.位运算 ^ (异或)规则二进制对应位两两进行逻辑XOR (异或) 的运算(当对应位的值不同时为 1, 否则为 0)即0^00, 0^11, 1^104.按位取反~规则二进制的0变成11变成0。5.左移运算左移后右边位补 0右移运算右移后左边位补原最左位值(可能是0可能是1)右移运算右移后左边位补 0关于位运算的规则我们再进行详细的讲述关于左移无论对于正数还是负数结果都是在原来数值的基础上进行乘2操作但是对于右移符号这其中就有说法了,对于无符号右移它的运算规则是将原有数字右移在左边补0也就是说如果原有的数字是负数通过无符号右移会变成正数对于正数则是简单的除2的效果对于右移符号则是无论对于正数还是负数达到的效果都是除2二.关于位运算的常见题目交换两个数利用位运算将数个数值进行交换aa^b;//aa^b
ba^b;//b(a^b)^ba^0a
aa^b;//a(a^b)^(a^b^b)0^b0判断奇偶数给定一个数值判断这个数字是奇数还是偶数if(n 1 1){// n 是个奇数。
}不用加减乘除做加法牛客链接https://www.nowcoder.com/practice/e7e0d226f1e84ba7ab8b28efc6e1aebc?tpId8tqId11065rp1ru/activity/ojqru/ta/cracking-the-coding-interview/question-ranking实现思路关于实现加法运算而不使用加减乘除运算我们则可以选择调用相关的位运算进行求解①按位异或^:可以实现无进位的加法运算比如 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时相加结束public int addAB(int A, int B) {
// write code here
if(B0){
return A;
}
int sum0;
int carray0;
while(B!0){
sumA^B;
carray(AB)1;
Asum;
Bcarray;
}
return A;
}求出现一次的数字①给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。说明你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗实现思路根据异或运算的特性我们能够理解的是任何数字异或自身结果都是0所以对于所有成对出现的数字而言我们将其全部异或一遍其结果是0再将唯一出现的数字再次异或最后的结果也就是那个唯一出现的数字。我们给出codeclass Solution {public int singleNumber(int[] nums) {int value0;for(int i0;inums.length;i){value^nums[i];}return value;}
}求出现一次的数字②一个整型数组 nums 里除两个数字之外其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)空间复杂度是O(1)。LeetCode链接https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/与①有所不同的是这次题目的给出的条件是有两个不同的数字让我们分别找出这两个数字既然仍然是出现多组出现两次的数字那么我们的实现大思路仍然保持不变就是通过不断异或来排除出现两次的数字那么这时候便引出了问题的关键异或之后剩下的结果是两个数字异或之后的结果那么我们如何在结果中将这两个数字分别拿出来呢这里我们选择的策略是区分两个数字中不同的一位具体实现思路如下首先将所有数字进行异或将最后生成的结果与m(m1)进行异或目的是找出异或结果中为1的一位因为两个不同的数字必然有一位不同异或结果是1我们利用这个辨识特点分别对数组进行分组异或最后的两个数字就是异或的结果具体code如下class Solution {public int[] singleNumbers(int[] nums) {//因为相同的数字异或为0任何数字与0异或结果是其本身。//所以遍历异或整个数组最后得到的结果就是两个只出现一次的数字异或的结果即 z x ^ yint z 0; for(int i : nums) z ^ i;//我们根据异或的性质可以知道z中至少有一位是1否则x与y就是相等的。//我们通过一个辅助变量m来保存z中哪一位为1.可能有多个位都为1我们找到最低位的1即可。//举个例子z 10 ^ 2 1010 ^ 0010 1000,第四位为1.//我们将m初始化为1如果z m的结果等于0说明z的最低为是0//我们每次将m左移一位然后跟z做与操作直到结果不为0.//此时m应该等于1000同z一样第四位为1.int m 1;while((z m) 0) m 1;//我们遍历数组将每个数跟m进行与操作结果为0的作为一组结果不为0的作为一组//例如对于数组[1,2,10,4,1,4,3,3]我们把每个数字跟1000做与操作可以分为下面两组//nums1存放结果为0的: [1, 2, 4, 1, 4, 3, 3]//nums2存放结果不为0的: [10] (碰巧nums2中只有一个10如果原数组中的数字再大一些就不会这样了)//此时我们发现问题已经退化为数组中有一个数字只出现了一次//分别对nums1和nums2遍历异或就能得到我们预期的x和yint x 0, y 0;for(int i : nums) {//这里我们是通过if...else将nums分为了两组一边遍历一遍异或。//跟我们创建俩数组nums1和nums2原理是一样的。if((i m) 0) x ^ i;else y ^ i;}return new int[]{x, y};}
}实现思路6.求出现一次的数字③在一个数组 nums 中除一个数字只出现一次之外其他数字都出现了三次。请找出那个只出现一次的数字。 LeetCode链接https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/实现思路相对于出现两次的数字能够利用异或的规律解决问题出现三次的数字显得毫无规律可言那么我们又该如何解决出现三次的数字问题呢我们可以观察其每一位数字的规律对于每一位数字而言既然是出现三次那么则可以对数组中的每一位数字的32个二进制位进行遍历记录每一位的结果至于最后返回的数字我们可以通过res(res0)和数组中的每一位进行%3然后进行或操作然后将res左移让二进制中的每一位回到原来的位置即可code如下class Solution {public int singleNumber(int[] nums) {int[] counts new int[32];for(int num : nums) {for(int j 0; j 32; j) {counts[j] num 1;num 1;}}int res 0, m 3;for(int i 0; i 32; i) {res 1;res | counts[31 - i] % m;}return res;}
}
7.n皇后问题的位运算优化notes需要注意的是利用位运算解决n皇后问题的暴力递归问题只是对效率问题进行常数级别的优化limit:是位数限制,对于行列数为N的棋盘limit的限制是对于前N个二进制位数均为1对于N行列的棋盘而言前N个二进制位代表棋盘的每一行第一个二进制位代表第一行第二个代表第二行........①col:对于每次摆放个皇后就将这个二进制位置变为1表示这个二进制位不能摆放皇后了②leftLim:左斜线限制如果leftLim为1代表对于当前行来说这个位置不能摆放皇后了。③RightLim:右斜线限制如果RightLim为1同样对于当前行来说这个位置不能摆放皇后了。④limitcol:代表col前N个二进制位都是1表示N个皇后都已经摆放好了游戏结束退出递归⑤limit(~(col|leftLim|rightLim))pos是在每一行中能选择的列⑥ mostRightpos(~pos1)取出最右边的一位⑦ pos-mostRight将最右边的位置从可选择的位数中去除使当前行不能放置皇后⑧while(pos!0) 循环当前行中能选择的位置⑨res process2(limit,col|mostRight,(leftLim|mostRight)1, (rightLim|mostRight)1)循环下一层code如下public static int process2(int limit,int col,int leftLim,int rightLim){//递归出口if(limitcol){return 1;}//计算能放的位置int pos limit(~(col|leftLim|rightLim));int mostRight0;int res0;//检验是否能递归while(pos!0){//找最右的位置mostRightpos(~pos1);pos-mostRight;res process2(limit,col|mostRight,(leftLim|mostRight)1, (rightLim|mostRight)1);}return res;
