越秀网站建设价格,抖音小程序开发者平台,张家口领先的网站建设服务商,企业网站建设排名口碑位运算是最高效而且占用内存最少的算法操作#xff0c;但也是最难看懂的操作。然而#xff0c;关于位运算的用法#xff0c;笔者查了许多资料#xff0c;似乎都没有找到详细而系统的讲解资料。笔者对位运算的操作相当感兴趣#xff0c;因此斗胆尝试对位运算来一个的总结。…位运算是最高效而且占用内存最少的算法操作但也是最难看懂的操作。然而关于位运算的用法笔者查了许多资料似乎都没有找到详细而系统的讲解资料。笔者对位运算的操作相当感兴趣因此斗胆尝试对位运算来一个的总结。本文先从基本概念出发然后从基本概念推导出基础应用然后再到算法题实战。层层推进逐步迭代。本人水平有限如有勘误敬请指正。说明本文会以Python的交互环境来做代码演示。关于本文的约定非代码块中的二进制数以下标x来表示进制数如十进制数15用二进制表示为 而用十六进制则表示为 所有代码块中的二进制数字都以0b开头比如十进制数15用二进制表示为0b1111有时候需要更直观地表示会使用竖式表示如两个二进制数的and操作表示为所有代码块中的十六进制数字都以0x开头比如十进制数255用十六进制表示为0xffbin()函数是Python中把十进制转换为二进制的转换函数所有的位运算操作的命名均用英文命名以增加辨识度。概念篇and 操作操作符“”定义称为按位与运算符。它对整型参数的每一个二进制位进行布尔与操作即两个对应的二进制位同时为1时才等于1。or 操作操作符“|”定义称为按位或运算符。它对整型参数的每一个二进制位进行布尔或操作即两个对应的二进制位任意一个为1时就等于1。xor操作操作符“^”定义称为按位异或运算符。它对整型参数的每一个二进制位进行布尔异或操作即两个对应的二进制位有且仅有一个为1时才等于1。not操作操作符“~”定义称为按位非运算符。它是一个单运算符对运算数的所有二进制位进行取反操作。shl操作操作符“定义称为按位左移运算符。它把第一个运算数的所有二进制位向左移动第二个运算数指定的位数而新的二进制位补0。将一个数向左移动N个二进制位相当于将该数乘以2的N次方比如 shr操作操作符“”定义称为按位右移运算符。它把第一个运算数的所有二进制位向右移动第二个运算数指定的位数。为了保持运算结果的符号不变左边二进制位补 0 或 1 取决于原参数的符号位。如果第一个运算数是正的运算结果最高位补 0如果第一个运算数是负的运算结果最高位补 1。将一个数向右移动N个二进制位相当于将该数除以2的N次方比如 (总是向负无穷方向取整)。原理篇进制转换进制之间的转换其实是个数学问题在实际应用中我们基本上无需操心。因此这里想说的不是计算问题而是逻辑问题。二进制与十六进制有着天然的联系——每四个二进制位可以代表一个十六进制位由上图可见如果说二进制转十进制还要稍稍心算一下的话那二进制转十六制可以马上得出。只要记住了一个十六进制位与四个二进制位的对应关系就好了。同理八进制位与二进制的关系是每三个二进制位对应一个八进制位但实践中八进制并不常见因此点到即止。那么为什么二进制与十六进制在实践中更常见呢这是与内存的储存单位有关。字节与二进制数的关系对于计算机而言最小的储存单位是一个字节英文为byte。byte既是一个单位也是一种数据类型(关于数据类型的解释可查阅C/C、JAVA等静态类语言的相关资料本文不作介绍)。对于一个byte的数据用了八个二进制位去储存数据因此能正好用两个十六进制位来省略表示(比十进制还少写一位)。这就是为什么在实际操作中二进制与十六进制更常见的原因。二进制运算符的操作范围笔者查阅了许多二进制运算的相关资料似乎都忽略了对这一点的介绍。二进制运算符的作用范围与参与运算的变量的数据类型有关比如以JAVA为例对于byte类型变量由于byte以8-bit(8个二进制位)表示因此相应的位运算符的作用范围就是8-bit对于int类型变量由于int以32-bit表示因此位运算符的作用范围就是32-bit假如两个大小不一的数据类型进行操作那位运算的作用范围会以较大的数据类型作为基准范围。二进制数的符号有了数据类型的范围限定因此才有了高位、低位、符号位的概念。高位指在数据类型限定范围内靠左的二进制位低位指在数据类型限定范围内靠右的二进制位符号位指在数据类型限定范围内最左边的一个二进制位符号位为0表示正数1表示负数。(除了C语言存在无符号的值类型外绝大部分语言的值类型都默认为有符号的数值类型)因此假如一个byte范围内的整数提升为一个int范围内的整数由于二进制位数的范围大了必然需要进行补位因此当原byte整数为正数时提升为int类型时补位全部以0补位当原byte整数为负数时提升为int类型时补位全部以1补位为什么要这样做因为这样才能保证数值在范围提升后原值的十进制数不变。以下来看看JAVA的验证代码// byte类型的值范围是[-128,127]byte a (byte) -55; //由于值在byte范围内因此强制转换缩小变量内存范围不会改变原值byte b (byte) 100;System.out.println(Integer.toBinaryString(a)); //输出(二进制数)11111111111111111111111111001001System.out.println(Integer.valueOf(a)); //输出-55(重新提升范围值不变)System.out.println(Integer.toBinaryString(b)); //输出(二进制数)1100100(高位的0会被省略显示)System.out.println(Integer.valueOf(b)); //输出100二进制下的负数表示法对于一个十进制的负数我们经常把它看作是一个数加一个负号然而对于二进制负数来讲却不是一堆二进制位数加一个符号位。二进制的正数与负数之间的关系更像是“进位”的关系。以下我们以一个byte值来举例如上所述byte的数值范围是[-128,127]。为了让表示更清楚笔者特意把符号位隔开。留意从0到-1由于非符号位全部为0已经没有东西可减但假如我们假设从更高的位借来了一个1这样就能让 了有了-1那 就可以继续成立了……直到把除符号位之外的位全部减完这时十进制数就相当于-128。因此八位二进制数可以表达的数为 个即[-128,127]。二进制数的性质由以上的二进制数变化规律我们可以发现二进制数有以下性质x -x - 1从以上0与-1的按位关系可以看到两者的二进制位正好取反此规律能推广到1与-22与-3……等等。因此该性质是not操作中最常使用的性质。(~x)x 0任意数与它的取反数的and操作结果为0。(~x)|x -1任意数与它的取反数的or操作结果为-1。(~x)^x -1任意数与它的取反数的xor操作结果为-1。x|0 x任意数x与0的or操作结果为x自己。x^0 x任意数x与0的xor操作结果为x自己。x^y^y x任意数x与任意数y进行两次xor操作结果为x自己。与四则运算一样位运算也有它自己的定律。因此我们有必要先熟悉并证明一下这些定律。定律篇and操作交换律ab ba证明略(因为显然易见)结合律(ab)c a(bc)证明只要证明一个二进制位便能推广到N个二进制位。(10)0 1(00) 0110 1(10) 0。or操作交换律a|b b|a证明略结合律(a|b)|c a|(b|c)证明只要证明一个二进制位便能推广到N个二进制位。(1|0)|0 1|(0|0) 11|1|0 1|(1|0) 1。xor操作交换律a^b b^a证明略结合律(a^b)^c a^(b^c)证明not操作结合律a ~(~a)证明略shl操作无shr操作无继续深入传送门黄伟亮二进制与位运算实用操作汇总(应用篇)zhuanlan.zhihu.com参考资料
