【位运算】基础算法总结
目录
基础位运算
- <<
- >>
- ~ ：按位取反
- &：有0就是0（按位与）
- | ：有1就是1（按位或）
- ^ ：相同为0，相异为1/无进位相加（按位异或）
- 规则：
从右往左的下标一直由0->31
给一个数n，确定它的二进制表示的第x位是0还是1
(n>>x) &1
将一个数n的二进制表示的第x位修改成1
n |= (1<<x)
将一个数n的二进制表示的第x位修改成0
n &= (~(1<<x))
位图思想（哈希表）
int：32位
利用32位的每一位0/1来记录信息。
提取一个数（n）二进制表示中的最右侧的1（lowbit）
01110101000
->
00000001000
- -n的本质：
n按位取反+1(补码)
将最右侧中的1，左边的区域（不包括最右侧的1）全部变成相反
所以最右侧的1的左边区域全部&上n会为0，右侧全是0，&上也是0
n&-n
干掉一个数n二进制表示中最右侧的1
- n-1的本质：
最右侧的1的右侧（包括最右侧的1）全部变为相反
n&n-1
异或
1.a^0 = a
2.a^a = 0
3.a ^ b ^ c = a ^ (b ^ c) — 符合交换律和结合律
原文地址：https://blog.csdn.net/qq_72680384/article/details/140243686
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！