(笔记自用)位运算总结+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;
}