位运算

常用技巧

1.位运算符 “^” 按位异或 “&” 按位与 “|” 按位或 “~” 取反 “<<” 算术左移 “>>” 算术右移

1.给定两个十进制数，求他们二进制表示的不同位的个数。（力扣416）

int x,y; int diff=x^y,ans=0; while(diff){ ans+=diff&1; diff>>=1; } cout<<ans<<endl;

2.给定一个十进制整数，输出它在二进制下的翻转结果。（力扣190）

uint32_t reverseBits(uint32_t n){ uint32_t ans=0; for(int i=0;i<32;i++) { ans<<=1; ans+=n&1; n>>=1; } return ans; }

3.判断一个整数是否是4的次方。（力扣342）

思路： 如果一个数字n是2的整数次方，那么他的二进制形式一定是0…010…0这样的；考虑到n-1的二进制是0…001…1，这两个数求按位与的结果一定是0。因此如果n&(n-1)为0，那么这个数是2的次方。 如果这个数也是4的次方，那么二进制表示中1的位置必须为奇数位。那么我们可以把n和二进制的10101…101（即十进制下的1431655765）做按位与，如果结果不为0，那么说明这个数是4的次方。

bool isPowerOfFour(int n){ return n>0&&!(n&(n-1))&&(n&&1431655765); }

4.给定一个非负整数，求从0到n的所有数字的二进制表达中，分别有多少个1。（力扣338）

思路： 可以利用动态规划和位运算快速求解。定义一个数组dp，其中dp[i]表示数字i的二进制含1的个数。对于第 i 个数字，如果它二进制的最后一位为 1，那么它含有 1 的个数 则为 dp[i-1] + 1；如果它二进制的最后一位为 0，那么它含有 1 的个数和其算术右移结果相同，即 dp[i>>1]。

vector<int> countBits(int num) { vector<int> dp(num+1, 0); for (int i = 1; i <= num; ++i) dp[i] = i & 1? dp[i-1] + 1: dp[i>>1]; // 等价于dp[i] = dp[i&(i-1)] + 1; return dp; }