曾彪彪的个人网站
首页
文章列表
>>
文章详情
二进制位运算总结
作者：
曾彪彪
日期：
2025-10-17 03:04:09
阅读(26)
分类：
问题记录
Algorithm
在做csp的笔试题时，发现二进制位运算是弱项，于是做些专项训练，整理以下笔记。 在二进制位运算中，有一些公式和定理可以直接使用，加速计算，并且这是公式有数学意义。 对于异或运算符^，有以下结论： a^a=0 a^0=a a^b=b^a a^b^b=a a^b^a=a 其实异或运算可以看成无进位的加法， 利用这些公式，可以实现两个数交换，找出唯一出现一次的数字等等。 如交换a和b的值，可以写成 a=a^b b=b^a=b^(a^b)=a a=a^b=a^b^b=a --- 对于与运算&，有以下结论： a&a=a a&0=0 a&(~a)=0 a&1=a%2 用来判断奇偶性 a&(0xF)=a%16 用来求模 a & (2^n - 1) ≡ a % (2^n) a&(a-1)，用来去掉最低位的1，比如 111000 & (111000-1)=110000，将最低位的1变成0，这也可以用来判断一个数是否是2的幂次方。 if(a&(a-1))==0 那么a是2的幂次方，a>0。 --- 或运算符| a|0=a a|a=a a|(~a)=全1 --- 取反~ ~a=-(a+1) 在补码表示中成立，如~5=-6, ~(-3)=2 ~~a=a --- 位移运算 a << n = a*(2^n) a >> n = a/(2^n) (a<<1) +1 在二进制数末尾加1 a >> n（负数）算术右移会补符号位（补1） --- 常见组合结论： a&(-a) 取出a中最低位的1，如6=110，-6=1010， 110 & 1010=10，取出最低位的10 a^(a>>1)，计算a的格雷码
评论(0)
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)
提交
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)