php网站开发工程师招聘要求,汕头网站优化,大型seo公司,行政机关单位网站建设数独 数独是介绍位运算的好例子#xff0c;运用位运算和不运用效率差别还是挺大的。我们先看数独需求: 1、当前数字所在行数字均含1-9#xff0c;不重复 2、当前数字所在列数字均含1-9#xff0c;不重复 3、当前数字所在宫#xff08;即3x3的大格#xff09;数字均含1-9运用位运算和不运用效率差别还是挺大的。我们先看数独需求: 1、当前数字所在行数字均含1-9不重复 2、当前数字所在列数字均含1-9不重复 3、当前数字所在宫即3x3的大格数字均含1-9不重复宫如下图每个粗线内是一个宫 、 常规算法 若是我们采用常规方式的每填写一个数字需要检查当前行、列宫中其他位置是否有重复数字极端情况下需要循环273*9次来进行检查我们看下常规算法下check int check(int sp) { // 檢查同行、列、九宮格有沒有相同的數字若有傳回 1 int fg 0 ; if(!fg) fg check1(sp, startH[sp], addH) ; // 檢查同列有沒有相同的數字 if(!fg) fg check1(sp, startV[sp], addV) ; // 檢查同行有沒有相同的數字 if(!fg) fg check1(sp, startB[sp], addB) ; // 檢查同九宮格有沒有相同的數字 return(fg) ; } int check1(int sp, int start, int *addnum) { // 檢查指定的行、列、九宮格有沒有相同的數字若有傳回 1 int fg 0, i, sp1 ; //万恶的for循环 for(i0; i9; i) { sp1 start addnum[i] ; if(sp!sp1 sudoku[sp]sudoku[sp1]) fg ; } return(fg) ; } 这个效率是否很吓人每次填写一个就需要check27次有木有check一次的算法当然有了采用位运算一次搞定。来我们看下位运算的思路: 位运算 我们看上图所示单个行或者列、宫数据都是有1-9共9个数字我们统称为九宫数字。若是我们采用二进制以九宫数字充当二进制数据的位坐标,采用9位的二进制就可以与之一一对应位上有数据标识为1无数据标识为0如此一个正数就能解决一行九宫数据状态无需需存一个数组。 比如 看图中深红色部分当前九宫数据中已经有1和3那么二进制右起第一位和第三位标识为1一个数字5就可以存下当前行或者列、宫数组状态了,如若数字为511表明所有的九宫数字都用完了如图第一行。 check一个数字是否已经被占用了可以采取位运算来获取二进制的右数第k位来查看是否是1若是1表明指定数字已经被占用了。我们看下具体check算法: // sp 是当前位置索引indexV 行索引indexH 列索引indexB九宫格索引int check(int sp,int indexV,int indexH,int indexB) { // 检查同行、列、九宮格沒有用到的数字若已经用过返回 1 int status statusV[indexV]|statusH[indexH]|statusB[indexB]; //9个数字都被用了 if (statusSTATUS_MAX_VALUE) { return 1; } int numbersudoku[sp]; //取右数第k位,若是1表明这个值已经存在了 return status(number-1)1; } // 行、列、宫二进制数据指定位置标记为1int markStatus(int indexV,int indexH,int indexB,int number){ if (number1) { return 0; } //把右数第k(从1计数)位变成1 statusV[indexV]|(1(number-1)); statusH[indexH]|(1(number-1)); statusB[indexB]|(1(number-1)); } 我们以以下图例位置举例如何获得当前位置可以填取的数字 可以看到2个位运算就解决了检查可用数字的操作了而之前常规算法需要用27次查找才可以获取到。当然了这个算法还可以优化比如采用启发式DFS搜索可用数字速度更快感兴趣可点击这里。 常规算法和位运算算法C语言代码我已经上传码云了想了解的点击下面链接自行去查看去。常规算法google的 地址: 常规算法数独位运算版本数独 基础 位操作符 符号含义规则 与两个位都为1时结果为1|或有一个位为1时结果为1^异或0和1异或0都不变异或1则取反~取反0和1全部取反左移位全部左移若干位高位丢弃低位补0算术右移位全部右移若干位高位补k个最高有效位的值逻辑右移位全部右移若干位高位补0注意: 1、位运算只可运用于整数对于float和double不行。 2、另外逻辑右移符号各种语言不太同比如java是。 3、位操作符的运算优先级比较低尽量使用括号来确保运算顺序。比如1i1,会先执行i1再执行。 应用实例 很棒的应用实例你可以mark一下方便以后对照使用。 1、混合体 位运算实例 位运算功能示例x 1去掉最后一位101101-10110x 1在最后加一个0101101-1011010x 1 | 1在最后加一个1101101-1011011x | 1把最后一位变成1101100-101101x -2把最后一位变成0101101-101100x ^ 1最后一位取反101101-101100x | (1 (k-1))把右数第k位变成1101001-101101,k3x ~ (1 (k-1))把右数第k位变成0101101-101001,k3x ^(1 (k-1))右数第k位取反101001-101101,k3 x 7取末三位1101101-101x (1 k-1)取末k位1101101-1101,k5x (k-1) 1取右数第k位1101101-1,k4x | ((1 k)-1)把末k位变成1101001-101111,k4x ^ (1 k-1)末k位取反101001-100110,k4x (x1)把右边连续的1变成0100101111-100100000x | (x1)把右起第一个0变成1100101111-100111111x | (x-1)把右边连续的0变成111011000-11011111(x ^ (x1)) 1取右边连续的1100101111-1111x -x去掉右起第一个1的左边100101000-1000x0x7F取末7位100101000-101000x ~0x7F是否小于127001111111 ~0x7F-0x 1判断奇偶000001111-12、交换两数 int swap(int a, int b) { if (a ! b) { a ^ b; b ^ a; a ^ b; } } 3、求绝对值 int abs(int a) { int i a 31; return ((a ^ i) - i); } 4、二分查找32位整数前导0个数 int nlz(unsigned x) { int n; if (x 0) return(32); n 1; if ((x 16) 0) {n n 16; x x 16;} if ((x 24) 0) {n n 8; x x 8;} if ((x 28) 0) {n n 4; x x 4;} if ((x 30) 0) {n n 2; x x 2;} n n - (x 31); return n; } 5、二进制逆序 int reverse_order(int n){ n ((n 0xAAAAAAAA) 1) | ((n 0x55555555) 1); n ((n 0xCCCCCCCC) 2) | ((n 0x33333333) 2); n ((n 0xF0F0F0F0) 4) | ((n 0x0F0F0F0F) 4); n ((n 0xFF00FF00) 8) | ((n 0x00FF00FF) 8); n ((n 0xFFFF0000) 16) | ((n 0x0000FFFF) 16); return n; } 6、 二进制中1的个数 unsigned int BitCount_e(unsigned int value) { unsigned int count 0; // 解释下下面这句话代码这句话求得两两相加的结果例如 11 01 00 10 // 11 01 00 10 01 01 00 00 10 00 00 10即由奇数位和偶数位相加而成 // 记 value 11 01 00 10high_v 01 01 00 00 low_v 10 00 00 10 // 则 value high_v low_vhigh_v 右移一位得 high_v_1 // 即 high_v_1 high_v 1 high_v / 2 // 此时 value 可以表示为 value high_v_1 high_v_1 low_v // 可见 我们需要 high_v low_v 的和即等于 value - high_v_1 // 写简单点就是 value value 0x55555555 (value 1) 0x55555555; value value - ((value 1) 0x55555555); // 之后的就好理解了 value (value 0x33333333) ((value 2) 0x33333333); value (value 0x0f0f0f0f) ((value 4) 0x0f0f0f0f); value (value 0x00ff00ff) ((value 4) 0x00ff00ff); value (value 0x0000ffff) ((value 8) 0x0000ffff); return value; // 另一种写法原理一样原因在最后一种解法中有提到 //value (value 0x55555555) (value 1) 0x55555555; //value (value 0x33333333) ((value 2) 0x33333333); //value (value 0x0f0f0f0f) ((value 4) 0x0f0f0f0f); //value value (value 8); //value value (value 16); //return (value 0x0000003f); } 转载于:https://www.cnblogs.com/hwcs/p/7196918.html
