(笔记自用)位运算总结+LeetCode例题:颠倒二进制位+位1的个数
一.位运算总结:
在解题之前理解一下为什么需要位运算？它的本质是什么？
力扣上不少位运算相关的题，并且很多题也会用到位运算的技巧。这又是为什么？
位运算的由来
在计算机里面，任何数据最终都是用数字来表示的（不管是我们平时用的软件，看的图片，视频，还是文字）。
并且计算机运算单元只认识高低电位，转化成我们认识的逻辑，也就是 0 1 。
这就是导致计算机里面任何数据最终都是用二进制（0 1）来保存的数字。只是我们平时看到的图片、文字、软件都只从二进行数字转化而来的。
位运算符:
常用位操作:
1.判断奇偶
(x & 1) == 1 ---等价---> (x % 2 == 1)
(x & 1) == 0 ---等价---> (x % 2 == 0)
2.x / 2 ---等价---> x >> 1
3.x &= (x - 1) ------> 把x最低位的二进制1给去掉
4.x & -x -----> 得到最低位的1
5.x & ~x -----> 0
6.指定位置的位运算
将X最右边的n位清零：x & (~0 << n)
获取x的第n位值：(x >> n) & 1
获取x的第n位的幂值：x & (1 << n)
仅将第n位置为1：x | (1 << n)
仅将第n位置为0：x & (~(1 << n))
将x最高位至第n位（含）清零：x & ((1 << n) - 1)
将第n位至第0位（含）清零：x & (~((1 << (n + 1)) - 1))
7.异或结合律
x ^ 0 = x, x ^ x = 0
x ^ (~0) = ~x, x ^ (~x) = ~0
a ^ b = c, a ^ c = b, b ^ c = a
字母表示：(a ^ b) ^ c = a ^ (b ^ c)
图形表示：(☆ ^ ◇) ^ △ = ☆ ^ (◇ ^ △)
作者：疯子
链接：https://leetcode.cn/problems/reverse-bits/solutions/658732/ccying-gai-zhi-dao-de-wei-cao-zuo-zong-j-etzo/
来源：力扣（LeetCode）
二.Leetcode例题:颠倒二进制位
1.题目:
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：n = 11111111111111111111111111111101 输出：3221225471 (10111111111111111111111111111111) 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
提示：
- 输入是一个长度为
32的二进制字符串
2.题解:
每次把 res 左移，把 n 的二进制末尾数字，拼接到结果 res 的末尾。然后把 n 右移。
举一个 8 位的二进制进行说明：
i n res
- 11001001 -
0 1100100 1
1 110010 10
2 11001 100
3 1100 1001
4 110 10010
5 11 100100
6 1 1001001
8 - 10010011
作者：负雪明烛
链接：https://leetcode.cn/problems/reverse-bits/solutions/686503/fu-xue-ming-zhu-xun-huan-yu-fen-zhi-jie-hoakf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; ++i)
res = (res << 1) + (n >> i & 1);
return res;
}
//注意:n >> i & 1 从n中取出第i位（从右往左数，最右边的是第0位）
// res << 1 为新计算出的位（从n中取出的那一位）腾出空间。
// (res << 1) + (n >> i & 1) 如果n的第i位是1，则在result的相应位置上也设置为1；
// 如果是0，则保持不变（因为加上0不改变原值）三.LeetCode例题:位1的个数
1.题目:
编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中
设置位
的个数（也被称为汉明重量）。
示例 1：
输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。
示例 2：
输入：n = 128 输出：1 解释：输入的二进制串 10000000 中，共有 1 个设置位。
示例 3：
输入：n = 2147483645 输出：30 解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。
提示：
1 <= n <= 231 - 1
2.题解:
利用上面提到的常用位操作：
x &= (x - 1)
从右往左，每次把最低位的 1 给打掉，并累加被打掉1的次数
如：
n : 0B101011
n - 1 : 0B101010
------------------
& : 0B101010
n : 0B101000
n - 1 : 0B100111
------------------
& : 0B100000
作者：疯子
链接：https://leetcode.cn/problems/number-of-1-bits/solutions/658783/ying-gai-zhi-dao-de-wei-cao-zuo-zong-jie-idne/
来源：力扣（LeetCode）
int hammingWeight(uint32_t n)
{
int result = 0;
while (n ? ++result, (n &= (n - 1)) : 0);
//若n非0,则每次去掉最低位的1并计数,否则退出循环
return result;
}
此题也可以用暴力破解,但效率不如使用位运算
int hammingWeight(int n) {
int count=0;
while(n)
{
if(n%2==1)
count++;
n/=2;
}
return count;
}